Topics Covered by Lecture
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 - Tuesday, March 31:
[Slides 1-1 through 1-19]
- Overview of the course
- Introduction. Basics of Algorithm Analysis. Asymptotic notation, part 1.
- Lecture 2 - Thursday, April 2:
[Slides 1-20 through 1-44]
- Asymptotic notation, part 2. Sums, summations. Basic functions: logarithms, floors and ceilings, factorials, combinations. Harmonic numbers, part 1.
- Lecture 3 - Tuesday, April 7:
[Slides 1-45 through 1-64]
- Harmonic numbers, part 2. Proofs / Proof by Induction. Basic Probability.
- Lecture 4 - Thursday, April 9:
[Slides 2-1 through 2-25]
- Review of basic data structures: arrays, linked lists, stacks, queues, hash tables, binary trees. Binary search: algorithm, correctness, analysis of running time, proof of optimality using decision trees. Sorting, basic terminology (permutations, inversions). Comparison-based sorting. Insertion sort, part 1.
- Lecture 5 - Tuesday, April 14:
[Slides 2-26 through 2-46]
- Insertion sort, part 2. Selection sort. Quick sort.
- Lecture 6 - Thursday, April 16:
[Slides 2-47 through 2-60, Slides 3-1 through 3-5]
- Suggestions on how to prepare for Midterm 1
- Merge sort. Applications of merge sort: line intersections, inversion counting.
- Priority queues. Binary heaps, part 1: basic properties.
- Lecture 7 - Tuesday, April 21:
[Slides 3-6 through 3-23, but see list below for midterm 1 coverage]
- Binary heaps, part 2: sift-up, sift-down, insertion, deletion, extract-max.
- Midterm 1 coverage is up through and including slide 3-13.
- Binary heaps, part 3: heap construction (heapify)
- Discussion, questions about upcoming Midterm 1
- Thursday, April 23: No lecture (Midterm 1)
- Lecture 8 - Tuesday, April 28:
[Slides 3-24 through 3-47]
- Heap sort. Summary of comparison-based sorts. Stable sorting. Lower bounds on comparison-based sorting / decision tree argument. Optimally sorting 5 elements. Address calculation sorting. Counting sort. Bucket sort, part 1.
- Lecture 9 - Thursday, April 30:
[Slides 3-48 through 3-64, Slides 4-1 through 4-3]
- Bucket sort, part 2. Radix sort. External sorting: polyphase merge, replacement selection
- Greedy algorithms introduction. Fractional knapsack problem, part 1.
- Lecture 10 - Tuesday, May 5:
[Slides 4-4 through 4-19]
- Fractional knapsack problem, part 2. 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.
- Lecture 11 - Thursday, May 7:
[Slides 5-1 through 5-19]
- Divide and conquer. The divide-and-conquer recurrence equation. The Simplified method. The Master Method. Analysis of binary search and merge sort.
Last modified: May 7, 2026