CS 3813/780, Advanced Programming, Fall 2014

Time and Location	MW, 9:15 -- 10:30 am, SB A135B
Instructor	Prof. Liang Huang (`huang at cs`)
Teaching Assistants	Dr. Feifei Zhai (`ffzhai2012 at gmail`) and Lei Jiang (`jlwatereast at gmail`)
Course Admin	Ms. Xiuyi Huang (`xiuyi@cs`)
Course Homepage	http://acl.cs.qc.edu/~lhuang/teaching/advprg/
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	weekly homework: 30%, quizzes: 10+15=25%, final project: 20%. in-class miniquizzes: 15%. class participation: 10%. homework policy: HW is graded only by completeness, not by correctness. Therefore, no late HW is accepted.

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
Dynamic Programming
Graph Algorithms: Dijkstra, Prim, Kruskal

Resources

HW0 and 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 W 9/3

Administrativia
Brief Review: topological sort, priority queue, Dijkstra
Python Intro
slides for Section 1 (weeks 1-3)
HW0 out on W 9/3, due Su 9/7: dollar words
2 M 9/8

HW0 discussions; Pythonic style (sum/max: list comprehension)
Python Tutorial: quicksort
2 W 9/10

More on Python Tutorial
quicksort vs. binary search tree; inorder/insertion/deletion on BST
3 M 9/15

More on Python Tutorial
quickselect (CLRS 9.2, KT 13.5)
HW1 out
4 M 9/22

Discussions of HW1 solutions
Quiz 1

5 M 9/29

Discussions of Quiz 1: qselect on BSTs; best-case: O(1), worst-case: O(n)
lowest common ancestor
HW2 out

5 W 10/1

lowest common ancestor (cont'd)
top k numbers closest to a query x (unsorted and sorted)
triples x+y=z (hash and sweeping; O(n^2))

6 M 10/6

lowest common ancestor: feifei's nicer solution and liang's further embellishment
top k numbers closest to a query x (unsorted and sorted)

6 W 10/8

triples x+y=z (hash and sweeping; O(n^2))
heap: push (bubble-up) and pop (bubble-down): O(logn)
heapify: n bubble-ups: O(nlogn)
heapify: n bubble-downs: O(n)
1/2 + 2/4 + 3/8 + ... = (1/2 + 1/4 + 1/8 + ...) + (0 + 1/4 + 2/8 + 3/16 + ...)
= 1 + (1/4 + 1/8 + 1/16 + ...) + (1/8 + 2/16 + 3/32 + ...) = 1 + 1/2 + ... = 2.
intuition: n bubble-down: the majority of nodes are cheap (from lower-levels downto leaves: ~1);
n bubble-ups: the majority are expensive (from leaves upto root: ~logn)
hw3 out

Liang Huang

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

Week	Date	Topics and Readings (CLRS and KT)
1	W 9/3	Administrativia Brief Review: topological sort, priority queue, Dijkstra Python Intro slides for Section 1 (weeks 1-3) HW0 out on W 9/3, due Su 9/7: dollar words
2	M 9/8	HW0 discussions; Pythonic style (sum/max: list comprehension) Python Tutorial: quicksort
2	W 9/10	More on Python Tutorial quicksort vs. binary search tree; inorder/insertion/deletion on BST
3	M 9/15	More on Python Tutorial quickselect (CLRS 9.2, KT 13.5) HW1 out
4	M 9/22	Discussions of HW1 solutions Quiz 1
5	M 9/29	Discussions of Quiz 1: qselect on BSTs; best-case: O(1), worst-case: O(n) lowest common ancestor HW2 out
5	W 10/1	lowest common ancestor (cont'd) top k numbers closest to a query x (unsorted and sorted) triples x+y=z (hash and sweeping; O(n^2))
6	M 10/6	lowest common ancestor: feifei's nicer solution and liang's further embellishment top k numbers closest to a query x (unsorted and sorted)
6	W 10/8	triples x+y=z (hash and sweeping; O(n^2)) heap: push (bubble-up) and pop (bubble-down): O(logn) heapify: n bubble-ups: O(nlogn) heapify: n bubble-downs: O(n) 1/2 + 2/4 + 3/8 + ... = (1/2 + 1/4 + 1/8 + ...) + (0 + 1/4 + 2/8 + 3/16 + ...) = 1 + (1/4 + 1/8 + 1/16 + ...) + (1/8 + 2/16 + 3/32 + ...) = 1 + 1/2 + ... = 2. intuition: n bubble-down: the majority of nodes are cheap (from lower-levels downto leaves: ~1); n bubble-ups: the majority are expensive (from leaves upto root: ~logn) hw3 out