This article describes the Algorithms (Course), based on the University of Florida graduate class Analysis of Algorithms, COT5405.

# Course Description

Credits: 3; Prerequisite: COT 3100, COP 3530.
Introduction and illustration of basic techniques for designing efficient algorithms and analyzing algorithm complexity.

Ungor - Spring 2006
Study Materials

The textbook is Introduction to Algorithms by Cormen, 2nd. Sections with a "*" in the Cormen books are intended for graduate students.

# Schedule

## Algorithmic Paradigms and Data Structures

2nd Ch 1,2,3,4,5,7,8,9, - , 15,16,17
3rd Ch 4

### Algorithm Design and Analysis, The Basics

Correctness, time and space complexity, insertion-sort, growth of functions, asymptotic notation, big-Oh, big-Omega, big-Theta, upper bound, lower bound, tight bounds, divide-and-conquer, mergeSort, recurrences, substitution method, recursion-tree method, master theorem.
2nd Ch 1,2,3,4

### Randomized Algorithms

Quicksort, partitioning, worst-case, randomization, expected-time analysis
2nd Ch 5,7

### Lower Bounds on Sorting Problem

Lower bound on comparison sorts, decision-tree model
2nd Ch 8

2nd Ch 8

### Median and Order Statistics

Selection, median, quickselect, deterministic selection
2nd Ch 9

### Heaps, Priority Queues

Array representation of heaps, heap property, min-heap, max-heap, building a heap, heapsort, analysis of priority queue operations
2nd Ch 6

Review of various examples, using master theorem, computing power of a number, matrix multiplication, Strassen's algorithm, VLSI design, complete binary treee embedding
3rd Ch4

### Dynamic Programming

Longest common subsequence (LCS), brute-force algorithm, optimal substructure, shortest-path vs. longest-path, overlapping subproblems, memoization algorithm, dynamic programming algorithm, Matrix-chain multiplication (MCM), optimal substructure, LCS vs. MCM
2nd Ch 15

### Greedy Algorithms

Activity selection problem, optimal substructure, greedy choice, 0/1 knapsack problem, fractional knapsack problem, greedy vs. dynamic programming
2nd Ch 16

### Amortized Analysis

Aggregate method, accounting method, potential method
2nd Ch 17

## Graph Algorithms

### Elementary Graph Algorithms

Graphs and their representations, handshaking lemma
2nd Ch 22

### Minimum Spanning Trees

Greedy algorithms, optimal substructure, greedy choice property, Prim's algorithm, correctness proof, Kruskal's algorithm
2nd Ch 23

### Shortest Paths

Single-source shortest paths, path properties, triangle inequality, Dijkstra's algorithm, correctness proof, time analysis, unweighted graphs, breadth first search
2nd Ch 24

### Single Source Shortest Paths

Negative edge weights, Bellman-Ford algorithm, detecting negative cycles, linear programming and difference constraints
2nd Ch 24

### All Pairs Shortest Paths

Dynamic programming formulations, matrix multiplication algorithm for shortest paths, Floyd-Warshall algorithm, graph reweighting, Johnson's algorithm, transitive closure
2nd Ch 25

### Network Flows

Flow network, conservation of flow, positive flow, cut, residual graph, augmenting paths
2nd Ch 26

## Geometric Algorithms

### Geometric Algorithms

Points, lines, line segments, polygons, triangulations, geometric objects, orientation test, orthogonal range searching, range trees, line segment intersection, sweepline algorithm
2nd Ch 33

### Convex Hull Algorithms

Jarvis March (gift wrapping), Graham's Scan, Divide and Conquer on understanding problems, sorting vs. sortedness, computing vs. determining convex hulls, a lower bound on computing convex hull, reduction from sorting
2nd Ch 33

### Closest/Furthest Point Pair Problems

Repeated squaring, closest point pair problem, furthest point pair problem
2nd Ch 33

## Complexity and Approximation

### NP-completeness

Find the longest path, easy vs. hard problems, traveling salesperson problem (TSP), dynamic programming for TSP, max clique problem, exponential vs. polynomial time, decision problems vs. optimization problems. Complexity classes P and NP, non-deterministic polynomial time solvable problems, polynomial time verification, reductions, polynomial time reductions, satisfiability problem (SAT), Cook's theorem, NP-hardness, NP-completeness, Clique problem is NP-complete: reduction from SAT, Independent Set Problem is NP-complete: reduction from Clique problem, Vertex Cover Problem is NP-complete: reduction from Independent Set problem
2nd Ch 34

### Approximation Algorithms

How to cope with Hard Problems. Enumeration strategies, Heuristics, Polynomial Time Approximation Schemes. Approximation ratio. Two Algorithms for Vertex Cover Problem: Not so good Greedy Algorithm, and simple 2-factor Approximation algorithm. 2-approximation algorithm for Metric TSP. How good is an analysis? Proving tightness of a bound with an example. How good is an algorithm? Improving Approximation ratio. A 3/2 Approximation Algorithm for Metric TSP.
2nd Ch 35