Business

• Test 1 is Tuesday, Feb. 15 during class.

The test will take the entire class period.
No notes or cheat sheets allowed.
• Project 2 is on the web.

It is due March 3rd.
Less programming but conceptually harder.
Start early.
• Lab this week is about the STL map (which uses trees).

Need Help?

I have office hours for an hour after class.

But, feel free to pester the TA's.

Karan Gupta 
E-Mail: guptak2@cs.rpi.edu 
Office: Lally 009 
Office Hours: Friday, 10:30 - 12:00 
Phone: x8981 
Section 1: Friday,    8:00 - 9:50 AM,  Sage 3101 
Section 7: Friday,   6:00 - 7:50 PM,  Sage 3101 

Ann Grace 
E-Mail: gracea@cs.rpi.edu 
Office:  Amos Eaton 207 
Office Hours: Thursday, 2:15 - 3:45 
Phone: x6597 
Section 6: Friday,   12:00 - 1:50 PM,  VCC North 
Section 8: Friday,   10:00 - 11:50 AM, Pittsburg 4114 

Shrikrishna Karand 
E-Mail: karans@cs.rpi.edu 
Office: Lally 004 
Office Hours: Monday and Tuesday, 6:00 - 7:30 PM 
Phone:  x2135 
Section 2: Thursday, 8:00 - 9:50 PM, Sage 3101 
Section 5: Thursday, 6:00 - 7:50 PM, Sage 3101 

Sidhartha 
E-Mail: sidha@cs.rpi.edu 
Office: Lally 003B 
Office Hours: Tuesday 10:00-11:30 
Phone: x8565 
Section 3: Friday,   12:00 - 1:50 PM, Sage 3101 
Section 4: Friday,   2:00 - 3:50 PM,   Sage 3101

Review for Test 1

Generic Programming and STL

Study: http://www.sgi.com/Technology/STL/

Emphasis: General knowledge questions, very basic, don't spend too much time studing this.

• General concept of generic programming
• Generic containers
• Generic algorithms
• Iterators

Important concepts:

Containers are heavily parameterized. One container can hold many different data types.

Iterators are the glue between containers and algorithms. In STL, generic algorithms are defined in terms of iterator (i.e., pointer) parameters. So the algorithm doesn't even need to consider the implementation details of the container. Therefore, one algorithm can operate on many different containers (as long as the container supports certain iterator operations).

Iterators are classes (the underlying implementation is a pointer). Iterators can have member functions and operators, and can be specialized for specific containers.

Basic Containers and STL

Study:

• http://www.sgi.com/Technology/STL/
• Text 3.2

Emphasis: Know how to use these containers; know the advantages and disadvantages of array implementation (std::vector) and linked list implementation (std::list);

• Array implementation vs. linked list implementation
• STL vector (inserting and deleting)
• STL list (inserting and deleting)
• Iteration through basic containers

Sorting

Study:

• Text 7.2, 7.3, 7.6, 7.7, 7.9, 7.10

Emphasis: Know how the algorithms work; be prepared to implement part of each algorithm; know the worst, average, and best case running times.

• Insertion sort (7.2)
• Inversions and their relation to the average analysis of insertion sort (7.3)
• Mergesort (7.6)
• Merge technique
• Quicksort (7.7)
• Decision trees and their relation to the lower bound of sorting (7.9)
• Bucket sort (7.10)

Algorithm Analysis

Study:

• Text 2.1, 2.2, 2.3, 2.4

Emphasis: Be able to count the number of operations in an algorithm (may be recursive). Absolutely memorize the definition of following concepts:

• O(f(n))
• $\Omega(f(n))$
• $\Theta(f(n))$

Trees

Study:

• Text 4.1, 4.2

Emphasis:

• Tree terminology
• Binary tree features

2000-02-11