Topics Covered by Lecture

Topics covered by lecture

• 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.
• Lecture 12 - Tuesday, May 12: [Slides 5-20 through 5-40]
  • Recursive construction of a binary heap. Integer multiplication. Matrix multiplication and Strassen's method
• Lecture 13 - Thursday, May 14: [Slides 6-1 through 6-21]
  • Dynamic Programming: Basic principles. Optimal Weighted-interval scheduling. Principles of dynamic programming. Specifying a dynamic programming solution. The truck-loading problem, part 1
• Lecture 14 - Tuesday, May 19: [Slides 6-22 through 6-30]
  • The truck-loading problem, part 2
  • The 0/1 knapsack problem
  • Midterm 2 coverage is up through and including slide 6-30.
  • Discussion, questions about upcoming Midterm 2
• Thursday, May 21: No lecture (Midterm 2)
• Lecture 15 - Tuesday, May 26: [Slides 6-31 through 6-46]
  • Optimal matrix chain multiplication.
  • Optimal binary search trees, part 1.
• Lecture 16 - Thursday, May 28: [Slides 6-47 through 6-53, Slides 7-1 through 7-13]
  • Optimal binary search trees, part 2.
  • Graph basics. Undirected/directed graphs. Definitions of basic terms associated with graphs and digraphs. Formulae for sums of degrees, indegrees, outdegrees. Paths. Cycles. Subgraphs.
• Lecture 17 - Tuesday, June 2: [Slides 7-14 through 7-21, Slides 8-1 through 8-10]
  • Graph basics, continued. Undirected/directed graphs. Connected graphs. Connected components. Trees Representation of graphs: Edge list, Adjacency matrix, adjacency list.
  • Weighted graphs. Shortest paths: definition and formulation of problem. Dijkstra's algorithm (part 1).
• Lecture 18 - Thursday, June 4: [Slides 8-11 through 8-31]
  • Dijkstra's algorthm (part 2). Minimum spanning trees: Definition and formulation of the problem. Prim-Jarnik algorithm. Kruskal's algorithm, cluster management.