CS38 Introduction to Algorithms
Instructor |
|
| Name | Prof. Alexei Kitaev |
| kitaev@iqi.caltech.edu | |
| Phone | x8760 |
| Office | 280 Jorgensen |
| Hours | TBA |
Teaching Assistants |
|||
Kevin Ko |
William Hong | Ben Zax | |
| cko@caltech.edu | cwhong@caltech.edu | benzax@gmail.com | |
** Class schedule: Tuesday and Thursday 10:30am--11:55am, 106 Spalding Laboratory
** OFFICE HOURS: Wednesday 8-9pm and Thursday 9-11pm in the VLSI lab
Textbook
[CLRS] Introduction to Algorithms, 2nd Ed.
Cormen, Leiserson, Rivest, Stein
The MIT Press, 2001
Mailing Lists
Class mailing list: cs38@caltech.edu (visit this page to subscribe)
Instructor and TA mailing list: cs38-ta@caltech.edu
Handouts
| Assignment 1 | Due April 11 at 5pm | Kevin Ko | Solutions |
| Assignment 2 | Due April 18 at 5pm | Ben Zax | Solutions |
| Assignment 3 | Due April 25 at 5pm | William Hong | Solutions |
| Assignment 4 | Due May 2 at 5pm | Ben Zax | Solutions |
| Midterm | Due May 8 at 5pm | Solutions | |
| Assignment 5 | Due May 16 at 5pm | Kevin Ko | Solutions will appear here |
Lecture 1 [4/01/08]. Insertion sort. Algorithm analysis: correctness and running time. Asymptotic function growth. Computational models, the RAM model. Divide-and-conquer approach: Merge sort. (See CLRS Chapters 2, 3.)
Lecture 2 [04/03/08]. Lower bound for sorting by comparison. Solving recurrences. A variant of the master theorem. Multiplication of large integers: the Karatsuba algorithm. Strassen's algorithm for matrix multiplication. (See CLRS Theorem 8.1, Chapter 4, and Sec. 28.2; Knuth v.2, 4.3.3 (pp. 294--295).)
Lecture 3 [04/08/08]. Selection and median in worst-case linear time. Simple data structures: stack, queue. Binary heap, min-heap order, and associated subroutines: "sinking" and building the heap. Heapsort. (See CLRS 9.3, Chapter 10, 6.1--6.4.)
Lecture 4 [04/10/08]. Average-case complexity of the quicksort and selection with an arbitrary choice of pivot. Hash tables. (See CLRS Chapter 7, 9.2, 11.2--11.3.2.)
Lecture 5 [04/15/08]. Universal hashing. Binary search trees. Inserting and deleting nodes. Rotations. Height balanced (AVL) trees: height vs. size analysis. (See CLRS 11.3.3, 12.1--12.3, 13.2, Problem 13-3.)
Lecture 6 [04/17/08]. Balancing an AVL tree. Dynamic programing: the subset sum problem, knapsack, matrix-chain multiplication. Solving recurrences on a computer; memoization. (See CLRS 15.2--15.3.)
Lecture 7 [04/22/08]. Longest common subsequence. Greedy algorithms: fractional knapsack, activity selection, Huffman codes. (See CLRS 15.4, 16.1--16.3.)
Lecture 8 [04/24/08]. Graphs: definition, adjacency list representation. Shortest paths; breadth-first search. Depth-first search. The relation between DFS and memoization; topological sort. (See CLRS 22.1--22.4.)
Lecture 9 [04/29/08]. Depth-first search: parenthesis lemma, properties of the finishing times. Strongly connected components. Weighted single-source shortest paths: a dynamic programming solution and the Bellman-Ford algorithm. (See CLRS 22.3--22.5, 24.1.)
Lecture 10 [05/06/08]. Dijkstra's algorithm. The all-pairs shortest path problem; matrix multiplication method. (See CLRS 24.3, 25.1)
Lecture 11 [05/08/08]. The Floyd-Warshall and Johnson algorithms. Amortized analysis and potential function. Examples: dynamic tables, incrementing and decrementing a counter. (See CLRS 25.2, 25.3, Chapter 17.)
Problems? Questions? email cs38-ta@caltech.edu!