Lecture Schedule

Monday

• Binary Search Trees Overview
• Reading: Drozdek 1.1-1.4, 6.1-6.2, 6.5-6.6
• Also see Paul Kube's slides on Java vs C++

Wednesday

• C++ vs. Java: Case study Binary Search Trees, C++ development using Git
• Official Git Book 1.1, 1.3 and chapter 2.
• Got 15 minutes and want to learn Git? Git Challenge

Friday

• Implementing BSTs, C++ iterators
• Drozdek 6.4-6.6, (Much of this reading is, or should be, review)
• Also see Paul Kube's slides on BSTs and C++ iterators

Monday

• BST strengths and weaknesses, Average Case Analysis
• Drozdek 2.1-2.8
• Also see Paul Kube's slides on BSTs average case analysis (through slide 20).

Wednesday

• BST average case analysis

Friday

• Huffman coding
• 11.1-11.2 (11.2.1 is optional)
• Also see Paul Kube's slides on decision trees and Huffman coding

Monday

• Huffman coding continued
• No new reading

Wednesday

• Huffman continued, priority queues, heaps
• No new reading

Friday

• C++ I/O
• C++ tutorial on I/O
• Also see Paul Kube's slides on C++ I/O

Monday

• C++ I/O
• No new reading

Wednesday

• Balanced binary trees, AVL trees
• Reading: Drozdek 6.7, 6.10
• Also see Paul Kube's slides on AVL trees

Friday

• Treaps, Randomized Search Trees
• Also see Paul Kube's slides on RSTs and RAS time costs (slides 22-32)
• Seidel and Aragon: Randomized Search Trees, Aragon and Seidel, Algorithmica (1996)

Monday

• Midterm review and RST runtime analysis

Friday

• Introduction to graphs, graph search
• Drozdek 8.1-8.2

Monday

• Graph search algorithms continued
• Drozdek 8.1-8.3

Friday

• Dijkstra's shortest path algorithm
• Drozdek 8.3

Monday

• Minimum Spanning Trees (Prim's and Kruskal's)
• Reading: Drozdek 8.4.1, 8.5 (up to page 413, Kruskal's Algo only)
• Also see: Paul Kube's slides on MST's

Wednesday

• Union-Find Data structure, Eager and Lazy unions with up-trees
• Read: Paul Kube's slides on Kruskal's and Equivalence Classes, Slides 24 to 29
• Also see: Paul Kube's slides on union-find Slides 1 to 13

Friday

• Lazy smart unions and find with path compression
• Also see: Paul Kube's slides on union-find (slides 13 to 24)

Monday

• Multiway tries, ternary tries (continued)
• Reading: Drozdek 7.2
• Also see: Paul Kube's slides on Ternary tries (slides 26-39) (the rest are optional)

Wednesday

• Skip Lists
• Random Number Generation
• Also see: Paul Kube's slides on random number generation and skip lists

Monday

• Red-Black Trees
• Reading: Paul Kube's slides on Red-Black trees

Wednesday

• Red-Black trees contd.
• Memory and disk storage
• B-Trees
• Reading: Drozdek 7.1

Friday

• More on Boggle (PA4)

Monday

• B-trees Continued

Wednesday

• Hashing
• Reading: Drozdek 10.1-10.2

Friday

• Data structure comparison and Final review
• Review Drozdek 10.1-10.2 as well as all previous data strucres