| Schedule and handouts
| Discussion board
| Related material]
This schedule is tentative.
|Jan 6||Administrivia, Introduction, Stable Matching||Chapter 1 in [KT], Chapter 12 here|
|Mergesort, Intro divide and conquer||I. Introduction (Week 1)||Sections 0.3, 2.1-2.3 in [DPV], Section 5.1 in [KT]%|
|Jan 13||Asymptotic analysis||II. Asymptotic Analysis (week 1)||Section 2.2, 2.5 in [DPV]
Sections 2.1-2.2, 5.1-5.3, 5.5 in [KT]
|Jan 15||More on divide and conquer||III. Divide & Conquer Algorithms (Week I) [Strassen's Subcubic Matrix Multiplication Method];||Counting inversions|
|Jan 20||Discussion of HW1|
|Jan 22||Graph search and connectivity||X. Graph Search and Connectivity (Week 4)||Chapter 3, 4.1-4.2 in [DPV]
Chapter 3 in [KT]
|Jan 27||Basic graph algorithms continued|
|Jan 29||Graph algorithms continued|
|Feb 3||Greedy algorithms||III. Introduction to Greedy Algorithms (Week 1) and IV. A Scheduling Application (Week 1)||Sections 4.1-4.4 in [KT]|
|Feb 5||Greedy continued||V. Prim's MST Algorithm (Week 1) and VI. Kruskal's MST Algorithm (Week 2)||Sections 4.5-4.7 in [KT], 5.1 in [DPV]|
|Feb 10||Minimum spanning tree algorithms, Application to Clustering||VII. Clustering (Week 2)|
|Feb 17||Huffman codes||IX. Huffman Codes (Week 2)||Section 5.2 in [DPV], 4.8 in [KT]|
|Feb 19||Dynamic programming I||X. Introduction to Dynamic Programming (Week 3)||Chapter 6 in [DPV], Section 6.1-6.2 in [KT]|
|Feb 24||Dynamic programming II||XI. The Knapsack Problem (Week 3) and XII. Sequence Alignment||Sections 6.4-6.6 in [KT]|
|Feb 26||Additional DP examples||Problems 6.2 and 6.7 in [DPV]|
|Mar 2||All Pairs Shortest Paths||XV. All-pairs shortest paths|
|Mar 4||Bellman Ford||XIV. The Bellman-Ford Algorithm (Week 4)||Sections 6.8-6.10 in [KT]|
|Mar 9||NP-completeness||XVI. NP-complete Problems (Week 5)||Chapter 8 in [DPV]|
|Mar 16||Final 8:30 - 10:20am
In PCAR 192
Instructor: Anna Karlin,
CSE 594, tel. 543 9344
Time: Wednesdays and Fridays in THO 125, 9:00-10:20am
Office hours: Thursdays, 9:00 -- 10:00am and by appointment -- send email.
|Teaching Assistants||Office hours|
|Kiana Ehsani||Tuesdays, 4:30 - 5:30pm, CSE 220||kianae@cs|
|Yang (Daniel) Li||Wednesdays, 4-5pm, CSE 218||dyli@cs|
|Robert Weber||Thursdays, 5-6pm, CSE 220||rtweber2@cs|
Course evaluation: homework (~45%), midterm/quizzes (~30%), final (~25%).
Prerequisite: CSE 373
Class mailing list
About this course:
We will study principles in the design of efficient algorithms: recursion, divide and conquer, greedy algorithms, dynamic programming etc. We will also explore computational intractability and NP-completeness.
This quarter I will be experimenting with flipping the classroom.