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. Grading Curve: A/A: [90,100]; B+/B/B: [60,90); C: [50,60); F: [0,50). 
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 discussions of HW2. mergesort implementation: mergesorted(a[1:], b) is \(O(n^2)\)k numbers closest to input query, unsorted k numbers closest to input query, sorted; hand out graded quiz1
(Thu)  HW3 (kclosest, two pointers)  
4 10/11,13  (Tue)
brief discussions of HW3 heapify is \(O(n)\) Python heapq tutorial heapq bubbledown follows Knuth (vol.3) and different from textbooks kway mergesort (Thu) data stream quiz2 and discussions  HW4 (priority queues; baby Dijkstra)  Thu: Quiz 2 (covers HWs13/quiz1) 
5 10/18,20  (Tue) handout Quiz2 discussions of HW4 heapify is O(n) (Thu) DP 101: Fibonacci, memoization, bitstrings, max. indep. set [slides]  HW5 (DP I: memoized Fibonacci, # of BSTs, # of bistrings)  
6 10/25,27  (Tue) Knapsack: unbounded and 01 KT slides (pp. 3037) (Thu) Knapsack: bounded 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; redo one midterm question)  
10 11/22,24  (Tue) counting and kbest RNA (Thu) Thanksgiving  HW10 (RNA structure)  
11 11/29;12/1  (Tue)
inclass coding session: kbest RNA (Thu) Review problems updated solutions  optional hw11 (editdistance)  
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).