Lecture Schedule

Monday

• Course Overview
• Binary Search Trees Overview
• Reading: zyBook 14-1, 14-2
• Ref: Morin: 6.1-6.3
• Aux: 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
• Required C++ Reading: zyBook 8-1 to 8-3
• Reading quiz: zyBook Activity 8.1.1 to 8.3.2
• Reading quiz: zyBook Challenge homework activity not required
• Reading quiz: due Friday (4/3) 11:59pm
• Ref: zyBook 1-1 to 7-12
• Official Git Book 1.1, 1.3 and chapter 2.
• Got 15 minutes and want to learn Git? Git Challenge
• Also see Paul Kube's slides on Java and C++

Friday

• Implementing BSTs, C++ iterators
• Required Reading: zyBook 14.3-14.7
• Reading Quiz: zyBook Activity 14.3.1 to 14.7.2
• Reading Quiz: due Friday (4/3) at 11:59pm
• C++ Iterator Tutorial
• Aux: Drozdek 6.4-6.6
• Also see Paul Kube's slides on BSTs and C++ iterators

Monday

• Huffman coding
• Reading: Wiki
• Aux: Drozdek 11.1-11.2
• Also see Paul Kube's slides on decision trees and Huffman coding

Wednesday

• Huffman coding and PA2 overview
• Reading Quiz on Ted due Wed (4/8) 8am
• Quiz deadline extended till Fri (4/10) 8am
• Aux: Drozdek 11.1-11.2
• Also see Paul Kube's slides on Huffman implementation

Friday

• C++ I/O
• Required reading: zyBook 14.11 Heaps
• Required Reading: zyBook 9.1, 9.2, 9.5
• Reading Quiz: zyBook Activity 14.11.1 and 9.5.1
• Reading Quiz: due Friday (4/10) at 8:00am
• C++ tutorial on I/O
• Also see Paul Kube's slides on C++ I/O

Monday

• C++ I/O continued
• No new reading

Wednesday

• Runtime Analysis of Huffman, BST
• Required Reading: zybook 16.6-16.7
• Reading Quiz due Wed at 8am: zybook activities 16.6.1-16.6.2, 16.7.1 -16.7.2
• Also see Paul Kube's slides on Huffman

Friday

• BST average case analysis
• Reading: Paul Kube's slides on Average Case Analysis of BST
• Reading quiz on TED due Friday(4/17) at 8am

Monday

• BST analysis and AVL Trees
• Also see Paul Kube's slides Analysis of binary search trees; balance; AVL trees

Wednesday

• Introduction to graphs, graph search
• Reading: zyBook 19.1, 19.2, 19.3
• Aux: Drozdek 8.1-8.2

Monday

• Graph search algorithms: Depth First Search(DFS), Breadth Frist Search(BFS)
• Aux: Drozdek 8.1-8.3

Wednesday

• Dijkstra's shortest path algorithm
• Read Paul Kube's slides on graph search (Slide 27-end)
• Reading Quiz: TED Quiz Graph (due 8am on Wed (4/29))
• Aux: Drozdek 8.3

Friday

• Minimum Spanning Trees (Prim's and Kruskal's)
• Reading: Paul Kube's slides on MST's
• Reading Quiz: TED Quiz shortest path (due 8am on Sat (5/2))
• Aux: Drozdek 8.4.1, 8.5 (up to page 413, Kruskal's Algo only)

Monday

• BFS and Kruskal's run time and simple union-find
• Reading: Kube slides 18-26
• Reading: Kube slides 20-28
• Aux: Drozdek 8.4.1, 8.5

Wednesday

• Smart Union: union by height and size
• Reading Quiz MST on TED due at 8am on 5/6
• Also see: Paul Kube's slides on union-find (slides 13 to 24)

Friday

• Find with path compression, run time for Dijkstra and Prim
• Reading Quiz Union-Find on TED due at 8am on 5/8

Monday

• Hashing
• Reading: zyBook 18.1

Wednesday

• Hashing
• Reading: zyBook 18.1
• Reading Quiz: Complete zyBook activity 18.1.1, 18.1.2, 18.1.3
• Reading Quiz is due on Wednesday (5/13) at 8am
• No TED quiz
• Reading: Kube slides on Hashing
• Aux: Drozdek 10.1-10.2

Friday

PA4(Boggle) Introduction

No new reading

No Quiz

Monday

• Multiway tries
• Kube slides 21-25
• Aux: Drozdek 7.2

Wednesday

• Midterm Review
• Reading Quiz Tries on TED due at 8am on 5/20
• Kube slides 26-39
• Aux: Drozdek 7.2

Wednesday

• Ternary Tries and Red-Black Trees
• Reading: Paul Kube's slides on Red-Black trees
• Reading Quiz RB on TED due at 8am on 5/27

Friday

• Red-Black Trees (contd)
• Reading: Paul Kube's slides on Red-Black trees
• Reading Quiz on TED due at 8am on 5/29

Monday

• Skip Lists
• Open Data Structures, Chapter 4: 4.1-4.2 (required), 4.4 is optional
• Aux: Paul Kube's slides on Skip Lists

Wednesday

• B-trees
• Open Data Structures, Chapter 14: 14.1-14.3
• Aux: Paul Kube's slides on B-Tree
• Reading Quiz on TED due at 8am on 6/3

Friday

• Data structure comparison and Final review
• Reading Quiz on TED due at 11:59pm on 6/5