Coordinates  MWF, 1010:50am, GLSN 200 [Registrar] [Canvas] 
Instructor 
Liang Huang

TAs 
Mingbo Ma (lead)
Dezhong Deng 
Office hours  W/Th 56pm, KEC 2048 (Mingbo, grading questions welcome). Th 9:1010am, KEC 2069 (Liang, grading questions welcome). F 56pm, KEC 2048 (Dezhong, no grading questions allowed). 
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%, four quizzes: 5x4=20%; weekly homework: 3x10=30%, class participation: 5%. 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. 
Intended Audience 

Other Policies 
For questions, come to the office hours.
If you are unable to come, you can raise a question on Canvas. If you have a personal (nongrading) question, send it here which will reach the instructor and all TAs. Do not email us individually. For grading questions, please come to W/Th office hours. 
Week  Topics  Homework  Quiz/Exam 
1  (Wed) Admin Python Tutorial quicksort, BST (Fri) quickselect, mergesort, twopointers, stable sort  HW1 (qselect, qsort>bst)  
2  (Mon)
dividenconquer: number of inversions longest path in binary tree (Wed) brief discussions of HW1 k numbers closest to input query, unsorted and sorted (Fri) quiz1 and discussions x+y=z  HW2 (msort, inv, longest)  Fri: Quiz 1 (covers HW1) 
3  (Mon)
hand out graded quiz1 insertion sort can be made O(nlogn) by balanced BST discussions of HW2: qsort with randomized pivot can be made stable by 3way partition selection sort (inplace) is not stable generic way to stablize sort: decoratesortundecorate mergesort implementation: mergesorted(a[1:], b) makes it O(n^2) (this "beautiful" style only works for linkedlist or functional languages) (Wed) cont'd discussions of HW2 Python lazylists (yield) longest path implementation x+y=z (Fri) Priority Queue; heap; bubbleup/bubbledown  HW3 (kclosest, two pointers)  
4  (Mon)
heapify is O(n) Python heapq tutorial empirical difference b/w heapify and n heappushes (sorted array is bestcase (where heapify is slower); reversesorted is worstcase; use random list for avgcase) heapq bubbledown follows Knuth (vol.3) and different from textbooks (Wed) brief discussions of HW3 kway mergesort data stream (Fri) quiz2 and discussions  HW4 (priority queues; baby Dijkstra)  Fri: Quiz 2 (covers HWs13/quiz1) 
5  (Mon) Discussions of HW4 and Quiz2 (Wed) DP 101: Fibonacci and memoization (Fri) Maximum Independent Set memoization wrapper cache=None instead of cache={}  HW5 (DP I: memoized Fibonacci, # of BSTs, # of bistrings)  
6  (Mon) Help with HW5: backtracing, bitstrings, and BSTsipython %memit (sudo pip install memory_profiler; %load_ext memory_profiler )(Wed) Discussions of HW5 Knapsack: unbounded (Fri) Knapsack: 01  HW6 (DP II: knapsack, unbounded and bounded)  
7  (Mon) Discussions of HW6defaultdict (Wed) Review Problems Solutions (Fri) Midterm  (no HW; review problems I) Office Hours W/Th 46pm in KEC 2057  Midterm 11/4 (covers HWs16) 
8  (Mon) Discussions of Midterm solutions (Wed) LIS, TSP (Fri) Veteran's Day 11/11; NO CLASS  HW8 (DP III: LIS, TSP)  
9  (Mon) TSP; sparse vs. dense graphs (Wed) BFS topolsort; Viterbi (Fri) Discussions of HW8 DFS topolsort; Dijkstra  HW9 (BFSTopol/Viterbi/Dijkstra)  
10  (Mon) CKY: RNA structure (Wed) Discussions of HW9; kbest RNA structure (Fri) THANKSGIVING  Challenge problem (RNA structure)  
11  (Mon) Hints on RNA structures: total and kbest (Challenge problem due Tue) (Wed) Discussions of Challenge problem (Fri) Final Review Problems  (no HW; review problems II)  FINAL M 12/5 12pm1:50pm 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 details on analysis of complexity).