| Coordinates | W/F, 10-11:20am, Johnson 102 [Registrar] [Canvas] [Ed Discussion] |
| Instructor |
Liang Huang (huanlian@)
|
| TAs |
Graduate TA: Apoorv Malik (malikap@) Graduate TA: Tianshuo Zhou (zhoutian@) Undergrad TA: Otso Barron (barrono@) |
| Office Hours | Instructor: W/F 11:30-11:55am (KEC 2069) TAs: M 4:30-6pm (KEC 2057), T 4-5:30pm (3057), F 5-6pm (2057). Extra office hours available before exams. |
| Textbooks |
[H] My Course Notes (default reference).
[CLRS] Introduction to Algorithms, 4th/3rd/2nd edi. (2nd reference). [KT] Kleinberg and Tardos, Algorithm Design (DP chapter online, all slides online) [R] Roughgarden, Algorithms Illuminated (videos and 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 (week 7): 26+1.5%, Final: 25+1.5%, Quizzes (weeks 2 & 5): 6+1+10+1=16+2%. Weekly homework (1-3, 5-6, 7, 8-9, 10): 3%\(\times\)7+1%+6%=27%+1%. background survey: 2%. picking up graded papers: 2%; post-midterm survey: 2%. Total extra credit: 6%. For HW1-9, 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. HW is due every Tuesday 11:59pm. No late submission is accepted. Grading Curve: (>90 OR top 25%): A/A-; (<70 AND bottom 25%): C+ or lower; others: B+/B/B-. (i.e., at least 1/4 will get A/A- and at most 1/4 will get C+ or lower). |
| 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. |
| Other Policies |
Canvas is for announcements (you'll receive an email for each announcement I made on Canvas)
and checking grades,
and Ed Discussion is for discussions.
For technical questions, please come to office hours.
Or you can post a question on Ed Discussion, but please check if the same question has been asked by other students before posting. |
| Week | Topics | Homework | Quiz/Exam |
| 1 | (Wed) Admin Python Tutorial (first 5 pages) quicksort: in-place vs. out-of-place quicksort analyses: best-case \(O(n \log n)\); worst-case \(O(n^2)\) divide-conquer-combine array concatenation is \(O(n)\) in \(n!\) permutations, \(2^{n-1}\) are worst-case brief review of mergesort
(Fri)
quicksort <-> BST (buggy qsort) | HW1 (qselect, qsort->bst) | |
| 2 | (Wed)
discussions of HW1 number of inversions using mergesort; recursion with byproduct | HW2 (msort, inversions, longest) | Fri: Quiz 1 (covers HW1) |
| 3 | priority queue, lowerbound, datastream slides for nbest | HW3 (priority queue) | |
| 4 | review; HW2/HW3 solutions; quiz prep | no HW4 | |
| 5 | dynamic programming (DP): basics [slides] | HW5 (DP: part 1) | Wed: Quiz 2 (covers HWs 1-3) |
| 6 | dynamic programming (DP): knapsacks [KT slides] | HW6 (DP: part 2) | |
| 7 | midterm review problems [solutions] | optional HW7 | Fri: Midterm |
| 8-9 | graph algorithms and their connections to DP;
Topological sort Viterbi algorithm Dijkstra algorithm | HW8-HW9 (graphs) | |
| 10 | challenge problem and final review full DP slides Final Review Questions and Solutions | HW10 (RNA: connecting all topics) | |
| 11 |
FINAL Tue 6/11 at 6pm
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).
