CompSci 161 - Design and Analysis of Algorithms - Fall, 2023 (Dillencourt)
Topics covered by lecture
This is the list of topics that have been covered in each lecture.
For each lecture, the slides covered in the lecture are given.
- Lecture 1 - Friday, September 29:
- Overview of the course
- Introduction, part 1 [Slides 1-1 through 1-8]
- Lecture 2 - Monday, October 2:
- Introduction, part 2. Asymptotic Notation, part 1.
[Slides 1-9 through 1-17]
- Lecture 3 - Wednesday, October 4:
- Asymptotic Notation, part 2.
[Slides 1-18 through 1-31]
- Lecture 4 - Friday, October 6:
- Sums and summations; Logarithms and Exponents; Floors and Ceilings;
Factorials and combinations;
Harmonic numbers.
[Slides 1-32 through 1-45]
- Lecture 5 - Monday, October 9:
- Proofs / Proof by Induction; Basic Probability, part 1.
[Slides 1-46 through 1-62]
- Lecture 6 - Wednesday, October 11:
- Basic Probability, part 2.
[Slides 1-63 through 1-64]
- Basic data structures:
Arrays, Linked lists, stacks, queues, dictionaries, hash table.
Binary trees.
[Slides 2-1 through 2-10]
- Lecture 7 - Friday, October 13:
- Binary search: Correctness, analysis, proof of optimality
using decision trees.
Sorting, basic terminology (permutations, inversions).
Comparison-based sorting.
Insertion sort.
[Slides 2-11 through 2-28]
- Lecture 8 - Monday, October 16:
- Selection sort. Quicksort, part 1
[Slides 2-29 through 2-44]
- Lecture 9 - Wednesday, October 18:
- Quick sort, part 1.
Merge sort and applications, part 1.
[Slides 2-45 through 2-56]
- Lecture 10 - Friday, October 20:
- Merge sort and applications, part 2.
[Slides 2-57 through 2-60]
- Priority queues.
Binary heaps: basic properties, sift-up, sift-down, insertion, deletion.
[Slides 3-1 through 3-13]
- Lecture 11 - Monday, October 23:
- Binary heaps: construction (heapify).
Heap sort.
Lower bounds on comparison-based sorting / decision tree argument.
Optimally sorting 5 elements.
[Slides 3-14 through 3-40]
- Lecture 12 - Wednesday, October 25:
- Address calculation sorting: overview
[Slide 3-41]
- Bucket sort [Slides 3-46 through 3-49]
- Discussion, questions about upcoming Midterm 1
- Friday, October 27: No lecture (Midterm 1)
- Lecture 13 - Monday, October 30:
- Radix sort [Slides 3-50 through 3-53]
- Counting sort [Slides 3-42 through 3-45]
- Greedy algorithms. Overview. Fractional knapsack problem.
[Slides 4-1 through 4-6]
- Lecture 14 - Wednesday, November 1:
- Task scheduling to minimize the number of processors required.
Task scheduling on a uniprocessor to maximize the number of tasks
that can be performed.
Huffman trees and Huffman coding.
[Slides 4-7 through 4-19]
- Lecture 15 - Friday, November 3:
- Divide and conquer. The divide-and-conquer recurrence equation.
Solving a divide-and-conquer recurrence equation using the
Simplified method.
[Slides 5-1 through 5-8]
- Lecture 16 - Monday, November 6:
- Comments on Midterm 1.
- The master method. Analysis of binary search and merge sort
[Slides 5-9 through 5-19]
- Lecture 17 - Wednesday, November 8:
- Recursive construction of a binary heap. Integer multiplication.
Matrix multiplication and Strassen's method, part 1.
[Slides 5-20 through 5-36]
- Friday, November 10: No lecture (Veteran's Day Holiday)
- Lecture 18 - Monday, November 13:
- Strassen's method, part 2.
[Slides 5-37 through 5-40]
- Dynamic Programming. Introduction, basic principles.
Optimal Weighted-interval scheduling
[Slides 6-1 through 6-13]
- Lecture 19 - Wednesday, November 15:
- Principles of dynamic programming.
Specifying a dynamic programming solution.
The Truck-loading problem.
[Slides 6-14 through 6-25]
- Lecture 20 - Friday, November 17:
- 0/1 Knapsack problem.
Optimal Matrix chain multiplication (part 1)
[Slides 6-26 through 6-36]
- Lecture 21 - Monday, November 20:
- Optimal Matrix chain multiplication (part 2).
Optimal binary tree (part 1).
[Slides 6-37 through 6-52]
- Lecture 22 - Wednesday, November 22:
- Optimal binary tree (part 1).
[Slide 6-53]
- Graph basics (part 1)
[Slides 7-1 through 7-12]
- Friday, November 24: No lecture (Thanksgiving Holiday)
- Lecture 23 - Monday, November 27:
- Graph basics (part 2).
[Slides 7-13 through 7-21]
- Directed Acyclic Graphs (DAGs),Topological sorting
[Slides 7-22 through 7-28]
- Lecture 24 - Wednesday, November 29:
- Reprise of topological sorting
- Discussion, questions about upcoming Midterm 2
- Friday, December 1: No lecture (Midterm 2)
Last modified: November 30, 2023