CompSci 161 - Design and Analysis of Algorithms - Winter, 2025 (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.
It will be filled in as the quarter progresses.
- Lecture 1 - Monday, January 6:
- Overview of the course
- Introduction, Basics of Algorithm Analysis [Slides 1-1 through 1-14]
- Lecture 2 - Wednesday, January 8:
- Asymptotic notation
[Slides 1-15 through 1-31]
- Lecture 3 - Friday, January 10:
- Sums and summations;
Logarithms and Exponents;
Floors and Ceilings;
Factorials and combinations;
Harmonic numbers.
Proofs / Proof by Induction.
[Slides 1-32 through 1-51]
- Lecture 4 - Monday, January 13
:
- Basic Probability,
[Slides 1-52 through 1-64]
- Lecture 5 - Wednesday, January 15:
- Review of basic data structures:
arrays, linked lists, stacks, queues, hash tables, binary trees.
Binary search part 1:
algorithm, correctness, analysis of running time.
[Slides 2-1 through 2-17]
- Lecture 6 - Friday, January 17:
- Binary search part 2: proof of optimality using decision trees.
Sorting, basic terminology (permutations, inversions).
Comparison-based sorting.
Insertion sort.
Selection sort. Quicksort, part 1
[Slides 2-18 through 2-36]
- Monday, January 20: No lecture (University Holiday)
- Lecture 7 - Wednesday, January 22:
- Quicksort, part 2.
Mergesort.
[Slides 2-37 through 2-50]
- Lecture 8 - Friday, January 24:
- Applications of merge sort: line intersections, inversion counting
[Slides 2-51 through 2-60]
- Priority queues.
Binary heaps: basic properties, sift-up, sift-down, insertion.
[Slides 3-1 through 3-11]
- Lecture 9 - Monday, January 27:
- Binary heaps: deletion, construction (heapify).
Heap sort.
Summary of comparison-based sorts.
Stable sorting.
[Slides 3-12 through 3-32]
- Lecture 10 - Wednesday, January 29:
- Lower bounds on comparison-based sorting / decision tree argument.
- Optimally sorting 5 elements.
Address calculation sorting: overview.
[Slides 3-33 through 3-41]
- Discussion, questions about upcoming Midterm 1
- Friday, January 31: No lecture (Midterm 1)
- Lecture 11 - Monday, February 3:
- Bucket sort. Radix Sort
[Slides 3-46 through 3-53]
- Lecture 12 - Wednesday, February 5:
- Counting sort [Slides 3-42 through 3-45]
- Greedy algorithms Overview.
Fractional knapsack problem.
Slides 4-1 through 4-6]
NOTE:
I did not cover external sorting (slides 3-54 through 3-64) in class,
but I will expect you to know it for midterm 2 and the final exam.
It is covered in the "Prerecorded lectures from previous quarters"
in Minilectures 035 and 036. You can find a link to the prerecorded
lectures on the class canvas page.
- Lecture 13 - Friday, February 7:
-
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 14 - Monday, February 10:
- Divide and conquer. The divide-and-conquer recurrence equation.
Solving a divide-and-conquer recurrence equation using the
Simplified method.
The master method, part 1.
[Slides 5-1 through 5-14]
- Lecture 15 - Wednesday, February 12:
-
The master method, part 2.
Analysis of binary search and merge sort.
Recursive construction of a binary heap.
Integer multiplication.
Matrix multiplication and Strassen's method, part 1.
[Slides 5-15 through 5-31]
- Lecture 16 - Friday, February 14:
-
Matrix multiplication and Strassen's method, part 2.
[Slides 5-32 through 5-40]
-
Dynamic Programming: Introduction. Basic principles, part 1.
[Slides 6-1 through 6-2]
- Monday, February 17: No lecture (University Holiday)
- Lecture 17 - Wednesday, February 19:
-
Dynamic Programming: Basic principles, part 2.
Optimal Weighted-interval scheduling.
Principles of dynamic programming.
[Slides 6-3 through 6-14]
- Lecture 18 - Friday, February 21:
-
Specifying a dynamic programming solution.
The Truck-loading problem.
0/1 Knapsack problem.
[Slides 6-15 through 6-30]
- Lecture 19 - Monday, February 24:
-
Optimal Matrix chain multiplication.
[Slides 6-31 through 6-38]
- Lecture 20 - Wednesday, February 26:
-
Optimal binary trees, part 1
[Slides 6-39 through 6-44]
- Discussion, questions about upcoming Midterm 2
- Friday, February 28: No lecture (Midterm 2)
- Lecture 21 - Monday, March 3:
-
Optimal binary trees, part 2
[Slides 6-45 through 6-53]
- Lecture 22 - Wednesday, March 5:
- Graph basics.
Undirected/directed graphs.
Definitions of basic terms associated with graphs and digraphs.
Formulae for sums of degrees, indegrees, outdegrees.
Paths. cyclces. Subgraphs.
[Slides 7-1 through 7-13]
- Lecture 23 - Friday, March 7:
-
Connected graphs.
Connected components.
Trees
Representation of graphs:
Edge list, Adjacency matrix, adjacency list.
[Slides 6-45 through 6-53]
-
Directed Acyclic Graphs (DAGs),Topological sorting
[Slides 7-43 through 7-49]
- Lecture 24 - Monday, March 10:
- Weighted graphs.
Shortest paths: definition and formulation of problem.
Dijkstra's algorthm (part 1).
[Slides 8-1 through 8-10]
Last modified: March 10, 2025