Lecture Notes

The instructor reserves the right to update the notes right up to class time and within two weeks after each corresponding lecture. Check the time and date on the first slide of each set to make sure you have the most up-to-date version.

Course Information [PDF]

Algorithm Analysis - part 1 [PDF]
Reading: chapter 4; section 3.1.2 (insertion sort); insertion sort animation
Homework: R-4.9 to R-4.13 (R-4.16 to R-4.20 in 5th edition)

Algorithm Analysis - part 2 [PDF]
Reading: chapter 4
Homework: R-4.2, R-4.3, R-4.8 (R-4.7, R-4.8, R-4.13 in 5th edition)

Recursion and Logarithms [PDF]
Reading: chapter 5
Homework: R-5.1, R-5.5, R-5.8, R-5.10, C-5.17, C-5.18 (R-3.13, R-3.14, C-3.14, R-3.5, C-3.20, C-3.21 in 5th edition)
Hint: Write and run Java programs to verify the correctness of your algorithms.

Merge Sort [PDF]
Reading: section 12.1

Quick Sort [PDF]
Reading: section 12.2

Homework: Read section 3.1, "Using Arrays".

Linked Lists [PDF]
Reading: sections 3.2 and 3.4

Stacks [PDF]
Reading: section 6.1

Queues [PDF]
Reading: section 6.2

Double-ended Queues, Extendable Arrays [PDF]
Reading: sections 6.3, 7.2.3

Introduction to Trees [PDF]
Reading: chapter 8

Binary Trees [PDF]
Reading: section 8.2
Homework (for both general and binary trees): R-8.2, R-8.3, R-8.7, R-8.8, C-8.30, C-8.32, C-8.42, C-8.43, C-8.45 (R-7.5, R-7.6, R-7.7, R-7.16, R-7.23, C-7.4, C-7.5, C-7.6, C-7.9 in 5th edition)
Advanced exercises: C-8.28, C-8.29, C-8.55 (C-7.23, C-7.33, C-7.34 in 5th edition)

Binary Search Trees [PDF]
Reading: section 11.1
Homework: R-11.1 to R.11-4 (R-10.1 to 10.4 in 5th edition)

Software engineering disasters [PDF]

AVL Trees [pdf]
Reading: sections 11.2 and 11.3

Midterm review [PDF]

Heaps [PDF]
Reading: sections 9.1 to 9.3

Heap Sort [PDF]
Reading: section 9.4.2

Hash Tables, part 1 - PDF, PowerPoint slides with detailed notes, VIDEO (posted Mar. 22)
Hash Tables, part 2 - PDF, PowerPoint slides with detailed notes, VIDEO (posted Mar. 25)
Reading: section 10.2

Graphs [PDF] - for self-study (not on final exam)
Reading: sections 14.1, 14.2 and 14.3