CSE 207N: Algorithms
Semester starting from February 26, 2011
Course Teachers & Contacts Books Syllabus Announcement
Dr. Masud Hasan
Office: CSE 117
Phone: PABX 8614640-44, 816833-38, 8618344-49, Ext. 6113
Email: mhasan2010 AT gmail DOT com
1. Introduction to Algorithms, by Cormen, Leiserson, Rivest, Stein, 3rd edition [collect this book].
2. Other materials/books will be mentioned/supplied as necessary.
Syllabus (will gradually grow):
[Relevant exercises are by default included]
[Preamble of all chapters are by default included]
Ch 1: The Role of Algorithms in Computing
Self study.
Ch 2: Getting Started
Self study.
Ch 3: Growth of Functions
Preamble
3.1: Asymptotic notations
3.2: Standard notations and common functions (self study)
Ch 4: Divide and Conquer
Preamble
4.2: Strassens’s algorithm
4.4: Recursion tree
4.5: Master method
Ch 7: Quicksort
Full (except 7.4.1)
Ch 8: Sorting in Linear Time
Preamble
8.1: Lower bound on sorting
Lecture audio for Ch 3 to 8 (some audios are incomplete due to technical failure):
Section A: [lec-1] [lec-2] [lec-3] [lec-4.1] [lec4.2] [lec-5]
Section B: [lec-1] [lec-2] [lec-3] [lec-4] [lec-5]
Sample questions for Ch 3 to 8. [pdf]
Ch 15: Dynamic Programming
15.2: Matrix-chain multiplication
15.3: Elements of dynamic programming
15.4: LCS
Lecture Audio: [lec-6-sec-A] [lec-6-sec-B] [lec-7] [lec-8]
Sample questions [pdf]
Ch 16: Greedy Algorithms
16.1: Activity-selection problem
16.2: Elements of greedy algorithms
16.3: Huffman coding
Lecture Audio: [Greedy-1] [Greedy-2] [Greedy-3]
Sample questions [pdf]
Supplementary note on optimal sub-structure property for
DP and greedy algorithms [pdf]
Ch 21: Data Structures for Disjoint Sets
21.1: Disjoint set operations
21.2: Linked-list representation
21.3: Disjoint-set forest
Lecture Audio: [Disjoint_set-1] [Disjoint_set-1]
Sample questions [pdf]
Ch 22: Elementary Graph Algorithms
No proofs for this chapter
22.1: Graph representation (self study)
22.2: BFS
22.3: DFS
22.4: Topological sort
22.5: Strongly connected components
Lecture Audio: [graph-1] [graph-2-MST-1]
Sample questions [pdf]
Ch 23: Minimum Spanning Trees
23.1: Growing MST
23.2: Prim’s and Krushkal’s algorithms
Lecture Audio: [graph-2-MST-1] [MST-2]
Sample questions [pdf]
Ch 24: Single-Source Shortest Paths
Preamble
24.1: Bellman-Ford Algorithm (up to page 652)
24.3: Dijkstra’s Algorithm (up to page 659)
24.5: Proofs of shortest path properties (ideas only)
Lecture Audio: [Shortest path-1] [Shortest path-2]
Sample questions [pdf]
Ch 25: All-Pairs Shortest Paths
25.1: All pair shortest paths and matrix multiplication
25.2: Floyed-Warshall algorithm
Lecture Audio: [APSP-1] [APSP-2] [APSP-3-Sec-A] [APSP-2-Sec-B]
Sample questions [pdf]
Ch 26: Maximum Flow (follow class note)
26.1: Flow network
26.2: Ford-Fulkerson method (without proofs for lemmas and corollaries)
26.3: Maximum bipartite matching (up to page 734)
Lecture Audio: [Flow-1] [Flow-2]
Sample questions [pdf]
Ch 29: Linear Programming
29.1, 29.2, 29.3, 29.4
Ch 32: String Matching
32.1, 32.2
Ch 34: NP-Completeness
Important: follow the lectures
Preamble
34.1: Polynomial time (up to page 1054)
34.2: Polynomial-time verification
34.3: NP-completeness and Reducibility (up to page 1072, except Lemma 34.3)
34.5: NP-complete Problems (34.5.1, 35.5.2, 35.5.4)
Class note
Lecture Audio: [NP-1] [NP-2] [NP-3]
Sample questions [pdf]
Ch 35: Approximation Algorithms
Preamble
35.1: Approximation algorithm for Vertex Cover problem
35.2: Approximation algorithm for TSP (up to 35.2.1)
Lecture Audio: [Approx-1] [Approx-2]
Sample questions [pdf]
Ch 9.1 of Das Gupta: Back-tracking and Branch and Bound, Pages 283-189 [pdf]
9.1.1: Back-tracking
9.1.2: Branch and Bound
Lecture Audio: [Branch]
Sample questions [pdf]
Ch 27: Multithreaded Algorithms:
Preamble
27.1: The basics of dynamic multithreading (except “scheduling”)
27.2: Multithreaded matrix multiplication
Lecture Audio: [Multi-thread-1] [Multi-thread-2]
Sample questions [pdf]
Ch 30: Polynomials and FFT
Preamble
30.1: Representing polynomials
30: DFT and FFT
Lecture Audio: [FFT-1] [FFT-2]
Sample questions [pdf]
- [CT marks]
- Class test 1: Class Test 1, 15-3-2011, Tuesday. Syllabus: Ch 3, 4, 7, 8; See detail above. [CT1 answer]
- Class test 2: Class Test 2, 12-4-2011, Tuesday. Syllabus: Ch 15, 16, 21; See detail above. [CT2 answer]
- Class test 3: Class Test 3, 10-5-2011, Tuesday. Syllabus: Ch 24, 25; See detail above.
- Class test 4: Class Test 4, 28-5-2011, Saturday. 10:45 (Section-B), 12:00 noon (Section A), Syllabus: Ch 34, 35, See detail above, Open Book. [CT4 Section A Answer] [CT4 Section B Answer]
- Class test 5 (bonus) (only if class is not cancelled due to hortal or any other emergency): 8/6/2011, Wednesday, in class, open book. Syllabus: Backtracking, Branch and Bound, Multithreaded algorithms; see detail above.