CS 3813/780, Advanced Programming, Spring 2014

Time and Location	MW, 9:15 -- 10:30 am, SB A135B
Instructor	Prof. Liang Huang (`huang@cs`)
Teaching Assistant	Dr. Lemao Liu (`lemaoliu@gmail`)
Course Admin	Ms. Xiuyi Huang (`xiuyi@cs`)
Course Homepage	http://acl.cs.qc.edu/~lhuang/teaching/advprg/
Office Hours	MW, 10:40 -- 11:15 am, SB A227 Additional office hours available before quizzes and exams.
Textbooks	[CLRS] Introduction to Algorithms, 3rd or 2nd edi. (default reference). [KT] Kleinberg and Tardos, Algorithm Design (also recommended) How to Think Like a Computer Scientist: Learning Python (also recommended)
Grading	homework: 5+6+8+8+8=35%, quizzes: 10+15=25%, final project: 25%. in-class problem-solving sessions: 2%x5=10%. class participation: 5%. homework policy: only high-level discussions are allowed; only one HW can be late for 24 hours.

Syllabus

The purpose of this course is five-fold, with the first three being more important:

to give you a much deeper understanding of algorithms by implementing them in Python
to prepare you for industrial interviews with top firms (Google, Facebook, Microsoft, Amazon, etc)
to prepare you for ACM International Collegiate Programming Contests (ICPC)
to convert you from a conventional C++/Java programmer to an elegant Pythonic programmer
to train you to think like a computer scientist: think recursively, abstractly, and rigorously.

We assume you have already taken both Datastructures and Algorithms, though the latter can be taken in parallel with this course upon instructor approval. The focus of this course is not on theoretical aspects such as complexities and proofs, but a solid understanding of theory is assumed, though we'll review them along the way.

Topics Covered and High-Level Schedule

Python Tutorial, Review of Basic Data Structures and Sorting
- HW1 out ~M 1/27: divide & conquer, qsort/qselect, msort, BSTs, memoization
- Quiz 1 on W 2/5 => check if you have enough prerequisite background
- HW2 out ~M 2/10: heaps & heapsort, hash, balancing BSTs
Dynamic Programming
- HW3 out ~M 3/3 (both chain DP and tree DP)
Graph Algorithms
- HW4 out ~W 3/19 (DFS/BFS, SCCs, Dijkstra/Bellman-Ford/Floyd-Warshall)
- Quiz 2 on M 4/7 (before spring break)
- HW5 out ~W 4/23 (Kruskal/Prim, Ford-Fulkerson/Edmonds-Karp)

Resources

HW1 will be trivial (to get you familiarized with Python while reviewing datastructures). HW2 will be more interesting, and HW3-5 will be challenging, with the use of those Online Judge Systems supporting Python, such as:

codeforces (recommended: each problem has annotated tags such as "dp", "dfs", etc.)
leetcode oj (you can practice "writing on the whiteboard" there)
zoj (Zhejiang University)
timus
project euler (math)
rosalind (bioinfo)

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 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 an algorithms class I taught before (at USC), see here (lots of details on analysis of complexity).

Have fun in lectures and HWs!

Detailed Schedule and Materials

Week Date Topics and Readings (CLRS and KT)
1 M 1/27

Administrativia
Review: quicksort, mergesort, BSTs, memoized Fibonacci (DP)
Python Showcase
slides for Section 1 (weeks 1-2)
HW1 out on T 1/28, due T 2/4: longest path on binary tree; randomized qselect; qsort=>BST, search/insertion on BST; memoized Ackermann
W 1/29

Python Tutorial
quickselect, randomization
2 M 2/3

More on Python Tutorial
Discussions of HW1
W 2/5

Quiz 1
More discussions on HW1
3 M 2/10

Discussions of Quiz1 solutions: fib.py msort.py qselect.py
Discussions of HW1 solutions: ackermann.py longest.py qselect.py (modified from Kent's) qsort.py (modified from Angelica's)
heap intro (CLRS Ch. 6)
HW2 out on T 2/11, due W 2/26: heapsort, hashtable, simplified dijkstra, datastream.
~~W 2/12~~

