COT5405: ANALYSIS OF ALGORITHMS  
Term: Spring 2018  
Time (period): T (34), R (4)  
Location: NEB0100  
Professor: Alper Ungor  
Teaching/Grader Assistants: ) Serdar Ayaz  
Contact email: 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 prerequisites 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, insertionsort growth of functions, asymptotic notation, bigOh, bigOmega, bigTheta upper bound, lower bound, tight bounds, divideandconquer, mergeSort recurrences, substitution method, recursiontree method, master theorem [CLRS01 Ch 1,2,3,4] (Download the lecture slides on eLearning)  
Randomized Algorithms quicksort, partitioning, worstcase, randomization, expectedtime analysis [CLRS01 Ch 5,7] (Download the lecture slides on eLearning)  

Lower Bounds on Sorting Problem lower bound on comparison sorts, decisiontree model [CLRS01 Ch 8] (Download the lecture slides on eLearning)  
Sorting in Linear Time countingsort, radixsort [CLRS01 Ch 8] (Download the lecture slides on eLearning)  
Median and Order Statistics selection, median, quickselect, deterministic selection [CLRS01 Ch 9] (Download the lecture slides on eLearning) 


Heaps, Priority Queues array representation of heaps, heap property, minheap, maxheap, building a heap heapsort, analysis of priority queue operations [CLRS01 Ch 6] (Download the lecture slides on eLearning) 

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 eLearning)  
Dynamic Programming longest common subsequence (LCS), bruteforce algorithm, optimal substructure shortestpath vs. longestpath, overlapping subproblems memoization algorithm, dynamic programming algorithm [CLRS01 Ch 15] (Download the lecture slides on eLearning) 

More on Dynamic Programming matrixchain 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 eLearning)   
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 singlesource 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, BellmanFord 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 FloydWarshall 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 maxflow mincut theorem and its proof, FordFulkerson algorithm EdmondsKarp 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  
NPcompleteness 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]   
NPcompleteness complexity classes P and NP, nondeterministic polynomial time solvable problems polynomial time verification, reductions, polynomial time reductions satisfiability problem (SAT), Cook's theorem, NPhardness, NPcompleteness Clique problem is NPcomplete: reduction from SAT Independent Set Problem is NPcomplete: reduction from Clique problem Vertex Cover Problem is NPcomplete: 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 2factor Approximation algorithm. 2approximation 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, McGrawHill, 2009
[CLRS01] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms, 2nd Edition, McGrawHill, 2001 [KT09] J. Kleinberg, E. Tardos. Algorithm Design, Pearson, 2009 [DPV06] S. Dasgupta, C. Papadimitrou, U. Vazirani. Algorithms , McGrawHill, 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] ACMSIGACT
[L4] Journals of ACM [L5] Journals of SIAM
info  announcements  schedule  references 