# Algorithms (Advanced)(Course)

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

## Contents

- 1 Course Description
- 2 Schedule
- 2.1 Algorithmic Paradigms and Data Structures
- 2.1.1 Algorithm Design and Analysis, The Basics
- 2.1.2 Randomized Algorithms
- 2.1.3 Lower Bounds on Sorting Problem
- 2.1.4 Sorting in Linear Time
- 2.1.5 Median and Order Statistics
- 2.1.6 Heaps, Priority Queues
- 2.1.7 Divide and Conquer Paradigm
- 2.1.8 Dynamic Programming
- 2.1.9 Greedy Algorithms
- 2.1.10 Amortized Analysis
- 2.1.11 Exam 1

- 2.2 Graph Algorithms
- 2.3 Geometric Algorithms
- 2.4 Complexity and Approximation

- 2.1 Algorithmic Paradigms and Data Structures
- 3 Internal Links

# Course Description

Graduate Level Class

Credits: 3; Prerequisite: COT 3100, COP 3530.

Introduction and illustration of basic techniques for designing efficient algorithms and analyzing algorithm complexity.

Ungor - Spring 2006[2]

Study Materials[3]

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

### Sorting in Linear Time

Counting-sort, radix-sort

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

### Divide and Conquer Paradigm

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

### Exam 1

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

### Exam 2

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

### Exam 3 Final

# Internal Links

*Parent Article:* Lecture Courses