CS 519-005, Algorithms (MS/MEng-Level), Fall 2016

Coordinates MWF, 10-10:50am, GLSN 200 [Registrar] [Canvas]
Instructor Liang Huang
TAs Mingbo Ma (lead)
Dezhong Deng
Office hours W/Th 5-6pm, KEC 2048 (Mingbo, grading questions welcome).
Th 9:10-10am, KEC 2069 (Liang, grading questions welcome).
F 5-6pm, KEC 2048 (Dezhong, no grading questions allowed).
Textbooks [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)
Grading (tentative) midterm: 20%, final: 25%, four quizzes: 5x4=20%;
weekly homework: 3x10=30%, class participation: 5%.
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.
Intended Audience
  • 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) starting Fall 2017.
  • Other students (EE, Stats, etc) who are interested in algorithms or finding a job with top software firms are also welcome.
  • 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.
Other Policies For questions, come to the office hours. If you are unable to come, you can raise a question on Canvas.
If you have a personal (non-grading) question, send it here which will reach the instructor and all TAs.
Do not email us individually. For grading questions, please come to W/Th office hours.

Objectives

The purpose of this course is six-fold:

Topics Covered

  1. Python Tutorial, Review of Basic Data Structures, Sorting and Selection
    (divide-n-conquer, quicksort/quickselect, mergesort, BSTs, memoization, heaps and heapsort, priority queue, hashing, hashed heap, etc.)
  2. Basic Complexity Analysis (Master equation, tree method, amortization, etc.)
  3. Dynamic Programming (DP)
  4. Graph Algorithms: BFS/DFS, topolsort, Dijkstra, Prim, Kruskal

Detailed Schedule and Materials

WeekTopicsHomeworkQuiz/Exam
1 (Wed) Admin
Python Tutorial
quicksort, BST
(Fri) quickselect, mergesort, two-pointers, stable sort
HW1
(qselect, qsort->bst)
2 (Mon) divide-n-conquer: number of inversions
longest path in binary tree
(Wed) brief discussions of HW1
k numbers closest to input query, unsorted and sorted
(Fri) quiz1 and discussions
x+y=z
HW2
(msort, inv, longest) 		Fri: Quiz 1
(covers HW1)
3 (Mon) hand out graded quiz1
insertion sort can be made O(nlogn) by balanced BST
discussions of HW2:
qsort with randomized pivot can be made stable by 3-way partition
selection sort (in-place) is not stable
generic way to stablize sort: decorate-sort-undecorate
mergesort implementation: mergesorted(a[1:], b) makes it O(n^2)
(this "beautiful" style only works for linkedlist or functional languages)

(Wed) cont'd discussions of HW2
Python lazylists (yield)
longest path implementation
x+y=z
(Fri) Priority Queue; heap; bubble-up/bubble-down 		HW3
(k-closest, two pointers)
4 (Mon) heapify is O(n)
Python heapq tutorial
empirical difference b/w heapify and n heappushes
(sorted array is best-case (where heapify is slower);
reverse-sorted is worst-case; use random list for avg-case)
heapq bubble-down follows Knuth (vol.3) and different from textbooks
(Wed) brief discussions of HW3
k-way mergesort
data stream
(Fri) quiz2 and discussions
HW4
(priority queues; baby Dijkstra) 		Fri: Quiz 2
(covers HWs1-3/quiz1)
5 (Mon) Discussions of HW4 and Quiz2
(Wed) DP 101: Fibonacci and memoization
(Fri) Maximum Independent Set
memoization wrapper
cache=None instead of cache={}
HW5
(DP I: memoized Fibonacci, # of BSTs, # of bistrings)
6 (Mon) Help with HW5: backtracing, bitstrings, and BSTs
ipython %memit (sudo pip install memory_profiler; %load_ext memory_profiler)
(Wed) Discussions of HW5
Knapsack: unbounded
(Fri) Knapsack: 0-1 		HW6
(DP II: knapsack, unbounded and bounded)
7 (Mon) Discussions of HW6
defaultdict
(Wed) Review Problems Solutions
(Fri) Midterm 		(no HW; review problems I)
Office Hours W/Th 4-6pm in KEC 2057 		Midterm 11/4
(covers HWs1-6)
8 (Mon) Discussions of Midterm solutions
(Wed) LIS, TSP
(Fri) Veteran's Day 11/11; NO CLASS 		HW8
(DP III: LIS, TSP)
9 (Mon) TSP; sparse vs. dense graphs
(Wed) BFS topolsort; Viterbi
(Fri) Discussions of HW8
DFS topolsort; Dijkstra 		HW9
(BFS-Topol/Viterbi/Dijkstra)
10 (Mon) CKY: RNA structure
(Wed) Discussions of HW9; k-best RNA structure
(Fri) THANKSGIVING 		Challenge problem (RNA structure)
11 (Mon) Hints on RNA structures: total and kbest
(Challenge problem due Tue)
(Wed) Discussions of Challenge problem
(Fri) Final Review Problems 		(no HW; review problems II) FINAL M 12/5 12pm-1:50pm
same room

Summary: what I learned from you, and what you should have learned from me.

Resources

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.

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).

For another MS/MEng-level algorithms class I taught before (at USC), see here (with lots of details on analysis of complexity).

Liang Huang
Last modified: Wed Jan 18 23:31:27 PST 2012