Algorithms (Advanced)(Course)

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

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.

Introduction to Algorithms 2rd, 2001 Errata[1]

Syllabus for Spring 2006

Introduction To Algorithms 3rd, 2009	Algorithm Design 1st, 2006
Instructor's Manual

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

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

Internal Links

Parent Article: Lecture Courses