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