CS 3813/780, Advanced Programming, Spring 2014
The purpose of this course is five-fold, with the first three being more important:
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.
- 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.
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)
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,
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.
- 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)
- 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 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||
- 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:
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|
- applications of priority queue: k-way mergesort, choose top k from stream, etc.
|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||
Last modified: Wed Jan 18 23:31:27 PST 2012