| No. | Date | |
|
| 1. | 2009/08/26 |
Introduction to the course: organization. Reading assignment: Chapter 1.2 - 1.3 |
Handout First HW (due back: 2009/08/31) |
| 2. | 2009/08/31 |
Growth of functions: Big Oh notation. Properties Determining the running time of algorithms: some simple examples Reading assignment: Chapter 2.1 - 2.4.2 |
HW01 Solutions |
| 3. | 2009/09/02 |
Solving recurrences: logarithms in the solution. Binary search: these notes Merge sort: page 261 of the text. Four solutions to the Maximum Subsequence Problem |
|
| 4. | 2009/09/09 | NO LECTURE | |
| 5. | 2009/09/14 | Abstract Data Types (ADT's). Lists (Sec 3.2 of the text); Stacks (Sec 3.6.1-3.6.2); Queues (Sec 3.7.1-3.7.2) |
Practice problems from Ch 2 (not to be turned in) Solutions to these practice problems |
| 6. | 2009/09/16 |
Recursive programming on lists Trees: definitions and representation. General (Sec 4.1.1) and Binary (Sec 4.2.1) The Dynamic Dictionary ADT. |
First programming assignment (due back: 2009/09/28) |
| 7. 8. |
2009/09/21 2009/09/23 |
GUEST LECTURES by Professor Jasleen Kaur Search Tree implementation of Dynamic Dictionaries. Implementing contains, insert, remove, findMin and findMax. Secs 4.3.1-4-3-4 AVL tree implementation of Dynamic Dictionaries (single rotation): Sec 4.4.1 |
|
| 9. | 2009/09/28 |
Dynamic Dictionary implementations: Arrays (and sorted); Linked lists (and sorted) AVL trees: definition and properties Single and double rotations for insertions: 4.4.2 |
|
| 10. | 2009/09/30 |
Deletion in AVL trees: lazy deletion Median-find (findKth) in BST's Tree traversals: in-order, pre-order, and post-order. Level-order traversals. Sec 4.6 |
Practice problems from Ch 4 (not to be turned in)
Programming assignment (due back: 2009/10/21) |
| 11. | 2009/10/05 | IN-CLASS EXAM | |
| 12. | 2009/10/07 |
The Priority Queue ADT. Some possible implementations: as (sorted and unsorted) Linked Lists; as BST's; as Balanced search trees Binary heaps: the structure and heap-order properties Implementing insert and deleteMin on binary heaps. Sec 6.3.1-6.6.3 |
Some practice problems from Ch 6 (not to be turned in) |
| 13. | 2009/10/12 |
Additional operations on Binary heaps: increase-/ decrease-key; delete;
buildHeap -- linear-time implementation. Sec 6.3.4 Heapsort. Sec 7.5 The Mergeable Pqueue ADT Implementation via binomial queues |
|
| 14. | 2009/10/14 |
Binomial trees and queues: structure and properties Implementation of merge; implementation of insert and deleteMin Sections 6.8.1 and 6.8.2 |
|
| 15. | 2009/10/19 |
Implementing Dynamic Dictionaries via hash tables Designing good hash functions; Resolving collisions through separate chaining Sections 5.1 - 5.3 |
|
| 16. | 2009/10/21 |
Hashing: Resolving collisions through probing; linear
and quadratic probing, and double hashing. The
problems of primary and secondary clustering. Sec 5.4 Rehashing. Amaortized analysis of rehashing. Sec 5.5 |
Hashing practice problems: Qns 5.1, 5.2, and 5.4 of your text. Binomial Queue practice problems: Qns 6.32, 6.38 of your text. |
| 17. | 2009/10/26 | IN-CLASS EXAM | |
| 18. | 2009/10/28 | No Class | |
| 19. | 2009/11/02 |
The dynamic equivalence problem: Union Find Matrix representations; linked list representations Forest of trees. Optimizations: union-by-height, and path compression The Ackermann function Reading: Secs 8.1 - 8.5 |
|
| 20. | 2009/11/04 | Analysis of Union-find: union-by-rank and find with path compression. Sec 8.6 | |
| 21. | 2009/11/09 | Complete analysis of union-find: the inverse Ackermann function | |
| 22. | 2009/11/11 |
Graphs: terminology and representation. Sec 9.1 Topological sort of DAG's. Sec 9.2 |
Practice questions: 9.1 and 9.2 of your text. |
| 23. | 2009/11/16 |
Shortest paths on Graphs. Definition and use.
The problem of negative cycles. Negative weights.
Unweighted shortest paths. Weighted shortest paths: the Dijkstra algorithm. Readings: Sec 9.3.1 - 9.3.2 |
Final programming assignment (due back: Nov 30th). |
| 24. | 2009/11/18 |
Dijkstra's algorithm: implementation details. Dealing with negative edges Dijkstra's algorithm on DAG's Warshall-Floyd algorithm Readings: Secs 9.3.2-9.3.4. Sec 10.3.4 |
|
| 25. | 2009/11/23 | Adjacency Matrix vs Adjacency List representations of Graphs: some examples | Practice problems: Qns 9.5, 9.7(a), 9.10 |
| 26. | 2009/11/30 | Minimum cost spanning trees (MCST's) for undirected graphs. Kruskal's algorithm Reading: Section 9.5; 9.5.2 | |
| 27. | 2009/12/02 | IN-CLASS EXAM | |
| 28. | 2009/12/07 | ||
| 29. | 2009/12/09 | NO CLASS | |
| - | 2009/12/14 | Final Exam at 4:00 pm. |
TOPICS TO BE COVERED: