COP 3503H CS II Honors

Fall 2020

Prof. Joseph J. LaViola Jr.

CB1 120 MW 10:30am - 11:45am

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

Getting Started
   - Insertion Sort

Getting Started
   - Merge Sort

Mathematical Preliminaries
   -summations
   -logarithms and exponents

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

Solving Recurrences
   -iteration method
   -substitution method
   -master method

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

Divide and Conquer
   -Strassen's algorithm

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

QuickSort
   - randomized partitioning
   - average case analysis

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

Order statistics
   - minimum/maximum
   - selection

Dynamic Programming
   - rod cutting
   - matrix chain mutliplication

Dynamic Programming
   - longest common subsequence

Dynamic Programming
   - optimal binary search tree

Dynamic Programming
   - optimal BST cont'd
   - finishing up

Greedy Algorithms
   - Activity Selection

Greedy Algorithms
   - elements of greedy strategy
   - Huffman codes

Elementary Graph Algorithms
   - breadth first search
   - depth first search

Elementary Graph Algorithms
   - strongly connected components

Minimum Spanning Trees
   - constucting a MST

Minimum Spanning Trees
   - Kruskal's algorithm
   - Prim's algorithm

Single Source Shortest Paths
   - Shortest Path properties
   - Bellman-Ford

Single Source Shortest Paths
   - Dijkstra
   - Difference constraints

All-Pairs Shortest Paths
   - shortest path and matrix multiplication
   - Floyd-Warshall

All-Pairs Shortest Paths
   - Transitive Closure and Johnson

Maximum Flow
   - preliminaries
   - Ford-Fulkerson

Maximum Flow
   - Maximum Bipartite matching

Parallel Algorithms

Holiday -- No Class

Parallel Algorithms