Coordinates  T/Th, 1011:20am, KEC 1001 [Registrar] [Canvas] [Teams] 
Instructor 
Liang Huang (huanlian@)

TA  Sizhen Li (lisiz@) 
Office Hours  Instructor: T/Th, 11:25am11:50am (KEC 2069) TA: M/F 45pm (KEC Atrium). Extra office hours available before exams. 
Textbooks  [CLRS] Introduction to Algorithms, 4th/3rd/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: 25%; Final: 25%; Quizzes: 8+10=18%; homework: 3x8%+6%=30%. background survey: 2%. For each HW, any complete submission automatically gets 2%. The other 1% is based on blackbox testing of the specified coding problem. Coding must be done in Python 3. Just finishing the background survey in week1 will get the 2%. no late submission is accepted.

Prerequisites  Students are assumed to be familiar with Data Structures (CS 261) and fluent in at least one mainstream language (C/C++, Java, Python). We'll start with a brief review of Data Structures integrated with a Python tutorial. 
Zoom/Recording  Each lecture is recorded and will be uploaded to Canvas the next day. But we do not offer live zoom unless it's a COVID or travel situation. Email the TA for zoom link requests. 
Other Policies 
Canvas is for announcements (you'll receive an email for each announcement I made on Canvas)
and checking grades,
and Teams is for discussions (we used to use Slack, but the University dropped Slack support).
For technical questions, come to office hours.
Otherwise you can raise a question on Teams. 
Week  Topics/Readings  Homework  Quiz/Exam 
1 9/22  (Thu) Admin Python Tutorial (first 5 pages required, others recommended) quicksort, BST, quickselect  HW1 (qselect, qsort>bst)  
2 9/27,29  (Tue) brief discussions of HW1 dividenconquer: quicksort vs. mergesort vs. quickselect vs. binary search master equation merging two sorted lists via twopointers multitasking recursion: # of inversions and longest path in binary tree stable sort; motivations: sorting with multiple keys mergesort and nonrandomized quicksort are stable, but randomized quicksort is not
(Thu)  HW2 (msort, inv, longest)  Thu: Quiz 1 (covers HW1) 
3 10/4,6  (Tue) brief discussion on Quiz1 (10 min). brief discussion on HW2 (10 min). mergesort implementation: mergesorted(a[1:], b) is \(O(n^2)\)Priority Queue (emergency room) slow implementations: sorted list, reversely sorted list, sorted linkedlist fast implementation: binary heap complete binary tree (also balanced); array representation. heap: bubbleup and bubbledown. hand out graded quiz1
(Thu)  HW3 (kclosest, two pointers)  
4 10/11,13  (Tue)
brief discussions of HW3 x+y=query: \(O(n^2) \Rightarrow O(n\log n)\) x+y=z: \(O(n^3) \Rightarrow O(n^2 \log n) \Rightarrow O(n^2)\) heapq bubbledown follows Knuth (vol.3) and different from textbooks (Thu) kbest from crossproduct (baby Dijkstra). data stream quiz2 and discussions  HW4 (priority queues; baby Dijkstra)  Thu: Quiz 2 (covers HWs13/quiz1) 
5 10/18,20  (Tue) discussions of HW4 DP 101: Fibonacci, memoization, bitstrings, max. indep. set [slides] handout graded Quiz2 (Thu) DP: backtracing the optimal solution DP: LIS DP: unbounded knapsack  HW5 (DP I: memoized Fibonacci, # of BSTs, # of bistrings)  
6 10/25,27  (Tue) DP: 01 and bounded knapsack KT slides (pp. 3037) (Thu) Discussions for HW5 Midterm Review problems [solutions]  HW6 (DP II: knapsack, unbounded and bounded)  
7 11/1,3  (Tue) Discussions of HW6 Q/A session (Thu) Midterm  Thu: Midterm  
8 11/8,10  (Tue) Discussions of Midterm solutions graphs: intro topological sort (BFSstyle) handout graded midterms (Thu) inclass coding session: topol sort: stack and queue Viterbi Dijkstra intro  HW8 (Topol, Viterbi)  
9 11/15,17  (Tue) Dijkstra: decreasekey; hashed heap (heapdict) KT slides demo HW8 solutions (Thu) CKY: RNA structure KT slides  HW9 (Dijkstra; TSP)  
10 11/22,24  (Tue) counting and kbest RNA (Thu) Thanksgiving  HW10 (RNA structure)  
11 11/29;12/1  (Tue)
hypergraphs and generalized Viterbi kbest Viterbi kbest generalized Viterbi (RNA) DP summary slides (Thu) Final review problems and solutions  optional HW11 (edit distance, just for practice)  
12 
FINAL EXAM Thu 12/8 9:30am11:20am same room, closed book, closed notes 
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).