CS 519-010, Algorithms (MS/MEng-Level), Winter 2018
||TR, 10-11:20am, GLSN 200
||He Zhang (zhangh7@) and Yilin Yang (yangyil@)
||Liang: T/Th, 11:25-11:55am (KEC 2069); TAs: M/T/Th/F, 4-5pm (KEC Atrium).
||[CLRS] Introduction to Algorithms, 3rd or 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)
||midterm: 20%, final: 25%, three quizzes: 7x3=21%;
weekly homework: 3x10=30%, class participation: 4%.
any complete HW submission automatically gets 2%.
the other 1% is based on blackbox testing of the specified coding problem.
no late submission is accepted.
Grading Curve: A/A-: 40-45%, B+/B/B-: 45-50%, the rest is C+/C/C- (very rare).
- This course is generally designed for MS/MEng students in CS.
- All CS graduate students (MS/MEng/PhD)
who have not taken an undergraduate algorithms class
(equivalent to our CS 325)
should take this class instead of the PhD-level CS 515 or the undergraduate-level CS 325.
- PhD students who have taken undergraduate algorithms should take CS 515 instead.
- MS/MEng students who have taken undergraduate algorithms should by default take
this class, unless they find it too basic.
This course counts as a Theory course for MS/MEng students, and will have a regular course number (CS 51x) in the near future.
Other students (EE, Stats, Robotics, etc) who are interested in algorithms
or seeking a job with top software firms are also welcome.
This course aims at the level of Google/Facebook coding interviews.
Students are assumed to be familiar with Data Structures 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.
For technical questions, come to office hours.
Otherwise you can raise a question on Canvas.|
(answering other people's questions correctly will be rewarded for class participation).
For grading questions, come to office hours.
Do not email us unless you have a personal issue.
The purpose of this course is six-fold:
- to teach you the most important algorithms and their implementations in Python
- to equip you with basic algorithm analysis skills (such as time complexity)
- to prepare you for industrial interviews with top firms (Google, Facebook, Microsoft, Amazon, etc)
- to convert you from a conventional C++/Java programmer to an elegant Pythonic programmer
- to prepare you for ACM International Collegiate Programming Contests (ICPC)
- to train you to think like a computer scientist: think recursively, abstractly, and rigorously.
- Python Tutorial, Review of Basic Data Structures, Sorting and Selection
mergesort, BSTs, memoization, heaps and heapsort, priority queue,
hashing, hashed heap, etc.)
- Basic Complexity Analysis (Master equation, tree method, amortization, etc.)
- Dynamic Programming (DP)
- Graph Algorithms: BFS/DFS, topolsort, Dijkstra, Prim, Kruskal
Detailed Schedule and Materials
quicksort, BST, quickselect
(Thu) mergesort, two-pointers, stable sort
divide-n-conquer: number of inversions|
longest path in binary tree
brief discussions of HW1
k numbers closest to input query, unsorted and sorted
quiz1 and discussions
(msort, inv, longest)
|Thu: Quiz 1|
what I learned from you, and what you should have learned from me.
The last two are different from the rest in the sense that they ask you to submit your output
to given testcases rather than programs (so that you can code in any language,
and their online judge system is as easy as a diff).
There are many other online judge systems that do not support Python
(traditionally ACM/ICPC uses C/C++/Java/Pascal),
such as the classical uva
(Universidad de Valladolid), poj (Peking University), tju, hit, hust, bjtu, etc.
(almost all major Chinese universities run their own online judge systems);
you can hone your C/C++/Java skills there if you have extra time.
Thanks to my former intern Zhuoran Yu for compiling this list.
- codeforces (recommended: each problem has annotated tags such as "dp", "dfs", etc.)
- leetcode oj (recommended: you can practice "writing on the whiteboard" there)
- zoj (Zhejiang University)
- project euler (math)
- rosalind (bioinfo)
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
For another MS/MEng-level algorithms class I taught before (at USC),
(with lots of details on analysis of complexity).
Last modified: Wed Jan 18 23:31:27 PST 2012