NO CLASS - UNIVERSITY HOLIDAY
4 ~~M 2/17~~

NO CLASS - UNIVERSITY HOLIDAY - CLASS MOVED TO THURSDAY
W 2/19

heaps: array representation, bubble-up, bubble-down
hw2 problem 1
gnuplot demo on O(n^2), O(nlogn), O(n), etc.
Th 2/20
(monday schedule)

heapq
applications of priority queue: k-way mergesort, choose top k from stream, etc.
Dijkstra
5 M 2/24

lowest common ancestor
first in-class problem solving session
W 2/26

help on hw2
DP intro: longest increasing subsequence
6 M 3/3

DP: knapsack: 0-1 & unbounded
W 3/5

7 M 3/10

HW3 out: DP
W 3/12

second in-class problem solving session
8 M 3/17

W 3/19

9 M 3/24
LCS & KMP
W 3/26
sample code for DP (0-1 Knapsack): memoized recursion (top-down) vs. bottom-up
when is top-down faster (sparse), and when is bottom-up faster (dense)?
10 M 3/31

miniquiz 3
HW3 solutions
W 4/2

LICS: O(n^4) -> O(n^3)
LCS w/ a query subseq
11 M 4/7

Viterbi and topological sort
Viterbi vs. Dijkstra
LCS w/ a query subseq
W 4/9

Viterbi on DAGs: backward vs. forward updates
Implementation details of topological sort
Matrix-Chain Multiplication
Viterbi on Hypergraphs
HW4 out
12 M 4/14-T 4/22 SPRING BREAK
12 W 4/23

Quiz 2

Liang Huang

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

Week	Date	Topics and Readings (CLRS and KT)
1	M 1/27	Administrativia Review: quicksort, mergesort, BSTs, memoized Fibonacci (DP) Python Showcase slides for Section 1 (weeks 1-2) HW1 out on T 1/28, due T 2/4: longest path on binary tree; randomized qselect; qsort=>BST, search/insertion on BST; memoized Ackermann
	W 1/29	Python Tutorial quickselect, randomization
2	M 2/3	More on Python Tutorial Discussions of HW1
	W 2/5	Quiz 1 More discussions on HW1
3	M 2/10	Discussions of Quiz1 solutions: fib.py msort.py qselect.py Discussions of HW1 solutions: ackermann.py longest.py qselect.py (modified from Kent's) qsort.py (modified from Angelica's) heap intro (CLRS Ch. 6) HW2 out on T 2/11, due W 2/26: heapsort, hashtable, simplified dijkstra, datastream.
	~~W 2/12~~	NO CLASS - UNIVERSITY HOLIDAY
4	~~M 2/17~~	NO CLASS - UNIVERSITY HOLIDAY - CLASS MOVED TO THURSDAY
	W 2/19	heaps: array representation, bubble-up, bubble-down hw2 problem 1 gnuplot demo on O(n^2), O(nlogn), O(n), etc.
	Th 2/20 (monday schedule)	heapq applications of priority queue: k-way mergesort, choose top k from stream, etc. Dijkstra
5	M 2/24	lowest common ancestor first in-class problem solving session
	W 2/26	help on hw2 DP intro: longest increasing subsequence
6	M 3/3	DP: knapsack: 0-1 & unbounded
	W 3/5
7	M 3/10	HW3 out: DP
	W 3/12	second in-class problem solving session
8	M 3/17
	W 3/19
9	M 3/24	LCS & KMP
	W 3/26	sample code for DP (0-1 Knapsack): memoized recursion (top-down) vs. bottom-up when is top-down faster (sparse), and when is bottom-up faster (dense)?
10	M 3/31	miniquiz 3 HW3 solutions
	W 4/2	LICS: O(n^4) -> O(n^3) LCS w/ a query subseq
11	M 4/7	Viterbi and topological sort Viterbi vs. Dijkstra LCS w/ a query subseq
	W 4/9	Viterbi on DAGs: backward vs. forward updates Implementation details of topological sort Matrix-Chain Multiplication Viterbi on Hypergraphs HW4 out
12	M 4/14-T 4/22	SPRING BREAK
12	W 4/23	Quiz 2