This course outline is under construction. This page will
be updated periodically with the highlights from each week, so visit here
often.
Problems 1-50, 1-52.
UNIX and C environment. Learn about editors, file systems, and course machinery. Tutorials
Layered memory. The heap as an array.
Required.Insert/delete in middle. Pointer-chasing.
Header cells, double linking, circular lists.
Problems 3-5, 3-7, 3-13.
Quiz on Monday.
Chapter 4 Tree terminology.
Binary trees. Traversal.
Chapter 3 XOR linking.
Topological Sort.
Chapter 4 Tree
threading. Insert node, delete node.
Sequential representation of trees.
Level-order,
Blind Triple order.
Chapter 5. Vectors,
Row-major arrays.
Multi-dimensional Arrays, Dope/Iliffe vectors.
Chapter 5.3.
Sparse arrays.
Midterm October 15.
Chapter 5.4. String representation, character
frequency,
compression.
String search problem.
Strings and Lempel-Zif compression
Problems for Discussion section: Lewis and Dennenberg 5.37 and 5.39.
Chapter 5.5. Knuth, Morris, Pratt and Boyer-Moore string search.
Chapter 10: Storage Management: Reference counting vs. Garbage Collection.
Chapter 10 Storage Management. And hybrids.
Chapter 6: Skip Lists, Static search structures.
Chapter 7: AVL trees.
Chapter 7: AVL(balanced)-trees. B-trees.
Second Quiz on November 19.
Chapter 7: B+trees.
Hash tables (Chapter 8).
Chapter 9.1: Priority Queues via dynamic search algorithms.
Designing the COBOL data structure.
Implementing the
COBOL data structure.
Floyd's Hare 'n Tortise algorithm.