COP 3503H CS II Honors

Fall 2014

Prof. Joseph J. LaViola Jr.

BHC 131 MWF 11:30am - 12:20pm

Welcome to COP 3503H! -- HW8 has been posted.

Course Syllabus and Info

Some Lecture Notes courtesy of Arup Guha

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