Coordinates  TR, 1011:20am, GLSN 200 [Registrar] [Canvas] 
Instructor 
Liang Huang

TAs  He Zhang (zhangh7@) and Yilin Yang (yangyil@) 
Office hours  Liang: T/Th, 11:2511:55am (KEC 2069); TAs: M/T/Th/F, 45pm (KEC Atrium). 
Textbooks  [CLRS] Introduction to Algorithms, 3rd or 2nd edi. (default reference).
[KT] Kleinberg and Tardos, Algorithm Design (DP chapter online, all slides online) [DPV] Dasgupta, Papadimitriou, and Vazirani (DPV). Algorithms (full text online via berkeley) [E] Jeff Erickson. Algorithms, Etc. (full text online) How to Think Like a Computer Scientist: Learning Python (full text online) 
Grading (tentative)  midterm: 20%, final: 25%, three quizzes: 7x3=21%; weekly homework: 3x10=30%, class participation: 4%. any complete HW submission automatically gets 2%. the other 1% is based on blackbox testing of the specified coding problem. no late submission is accepted. Grading Curve: A/A: 4045%, B+/B/B: 4550%, the rest is C+/C/C (very rare). 
Intended Audience 

Other Policies 
For technical questions, come to office hours.
Otherwise you can raise a question on Canvas. (answering other people's questions correctly will be rewarded for class participation). For grading questions, come to office hours. Do not email us unless you have a personal issue. 
Week  Topics  Homework  Quiz/Exam 
1  (Tue) Admin Python Tutorial (first 5 pages) quicksort, BST, quickselect (Thu) mergesort, twopointers, stable sort  HW1 (qselect, qsort>bst)  
2  (Tue)
dividenconquer: number of inversions longest path in binary tree brief discussions of HW1 (Thu) k numbers closest to input query, unsorted quiz1 and discussions  HW2 (msort, inv, longest)  Thu: Quiz 1 (covers HW1) 
3  (Tue)
hand out graded quiz1 insertion sort can be made O(nlogn) by balanced BST discussions of HW2: qsort with randomized pivot made stable by 3way partition selection sort (inplace) is not stable generic way to stablize sort: decoratesortundecorate mergesort implementation: mergesorted(a[1:], b) is O(n^2) k numbers closest to input query, unsorted x+y=z (Thu) Priority Queue; heap; bubbleup/bubbledown  HW3 (kclosest, two pointers)  
4  (Tue)
brief discussions of HW3 heapify is O(n) Python heapq tutorial heapq bubbledown follows Knuth (vol.3) and different from textbooks kway mergesort data stream (Thu) quiz2 and discussions  HW4 (priority queues; baby Dijkstra)  Thu: Quiz 2 (covers HWs13/quiz1) 
5  (Tue) handout Quiz2 DP 101: Fibonacci, memoization, bitstrings, max. indep. set [slides] (Thu) discussions of HW4 cache=None instead of cache={}  HW5 (DP I: memoized Fibonacci, # of BSTs, # of bistrings)  
6  (Tue) Knapsack: unbounded and 01 (Thu) Knapsack: bounded Discussions for HW5  HW6 (DP II: knapsack, unbounded and bounded)  
7  (Tue) Midterm Review Solutions Discussions of HW6 (Thu) Midterm  
8  (Tue) Discussions of Midterm solutions topological sort (BFSstyle) sparse and dense graphs (Thu) Viterbi; Dijkstra  HW8 (DP III: LIS, Topol, Viterbi)  
9  (Tue) Discussions of HW9; TSP (EdmondsKarp) (Thu) TSP cont'd.; CKY: RNA structure  HW9 (Dijkstra, TSP)  
10  (Tue) Discussions of HW9 counting RNA structures; kbest RNA structure (Thu) review problems  HW10: Challenge (RNA structure)  
11  FINAL Thu 3/22 6pm same room 
To prepare for coding interviews, you have to practice on some of the above (say, solving at least 20 problems on codeforces, with at least two from each topic). To prepare for ACM/ICPC, you have to practice a lot (solving at least 100 problems on zoj/poj).
For another MS/MEnglevel algorithms class I taught before (at USC), see here (with lots of complexity analysis).