Lecture Schedule

Tu

• No class

Th, 9/24

• Introduction;
• Structure and requirements of the course;
• Overview of trees and their properties

Friday(Discussion)

• The C++ programming language;
• comparison of C++ and Java;
• introduction to OO programming in C++

Tu, 9/29

• More on C++
• Reading Quiz is based on Lecture 1 slides
• Reading Quiz due 9/30 @8am
• Also see Paul Kube's slides on Java vs C++
• Ref: Morin: 6.1-6.3

Th, 10/1

• Binary search trees;
• basic operations on BST's
• C++ Iterator Tutorial
• Aux: Drozdek 1.1-1.4, 6.1-6.2, 6.4-6.6
• Also see Paul Kube's slides on BSTs and C++ iterators

Friday(Discussion)

Tu, 10/6

• C++ iterators, and the BST average case analysis
• Reading quiz is based on Lecture 2 and 3 slides
• Reading quiz due 8/6 @8am
• Also see Paul Kube's slides on Average Case Analysis of BST

Th, 10/8

• AVL trees and AVL rotations;
• AVL search tree algorithms
• Also see Paul Kube's slides on AVL tree

Friday(Discussion)

Tu, 10/13

• Quiz AVL is due on 10/13 @8am
• Treaps;
• Find, insert, delete, split, and join in treaps;
• Randomized search trees
• Also see Paul Kube's slides on Treaps and RSTs

Th, 10/15

• Random number generation;
• skip lists;
• Open Data Structures, Chapter 4: 4.1-4.2 (required), 4.4 is optional
• Aux: Paul Kube's slides on Skip Lists
• code: skiplist.cpp

Friday(Discussion)

Tu, 10/20

• Red-black trees;
• Analysis of red-black trees;
• red-black search tree algorithms
• Quiz SL due @8am
• Reading: Paul Kube's slides on Red-Black trees

Th, 10/22

• Trees for representation;
• intro to Huffman coding
• Reading: Paul Kube's slides on Huffman coding
• Reading: Wiki
• Aux: Drozdek 11.1-11.2

Friday(Discussion)

Tu, 10/27

• Priority queues; heaps;
• I/O in C++;
• Buffering; Bitwise I/O
• code: heap.cpp
• Reading: Paul Kube's slides on Huffman coding analysis
• Reading: Paul Kube's slides on C++ I/O

Friday(Discussion)

Tu, 11/3

• C++ I/O continued
• Intro to Graphs;
• Reading: Paul Kube's slides on Graph

Th, 11/5

• Djikstra's algorithm
• Reading: Paul Kube's slides on Graph Algorithms

Friday(Discussion)

Tu, 11/10

• Graph algorithms;
• MST; Union-Find
• Reading: Paul Kube's slides on Spanning Tree Algorithms
• Reading: Paul Kube's slides on Union-Find

Th, 11/12

• Union-Find, Path compression;
• Hashing;
• Reading: Paul Kube's slides on Hashing
• Aux: Drozdek 10.1-10.2

Friday(Discussion)

Tu, 11/17

• Hashing; Boggle;

Th, 11/19

• Radix search;
• digital search trees, multiway tries, ternary tries
• Reading: Paul Kube's slides on Tries
• Aux: Drozdek 7.2

Friday(Discussion)

Tu, 11/24

• Time costs in a memory hierarchy;
• B-trees;
• Open Data Structures, Chapter 14: 14.1-14.3

Tu, 12/1

• 2-3 trees; Analysis of B-trees

Th, 12/3

• Final Review
• Practice Final

Friday(Discussion)

• Final Review

Tu, 12/8

• Finals week: No class