|
|
|
COT5405: ANALYSIS OF ALGORITHMS |
|
|||||||||
Term: Summer 2008
| Time: Pre-recorded class (online lecture videos)
| Location: UF E-learning | Professor:
Alper Üngör | Professor Office Hours: 2-4pm Thursdays (CSE430) | Teaching Assistant: Nejhum Shahed, ( smshahed [AT] cise.ufl.edu) | TA Office Hours: 2-4pm Tuesdays (CSE309) | Catalogue number: 9189 | Credit hours: 3 |
| info | announcements | schedule | references |
| Date/Video# | Lecture Topic | Assignments | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 1-2 | Introduction, Syllabus, Course structure. | | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ALGORITHMIC PARADIGMS AND DATA STRUCTURES | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 3 |
Algorithm Design and Analysis correctness, time and space complexity, insertion-sort [CLRS01 Ch 1,2] (Download the lecture slides on E-learning) | 4-5
| The Basics | growth of functions, asymptotic notation, big-Oh, big-Omega, big-Theta upper bound, lower bound, tight bounds divide-and-conquer, mergeSort, matrix multiplication recurrences, substitution method, recursion-tree method, master theorem [CLRS01 Ch 2,3,4,28] (Download the lecture slides on E-learning) | 6
|
Randomized Algorithms | quicksort, partitioning, worst-case, randomization, expected-time analysis [CLRS01 Ch 5,7] (Download the lecture slides on E-learning) | 7-8
|
Sorting in Linear Time | lower bound on comparison sorts, decision-tree model, linear time sorting, counting-sort, radix-sort [CLRS01 Ch 8] Median and Order Statistics selection, median, quickselect, deterministic selection [CLRS01 Ch 9] (Download the lecture slides on E-learning) Hw1 out | 9
| 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) | 10-11
|
Hashing | direct-access hash tables, collisions, chaining, division method, multiplication method open addressing, linear probing, quadratic probing, double hashing analysis of open-address hashing [CLRS01 Ch 11] (Download the lecture slides on E-learning) Balanced Search Trees binary search trees, red-black trees, height bound, rotations, insertion [CLRS01 Ch 12,13] (Download the lecture slides on E-learning) Hw1 due | Hw2 out 12
| Augmented Data Structures | dynamic order statistics, augmentation methodology, interval trees [CLRS01 Ch 14] (Download the lecture slides on E-learning) | 13-14
| 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) | 15
| Amortized Analysis | aggregate method, accounting method, potential method [CLRS01 Ch 17] (Download the lecture slides on E-learning) More on Dynamic Programming matrix-chain multiplication (MCM), optimal substructure, LCS vs. MCM [CLRS01 Ch 15] Hw2 due | 16
| Exam Review (Fall 2007 MIDTERM-1)
| | June 11 W
| MIDTERM EXAM I
| | GRAPH ALGORITHMS
| 17-18
| 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] Hw3 out | 19
| 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] | 20-21
| 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] Hw3 due | 22
| Network Flows | flow network, conservation of flow, positive flow, cut, residual graph, augmenting paths [CLRS01 Ch 26] Hw4 out | 23-24
| 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] | GEOMETRIC ALGORITHMS
| 25
| 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.4] | 26-27
| Convex Hull Algorithms | Jarvis March (gift wrapping), Graham's Scan, Divide and Conquer Chan's algorithm [CLRS01 Ch 33] Hw4 due | 28
| Closest/Furthest Point Pair Problems | Chan's algorithm analysis, repeated squaring, closest point pair problem furthest point pair problem [CLRS01 Ch 33] | July 16 W
| MIDTERM EXAM II
| |
SELECTED TOPICS
| 29
| Miscellaneous Topics | on understanding problems, sorting vs. sortedness, computing vs. determining convex hulls a lower bound on computing convex hull, reduction from sorting | 30-31
| String Matching | searching patterns in text, naive algorithm, redundant comparisons finite state machines, Knuth-Morris-Pratt algorithm, failure function [CLRS01 Ch 32] |
COMPLEXITY AND APPROXIMATION
| 32
| 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] | 33-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] | 35
| NP-completeness | recap, comments on complexity classes, Other complexity classes, PSPACE, co-NP common mistakes and missunderstandings, direction of the reduction incorrect assumptions made establishing the transformation kite problem, reduction from clique problem [CLRS01 Ch 34] | 36-37
| Approximation Algorithms | [CLRS01 Ch 35] | 38
| Approximation Algorithms | [CLRS01 Ch 35] | Aug 8 F
| FINAL EXAM
| | | ||||||||||||
BooksLinks
[CLRS01] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms, 2nd Edition, McGraw-Hill, 2001 - REQUIRED [HSR97] E. Horowitz, S. Sahni and S. Rajasekaran. Computer Algorithms , Computer Science Press, 1997 - REFERENCE [E02] Lecture Notes on ConvexHulls by J. Erickson.
[L1] A compendium of NP optimization problems
[L2] ACM-SIGACT
[L3] Computing Science Journal Collections [L4] Journals of ACM [L5] Journals of SIAM
| info | announcements | schedule | references |
Alper Üngör
(ungor@cise.ufl.edu)
Apr 2008