|Coordinates||T/Th, 10-11:20am, LINC 302 [Registrar] [Canvas] [Slack]|
Liang Huang (huanlian@)
|TAs||Tianshuo Zhou (zhoutian@), Apoorv Malik (malikap@)|
|Office Hours||Instructor: T/Th, 11:30-11:50am (KEC 2069)|
TAs: M 4-5pm & 5:30-6:30pm; W 5:30-6:30pm; F 4-5pm & 5:30-6:30pm (KEC Atrium).
Extra office hours available before exams.
[CLRS] Introduction to Algorithms, 3rd or 2nd edi. (default 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 (Thu, week 7): 25%+4%, Final: 25%+5%, Quizzes (Thu, weeks 2 & 4): 8+2+8+3=16%+5%; background survey: 2%.
picking up graded papers: 1%; post-midterm survey: 3%. optional HW11: +3%.
Weekly homework (1-6, 8-10): 3x8%+4%+2%=28%+2%.
Total extra credit: 19%.
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.
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.|
Canvas is for announcements (you'll receive an email for each announcement I made on Canvas)
and checking grades,
and Slack is for discussions.
For technical questions, come to office hours.
Otherwise you can raise a question on Slack.
Python Tutorial (first 5 pages)
quicksort analyses: best-case \(O(n \log n)\); worst-case \(O(n^2)\)
array concatenation is \(O(n)\)
(Thu) quicksort <-> BST (buggy qsort)
(msort, inversions, qsort->bst)
discussions of HW1|
hints on Quiz 1
|Thu: Quiz 1|
hand out graded quiz1|
discussions of HW2
\(k\) numbers closest to input query, sorted; Python
\(k\) numbers closest to input query, unsorted;
x+y=query: \(O(n^2)\)->\(O(n \log n)\)
(k-closest, two pointers, kmergesort)
|4||priority queue, lowerbound, datastream|
slides for nbest
|Thu: Quiz 2|
|5||dynamic programming (DP): basics [slides]||HW5|
(DP: part 1)
|6||dynamic programming (DP): advanced||HW6|
(DP: part 2)
|7||midterm review problems [solutions]||no HW7||Thu: Midterm|
|8-9||graph algorithms and their connections to DP;
|10||challenge problem and final review|
full DP slides (pages 11-17)
Final Review Questions and Solutions
(RNA: connecting all topics)
FINAL Wed 6/14 2-4pm
same room, closed book, closed notes
optional HW11 due Fri 6/16|
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).