|
|
|
|
COT5405: ANALYSIS OF ALGORITHMS |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Term: Spring 2018 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Time (period): T (3-4), R (4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Location: NEB0100 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Professor: Alper Ungor | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Teaching/Grader Assistants: ) Serdar Ayaz | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Contact e-mail: cot5405sp18@cise.ufl.edu | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Weekly Schedule (office hours):
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| info | announcements | schedule | references |
| Jan 2 | To help you decide whether you are ready to take this class, please first take a look at the final exam of one of the pre-requisites COT3100 Final Exam |
| Jan 2 | Download the syllabus |
| Jan 2 | First class meeting is on Jan 9, Tuesday. |
| Tentative Date | Lecture Topic | Assignments | |
| Introduction, Syllabus, Course structure. | | ||
| ALGORITHMIC PARADIGMS AND DATA STRUCTURES | |||
| |
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 [CLRS01 Ch 1,2,3,4] (Download the lecture slides on e-Learning) | ||
|
Randomized Algorithms quicksort, partitioning, worst-case, randomization, expected-time analysis [CLRS01 Ch 5,7] (Download the lecture slides on e-Learning) | |
||
|
Lower Bounds on Sorting Problem lower bound on comparison sorts, decision-tree model [CLRS01 Ch 8] (Download the lecture slides on e-Learning) | |||
|
Sorting in Linear Time counting-sort, radix-sort [CLRS01 Ch 8] (Download the lecture slides on e-Learning) | |||
|
Median and Order Statistics selection, median, quickselect, deterministic selection [CLRS01 Ch 9] (Download the lecture slides on e-Learning) |
|
||
|
Heaps, Priority Queues array representation of heaps, heap property, min-heap, max-heap, building a heap heapsort, analysis of priority queue operations [CLRS01 Ch 6] (Download the lecture slides on e-Learning) |
|||
|
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 [CLRS09 Ch4] (Download the lecture slides on e-Learning)
|
| ||
|
Dynamic Programming longest common subsequence (LCS), brute-force algorithm, optimal substructure shortest-path vs. longest-path, overlapping subproblems memoization algorithm, dynamic programming algorithm [CLRS01 Ch 15] (Download the lecture slides on e-Learning) |
|||
|
More on Dynamic Programming matrix-chain multiplication (MCM), optimal substructure, LCS vs. MCM [CLRS01 Ch 15] |
Greedy Algorithms activity selection problem, optimal substructure, greedy choice 0/1 knapsack problem, fractional knapsack problem, greedy vs. dynamic programming [CLRS01 Ch 16] |
|
|
| Amortized Analysis aggregate method, accounting method, potential method [CLRS01 Ch 17] (Download the lecture slides on e-Learning) | | ||
| Feb 13 T | EXAM I | | |
| GRAPH ALGORITHMS | |||
|
Elementary Graph Algorithms graphs and their representations, handshaking lemma [CLRS01 Ch 22] | | ||
|
Minimum Spanning Trees greedy algorithms, optimal substructure, greedy choice property, Prim's algorithm, correctness proof, Kruskal's algorithm [CLRS01 Ch 23] | | ||
| Shortest Paths single-source shortest paths, path properties, triangle inequality Dijkstra's algorithm, correctness proof, time analysis, unweighted graphs, breadth first search [CLRS01 Ch 24] |
|
||
| Single Source Shortest Paths negative edge weights, Bellman-Ford algorithm, detecting negative cycles linear programming and difference constraints [CLRS01 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 [CLRS01 Ch 25] |
|||
| Network Flows flow network, conservation of flow, positive flow, cut, residual graph, augmenting paths [CLRS01 Ch 26] | | ||
| Network Flows max-flow min-cut theorem and its proof, Ford-Fulkerson algorithm Edmonds-Karp algorithm, A bound on the number of augmentations [CLRS01 Ch 26] | | ||
| Mar 27 T | EXAM II | | |
| GEOMETRIC ALGORITHMS | |||
| Geometric Algorithms points, lines, line segments, polygons, triangulations, geometric objects, orientation test orthogonal range searching, range trees, line segment intersection, sweepline algorithm [CLRS01 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 [CLRS01 Ch 33] Closest/Furthest Point Pair Problems repeated squaring, closest point pair problem furthest point pair problem [CLRS01 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 [CLRS01 Ch 34] | | ||
| NP-completeness 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 Indepent Set problem [CLRS01 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. [CLRS01 Ch 35] | |||
| Approximation Algorithms 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. [CLRS01 Ch 35] | | ||
| April 24 T | EXAM III | | |
REQUIRED TEXTBOOK
[CLRS09] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms, 3rd Edition, McGraw-Hill, 2009
[CLRS01] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms, 2nd Edition, McGraw-Hill, 2001 [KT09] J. Kleinberg, E. Tardos. Algorithm Design, Pearson, 2009 [DPV06] S. Dasgupta, C. Papadimitrou, U. Vazirani. Algorithms , McGraw-Hill, 2006 [HSR97] E. Horowitz, S. Sahni and S. Rajasekaran. Computer Algorithms , Computer Science Press, 1997 [GJ79] M. Garey, D. Johnson. Algorithms , W. H. Freeman, 1979
[L1] A compendium of NP optimization problems
[L2] ACM-SIGACT
[L4] Journals of ACM [L5] Journals of SIAM
| info | announcements | schedule | references |