COP 3503H CS II Honors

Fall 2012

Prof. Joseph J. LaViola Jr.

ENG2 205 MWF 11:30am - 12:20pm

Welcome to COP 3503H -- Final Exam is on Dec. 5th, 10am!

Course Syllabus and Info

Some Lecture Notes courtesy of Arup Guha

Date	Lecture Description	Readings	Assignments	Resources
8/20/12	Introduction -course mechanics -role of algorithms -role of analysis	Cormen et al., Chapter 1
8/22/12	Mathematical Preliminaries -summations -logarithms and exponents -probability	Cormen et al., Appendix A,C
8/24/12	Getting Started - Insertion Sort	Cormen et al., Chapter 2, pgs. 16-29		Insertion Sort Applet 1 Insertion Sort Applet 2
8/27/12	Getting Started - Merge Sort	Cormen et al., Chapter 2, pgs. 29-39		Merge Sort Applet 1 Merge Sort Applet 2
8/29/12	Growth of Functions -theta notation -big and little o notation -big and little omega notation	Cormen et al., Chapter 3
8/31/12	Solving Recurrences -iteration method -substitution method -master method	Cormen et al., Chapter 4, pgs. 83-97	Homework 1
9/3/12	Holiday -- No class
9/5/12	Divide and Conquer -maximum-subarray -Stassen's algorithm	Cormen et al., Chapter 4, pgs. 68-82
9/7/12	Heap Sort -Heap property -Building a heap -Priority Queues	Cormen et al., Chapter 6		HeapSort Applet 1 HeapSort Applet 2 Priority Queue Applet 1 Priority Queue Applet 2
9/10/12	QuickSort - randomized partitioning - average case analysis	Cormen et al., Chapter 7		QuickSort Applet 1 QuickSort Applet 2 QuickSort Applet 3
9/12/12	Linear time sorting - counting sort - radix sort - bucket sort	Cormen et al., Chapter 8		Counting Sort Applet 1 Counting Sort Applet 2 Bucket Sort Applet 1 Radix Sort Applet 1 Radix Sort Applet 2
9/14/12	Teach Me Friday		Homework 2
9/17/12	Order statistics - minimum/maximum - selection	Cormen et al., Chapter 9
9/19/12	Dynamic Programming - rod cutting	Cormen et al., Chapter 15, pgs. 359-370
9/21/12	Dynamic Programming - matrix chain mutliplication	Cormen et al., Chapter 15, pgs. 370-377	Homework 3	Matrix Chain Applet
9/24/12	Dynamic Programming - longest common subequence	Cormen et al., Chapter 15, pgs. 390-397		LCS Applet
9/26/12	Dynamic Programming - optimal binary search tree	Cormen et al., Chapter 15, pgs. 397-404		Optimal Binary Search Applet
9/28/12	Dynamic Programming - finishing up	Cormen et al., Chapter 15, pgs. 378-389
10/1/12	Greedy Algorithms - activity selection	Cormen et al., Chapter 16, pgs. 414-423
10/3/12	Greedy Algorithms - elements of greedy strategy - Huffman codes	Cormen et al., Chapter 16, pgs. 423-437		Huffman Code Applet
10/5/12	Teach Me Friday		Homework 4
10/8/12	Elementary Graph Algorithms - breadth first search - depth first search	Cormen et al., Chapter 22, pgs. 583-602		BFS Applet DFS Applet
10/10/12	Elementary Graph Algorithms - topological sort	Cormen et al., Chapter 22, pgs. 612-615		Topological Sort Applet
10/12/12	Elementary Graph Algorithms - strongly connected components	Cormen et al., Chapter 22, pgs. 615-621	Midterm Exam	Connected Component Applet
10/15/12	Minimum Spanning Trees - constucting a MST	Cormen et al., Chapter 23, pgs. 624-629
10/17/12	Minimum Spanning Trees - Kruskal's algorithm	Cormen et al., Chapter 23, pgs. 631-633		Kruskal Applet
10/19/12	Minimum Spanning Trees - Prim's algorithm	Cormen et al., Chapter 23, pgs. 634-636		Prim Applet
10/22/12	Single Source Shortest Paths - Shortest Path properties	Cormen et al., Chapter 24, pgs. 643-650
10/24/12	Single Source Shortest Paths - Bellman-Ford	Cormen et al., Chapter 24, pgs. 651-6655		Bellman-Ford Applet
10/26/12	Single Source Shortest Paths - Dijkstra	Cormen et al., Chapter 24, pgs. 658-664	Homework 5	Dijkstra Applet
10/29/12	All-Pairs Shortest Paths - shortest path and matrix multiplication	Cormen et al., Chapter 25, pgs. 684-691
10/31/12	All-Pairs Shortest Paths - Floyd-Warshall	Cormen et al., Chapter 25, pgs. 693-699		Floyd-Warshall Applet
11/2/12	All-Pairs Shortest Paths - Johnson's algorithm	Cormen et al., Chapter 25, pgs. 700-705	Homework 6
11/5/12	Maximum Flow - preliminaries	Cormen et al., Chapter 26, pgs. 708-714
11/7/12	Maximum Flow - Ford-Fulkerson	Cormen et al., Chapter 26, pgs. 714-731		Ford-Fulkerson Applet
11/9/12	Teach Me Friday		Homework 7
11/12/12	Veteran's Day -- No Class
11/14/12	Maximum Flow - Ford-Fulkerson cont'd	Cormen et al., Chapter 26, pgs. 714-731
11/16/12	Maximum Flow - Maximum Bipartite matching	Cormen et al., Chapter 26, pgs. 732-735	Homework 8
11/19/12	Randomized Algorithms	Cormen et al., Chapter 5
11/21/12	No Class
11/23/12	Holiday -- No Class
11/26/12	Parallel Algorithms	Cormen et al., Chapter 27, pgs. 772-792
11/28/12	Parallel Algorithms	Cormen et al., Chapter 27, pgs. 792-805
11/30/12	Teach Me Friday
12/3/12	Review
12/5/12	Final Exam