COP 3503H CS II Honors

Fall 2017

Prof. Joseph J. LaViola Jr.

BA1 0213 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/21/17

Introduction
   -course mechanics
   -role of algorithms
   -role of analysis

 Cormen et al., Chapter 1

8/23/17

Getting Started
   - Insertion Sort

 Cormen et al., Chapter 2, pgs. 16-29
Insertion Sort Applet
8/25/17

Mathematical Preliminaries
   -summations
   -logarithms and exponents
   -probability

 Cormen et al., Appendix A,C

8/28/17

Getting Started
   - Merge Sort

 Cormen et al., Chapter 2, pgs. 29-39
Merge Sort Animation 1
Merge Sort Animation 2
8/30/17

Growth of Functions
   -theta notation
   -big and little o notation
   -big and little omega notation

 Cormen et al., Chapter 3

9/1/17

Solving Recurrences
   -iteration method
   -substitution method
   -master method

 Cormen et al., Chapter 4, pgs. 83-97 Homework 1
9/4/17 Holiday -- No class


9/6/17

Divide and Conquer
   -maximum-subarray
   -Strassen's algorithm

 Cormen et al., Chapter 4, pgs. 68-82

9/8/17 Hurricane -- No class


9/11/17 Hurricane -- No class


9/13/17 Hurricane -- No class


9/15/17 Hurricane -- No class


9/18/17 Strassen's Algorithm


9/20/17

Heap Sort
   -Heap property
   -Building a heap
   -Priority Queues

 Cormen et al., Chapter 6
HeapSort Applet 1
9/22/17

QuickSort
   - randomized partitioning
   - average case analysis

 Cormen et al., Chapter 7 Homework 2
 QuickSort Applet 1
QuickSort Applet 2
9/25/17

Linear time sorting
   - counting sort
   - radix sort
   - bucket sort

 Cormen et al., Chapter 8
Counting Sort Applet
Bucket Sort Applet
Radix Sort Applet
9/27/17

Order statistics
   - minimum/maximum
   - selection

 Cormen et al., Chapter 9

9/29/17

Dynamic Programming
   - rod cutting

 Cormen et al., Chapter 15, pgs. 359-370 Homework 3
10/2/17

Dynamic Programming
   - matrix chain mutliplication

 Cormen et al., Chapter 15, pgs. 370-377
Matrix Chain Animation
10/4/17

Dynamic Programming
   - longest common subequence

 Cormen et al., Chapter 15, pgs. 390-397
LCS applet
10/6/17

Dynamic Programming
   - optimal binary search tree

 Cormen et al., Chapter 15, pgs. 397-404 Homework 4
10/9/17

Dynamic Programming
   - finishing up

 Cormen et al., Chapter 15, pgs. 378-389

10/11/17

Greedy Algorithms
   - activity selection

 Cormen et al., Chapter 16, pgs. 414-423

10/13/17

Greedy Algorithms
   - elements of greedy strategy
   - Huffman codes

 Cormen et al., Chapter 16, pgs. 423-437 Midterm exam
 Huffman Code Applet
10/16/17

Elementary Graph Algorithms
   - breadth first search
   - depth first search

 Cormen et al., Chapter 22, pgs. 583-602
BFS Applet
DFS Applet
10/18/17

Elementary Graph Algorithms
   - topological sort

 Cormen et al., Chapter 22, pgs. 612-615
Topological Sort Applet
10/20/17

Elementary Graph Algorithms
   - strongly connected components

 Cormen et al., Chapter 22, pgs. 615-621
Connected Component Applet
10/23/17

Minimum Spanning Trees
   - constucting a MST

 Cormen et al., Chapter 23, pgs. 624-629

10/25/17

Minimum Spanning Trees
   - Kruskal's algorithm

 Cormen et al., Chapter 23, pgs. 631-633
Kruskal Applet
10/27/17

Minimum Spanning Trees
   - Prim's algorithm

 Cormen et al., Chapter 23, pgs. 634-636 Homework 5
 Prim Applet
10/30/17

Single Source Shortest Paths
   - Shortest Path properties

 Cormen et al., Chapter 24, pgs. 643-650

11/1/17

Single Source Shortest Paths
   - Bellman-Ford

 Cormen et al., Chapter 24, pgs. 651-657
Bellman-Ford Applet
11/3/17

Single Source Shortest Paths
   - Dijkstra

 Cormen et al., Chapter 24, pgs. 658-664 Homework 6
 Dijkstra Applet
11/6/17

All-Pairs Shortest Paths
   - shortest path and matrix multiplication

 Cormen et al., Chapter 25, pgs. 684-691

11/8/17

All-Pairs Shortest Paths
   - Floyd-Warshall

 Cormen et al., Chapter 25, pgs. 693-699
Floyd-Warshall Applet
11/10/17 Veteran's Day -- No class
Homework 7
11/13/17

All-Pairs Shortest Paths
   - Johnson's algorithm

 Cormen et al., Chapter 25, pgs. 700-705

11/15/17

Maximum Flow
   - preliminaries

 Cormen et al., Chapter 26, pgs. 708-714

11/17/17

Maximum Flow
   - Ford-Fulkerson

 Cormen et al., Chapter 26, pgs. 714-731 Homework 8
 Ford-Fulkerson Applet
11/20/17

Maximum Flow
   - Maximum Bipartite matching

 Cormen et al., Chapter 26, pgs. 732-735

11/22/17

No Class


11/24/17

Holiday -- No Class


11/27/17

Parallel Algorithms

 Cormen et al., Chapter 27, pgs. 772-792

11/29/17

Parallel Algorithms

 Cormen et al., Chapter 27, pgs. 792-805

12/1/17

Finish Parallel Algorithms