|Coordinates||T/Th, 10-11:20am, KEC 1001 [Registrar] [Canvas] [Teams]|
Liang Huang (huanlian@)
|TA||Sizhen Li (lisiz@)|
|Office Hours||Instructor: T/Th, 11:25am-11:50am (KEC 2069)|
TA: M/F 4-5pm (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.|
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.
Python Tutorial (first 5 pages required, others recommended)
quicksort, BST, quickselect
brief discussions of HW1
divide-n-conquer: quicksort vs. mergesort vs. quickselect vs. binary search
merging two sorted lists via two-pointers
multitasking recursion: # of inversions and longest path in binary tree
stable sort; motivations: sorting with multiple keys
mergesort and non-randomized quicksort are stable, but randomized quicksort is not
(msort, inv, longest)
|Thu: Quiz 1|
brief discussions of HW2.
k numbers closest to input query, unsorted
k numbers closest to input query, sorted;
hand out graded quiz1
(k-closest, two pointers)
brief discussions of HW3|
heapify is \(O(n)\)
Python heapq tutorial
heapq bubble-down follows Knuth (vol.3) and different from textbooks
(Thu) data stream
quiz2 and discussions
(priority queues; baby Dijkstra)
|Thu: Quiz 2|
|(Tue) handout Quiz2|
discussions of HW4
heapify is O(n)
(Thu) DP 101: Fibonacci, memoization, bitstrings, max. indep. set [slides]
(DP I: memoized Fibonacci, # of BSTs, # of bistrings)
|(Tue) Knapsack: unbounded and 0-1|
KT slides (pp. 30-37)
(Thu) Knapsack: bounded
Discussions for HW5
Midterm Review problems [solutions]
(DP II: knapsack, unbounded and bounded)
|(Tue) Discussions of HW6|
|(Tue) Discussions of Midterm solutions|
topological sort (BFS-style)
handout graded midterms
(Thu) in-class coding session: topol sort: stack and queue
|(Tue) Dijkstra: decrease-key; hashed heap (heapdict)|
KT slides demo
(Thu) CKY: RNA structure
(Dijkstra; redo one midterm question)
|(Tue) counting and k-best RNA|
|HW10 (RNA structure)
in-class coding session: k-best RNA|
(Thu) Review problems updated solutions
|optional hw11 (edit-distance)
FINAL EXAM Thu 12/8 9:30am-11: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).