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):
  7:30 8:00 8:30 9:00 9:30 10:00 10:30 11:00 11:30 12:00 12:30 13:00 13:30 14:00 14:30 15:00 15:30 16:00 16:30 17:00 17:30 18:00
Monday                               Serdar
(CSE 309)
     
Tuesday     Lecture
(NEB0100)
                               
Wednesday                               Serdar
(CSE 309)
     
Thursday         Lecture
(NEB0100)
Alper
(CSE 534)
                         
Friday                               Nagarjun
(CSE 309)
     

info announcements schedule references

Announcements



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 Schedule

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


References

REQUIRED TEXTBOOK
[CLRS09] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms, 3rd Edition, McGraw-Hill, 2009

OTHER TEXTBOOKS
[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

SOME USEFUL LINKS
[L1] A compendium of NP optimization problems
[L2] ACM-SIGACT
[L4] Journals of ACM
[L5] Journals of SIAM

info announcements schedule references