Time in weeks |
Topic | Reading | Comment | |
---|---|---|---|---|
1 | Introduction. Which algorithm is best? |
1.1, 2.1-2.3 | Review C++ on your own: variables, operators, expressions, assignment; control statements (if, if-else, for, while); functions; class definitioin (data and function members), class implementation; using class objects; arrays |
|
1 | Review Math, Recursion, and C++ dynamic memory allocation |
Study Ch 1 for homework | Do the review yourself. For dynamic memory allocation you may use your old textbooks in C++. Focus on: new, delete, dynamic arrays | |
1 | How to choose between two or more algorithms that
solve the same problem?
Theoretical foundations: Complexity, recursion. Running time calculations. |
10.2.2, 2.3, 2.4.1-2.4.3 | ||
2 | Theoretical foundations: Complexity, solving recurrences. Algorithm design techniques: Greedy and Divide-and-Conquer |
Ch 2, 10.1-10.1.1, 10.2 (p409) 10.2.2, 7.6 |
||
1 | Sorting: Comparison based sorting, lower bound | 7.1-7.3,7.6,7.7,7.9,3 | ||
1 | Review List, Stacks, Queues | Ch 3 | ||
1 | Dynamic set ADT Dictionary, Hashing | class notes, Ch 5 | ||
1 | Priority Queue ADT, binary heaps | Sections 6.1-6.4 | ||
2 | Trees. Binary Search Trees. Balanced search trees | Ch 4 | ||
2 | Graphs and applications. Representing graphs. Graph searches: BFS, DFS. Graph problems and algorithms | Ch 9 |