COP 3503H CS II Honors

Fall 2024

Prof. Joseph J. LaViola Jr.

BA1 0213 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
   -matrix multiplication
   -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

Hurricane -- No Class

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
   - Johnson

Veteran's Day -- No Class

Maximum Flow
   - preliminaries
   - Ford-Fulkerson

Maximum Flow
   - Maximum Bipartite matching

Parallel Algorithms