BU CAS CS 330: Introduction to Analysis of Algorithms

Spring 1997

Schedule

97.01.14

Problems, instances of problems, algorithms to solve problems, efficiency of algorithms, average and worst-case analyses (Sections 1.1, 1.2, 1.3, 2.1, 2.2, 2.3, 2.4). Example: Multiplication, 2 algorithms ("standard" and "a la russe"). Example: Sorting, 2 algorithms ("insertion sort" and "selection sort").

97.01.16

Estimating the running time of an algorithm (Sections 2.5, 4.2). Iterative and recursive algorithms to compute Fibonacci numbers (Subsection 2.7.5, Section 4.2). Rates of growth (Section 2.6). "Big Oh" notation (Section 3.2 -- omit the proofs of the different rules: threshold rule, maximum rule, limit rule).

97.01.21

Sequential (or linear) search, binary search, their run times, iterative and recursive implementations of binary search (Section 7.3, Subsection 4.2.4). Complete and essentially complete binary trees (bottom half of page 162 and top half of page 163). Big Omega and big Theta (Section 3.3). Conditional asymptotic notation (Section 3.4 -- omit proof of smoothness rule).

97.01.23

Divide-and-conquer algorithms for multiplication (pages 4-5, Subsection 2.7.3, Section 7.1). Methods for solving recurrence relations (Subsection 4.7.1, Example 4.7.10 on pages 130-131).

97.01.28

Reading: Graphs and trees, and their representations in memory (Sections 5.4, 5.5). Heaps and operations on heaps (Section 5.7).

97.01.30

Analysis of make-heap (Theorem 5.7.1). Heapsort and its analysis (Theorem 5.7.2). Binomial trees, binomial heaps (first 4 pages of Section 5.8).

97.02.04

Finish binomial heaps and the analysis of operations on binomial heaps (Section 5.8). Amortized analysis (Section 4.6).

97.02.06

Recapitulate amortized analysis of inserting an item into a binomial heap (Section 5.8). Begin greedy algorithms. Making change (Section 6.1). Reading: Characteristics of greedy algorithms (Section 6.2). Minimum spanning trees: Kruskal's and Prim's algorithms (Section 6.3).

97.02.11

Disjoint set structures (Section 5.9). Minimum spanning trees (Lemma 6.3.1, page 192).

97.02.13

Implementation of Kruskal's algorithm, based on disjoint set structures, and its run-time analysis (Section 6.3). Reading: Implementation of Prim's algorithm and its run-time analysis (Section 6.3). Dynamic programming: Calculating binomial coefficients (Subsection 8.1.1), making change (Section 8.2). Reading: The principle of optimality (Section 8.3). Greedy algorithms: Fractional knapsack problem (Section 6.5).

97.02.25

Dynamic programming: 0-1 knapsack problem (Section 8.4). Greedy algorithms: Begin Dijkstra's algorithm for finding "single-source shortest-paths" in a weighted directed graph (Section 6.4).

97.02.27

Greedy algorithms: Complete Dijkstra's algorithm (Section 6.4). Dynamic programming: Floyd's algorithm for "all-pairs shortest-paths" in a weighted directed graph (Section 8.5) Dynamic programming: Begin algorithm for optimal "chain matrix multiplication" (Section 8.6).

97.03.04

Chained matrix multiplication completed (Section 8.6). Divide-and-conquer: Begin mergesort (Subsection 7.4.1).

97.03.06

Divide-and-conquer: Mergesort completed (Subsection 7.4.1). General template for divide-and-conquer algorithms, recurrence relations (Section 7.2). Start quicksort (Subsection 7.4.2).

97.03.18

Divide-and-conquer: Complete quicksort (Subsection 7.4.2), go easy with the proof of Theorem 7.4.1. Matrix multiplication (Section 7.6). Start exponentiation (Section 7.7).

97.03.20

Divide-and-conquer: Complete exponentiation (Section 7.7). Start exploring graphs (Chapter 9): Graphs and games (Section 9.1), traversing trees (Section 9.2).

97.03.25

Complete traversing trees (Section 9.2). Depth-first search on undirected graphs and applications (Section 9.3). Depth-first search on directed graphs and applications (Section 9.4).

97.03.27

Breadth-first search on trees, undirected graphs, directed graphs (Section 9.5). Backtracking, the knapsack problem (Subsection 9.6.1).

97.04.08

Backtracking, the knapsack problem (Subsection 9.6.1), the general template (Subsection 9.6.3). Branch-and-bound, the assignment problem (Subsection 9.7.1).

97.04.10

Branch-and-bound, the knapsack problem (Subsection 9.7.2). Start parallel algorithms (Section 11.1). Computing with a complete binary tree (Subsection 11.2.1), pointer doubling (Subsection 11.2.2).

97.04.15

Parallel algorithms. Complete pointer doubling (Subsection 11.2.2). Work efficiency (Section 11.3). Shortest paths using parallel algorithms (Subsection 11.4.1).

97.04.17

Parallel algorithms: Complete shortest paths algorithm (Subsection 11.4.1). Computational complexity: Lower bounds using information-theoretic arguments (Section 12.1) and adversary arguments (Section 12.3 to the end of subsection 12.3.1).

97.04.22

Computational complexity: The classes P and NP (Section 12.5 to the end of subsection 12.5.1). Alternative definition of NP in terms of "nondeterministic polynomial-time algorithms" (Subsection 12.5.6).

97.04.24

Heuristic and approximate algorithms. Heuristics (Section 13.1). Approximate algorithms for the travelling salesperson problem (Subsection 13.2.1).

97.04.29

Heuristic and approximate algorithms. Approximate algorithms for the knapsack problem and the bin packing problem (Subsections 13.2.2 and 13.2.3).

Assaf Kfoury

Created:  97.01.08

Modified: 97.04.29