|
|
|
|
COT5405: ANALYSIS OF ALGORITHMS |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Term: Spring 2013 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Time: Tuesday 9:35am-11:30am, Thursday 10:40am-11:30am | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Location: NEB0100 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Professor: Alper Üngör | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Teaching Assistants: Serdar Ayaz, Pegah Massoudifar, Hengxing Tan | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Contact e-mail: cot5405sp13@cise.ufl.edu | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Weekly Schedule (office hours):
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| info | announcements | schedule | references |
| Mar 24 | HW4 solution is out. | Mar 21 | EDGE Students must schedule their Mid term II exam through EDGE office as a 120 minutes time period between Tuesday Mar 26, 9:35am and Thursday Mar 28 5pm. Once you schedule your exam with an EDGE proctor, send the TA an e-mail informing its date and time. |
| Mar 11 | There is no meeting in class this week (March 12 and 14) due to travel. Please watch the pre-recorded class videos posted online (on Sakai). |
| Feb 28 | HW4 is out. It is due on Tuesday, March 19. |
| Feb 26 | Midterm 1 is graded. The average of the scores is 64. The regrade requests if any should be completed in full detail on a separate piece of paper (do NOT write anything on the Exam papers.) by March 12, 5pm. You can pick up your exam papers during TAs' office hours. |
| Feb 7 | HW3 solution is out. | Feb 10 | EDGE Students must schedule their exam through EDGE office as a 120 minutes time period between Tuesday Feb 19, 9:35am and Thursday Feb Feb 21 5pm. Once you schedule your exam with an EDGE proctor, send the TA an e-mail informing its date and time. | Feb 10 | Here is a sample test: MidTermI_Spring06 and its solution. |
| Feb 7 | HW2 is graded. HW2 solution is out. |
| Feb 1 | HW3 is out. It is due on Tuesday, Feb 12. |
| Jan 29 | HW1 is graded. HW1 solution is out. |
| Jan 24 | HW2 is out. It is due on Thursday, Jan 31. |
| Jan 24 | Dr. Ungor's office hour for today is cancelled due to travel. Please send e-mail if you have any questions. |
| Jan 22 | Pegah's office hour for today is rescheduled to be at 3-5pm. |
| Jan 15 | HW1 is out. It is due on Tuesday, Jan 22. |
| Jan 1 | Download the syllabus. |
| Jan 1 | First class meeting is on Jan 8, Tuesday. |
| Date | Lecture Topic | Assignments | |
| Jan 8 Tu | Introduction, Syllabus, Course structure. | | |
| ALGORITHMIC PARADIGMS AND DATA STRUCTURES | |||
| Jan 10 Th |
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) | ||
| Jan 15 Tu |
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) |
HW1 out | |
| Jan 17 Th |
Sorting in Linear Time counting-sort, radix-sort [CLRS01 Ch 8] (Download the lecture slides on e-Learning) | | |
| Jan 22 Tu |
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) |
HW1 due | |
| Jan 24 Th |
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)
HW2 out |
| |
| Jan 29 Tu | Balanced Search Trees binary search trees, red-black trees, height bound, rotations, insertion [CLRS01 Ch 12,13] (Download the lecture slides on e-Learning) | | |
| Jan 31 Th |
Augmented Data Structures dynamic order statistics, augmentation methodology, interval trees [CLRS01 Ch 14] (Download the lecture slides on e-Learning) | HW2 due |
|
| Feb 5 Tu |
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 [CLRS01 Ch 15] (Download the lecture slides on e-Learning) |
HW3 out | |
| Feb 7 Th |
Greedy Algorithms activity selection problem, optimal substructure, greedy choice 0/1 knapsack problem, fractional knapsack problem, greedy vs. dynamic programming [CLRS01 Ch 16] |
||
| Feb 12 Tu | Review of Topics review of various topics, proof techniques, lower bounds, dynamic programming, greedy algorithms |
HW3 due | |
| Feb 14 Th | Amortized Analysis aggregate method, accounting method, potential method [CLRS01 Ch 17] (Download the lecture slides on e-Learning) |
Feb 19 Tu | MIDTERM EXAM I | |
| GRAPH ALGORITHMS | |||
| Feb 21 Th | Elementary Graph Algorithms graphs and their representations, handshaking lemma [CLRS01 Ch 22] | | |
| Feb 26 Tu |
Minimum Spanning Trees greedy algorithms, optimal substructure, greedy choice property, Prim's algorithm, correctness proof, Kruskal's algorithm [CLRS01 Ch 23] | | |
| Feb 28 Th | 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] |
HW4 out |
|
| SPRING BREAK | |||
| Mar 12 Tu | 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] | | |
| Mar 14 Th | Network Flows flow network, conservation of flow, positive flow, cut, residual graph, augmenting paths [CLRS01 Ch 26] | | |
| Mar 19 Tu | 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] | HW4 due |
|
| Mar 21 Th | Topics review. | | |
| Mar 26 Tu | MIDTERM EXAM II | | |
| GEOMETRIC ALGORITHMS | |||
| Mar 28 Th | Geometric Algorithms points, lines, line segments, polygons, triangulations, geometric objects, orientation test orthogonal range searching, range trees, line segment intersection, sweepline algorithm 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] | | |
| Apr 2 Tu | Closest/Furthest Point Pair Problems repeated squaring, closest point pair problem furthest point pair problem [CLRS01 Ch 33] | | |
| COMPLEXITY AND APPROXIMATION | |||
| Apr 4 Th | 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] | | |
| Apr 9 Tu | 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] | | |
| Apr 11 Th | NP-completeness recap, comments on complexity classes, Other complexity classes, co-NP common mistakes and missunderstandings, direction of the reduction incorrect assumptions made establishing the transformation reduction from clique problem [CLRS01 Ch 34] | | |
| Apr 16 Th | Approximation Algorithms [CLRS01 Ch 35] | | |
| Apr 18 Th | Approximation Algorithms [CLRS01 Ch 35] | | |
| Apr 23 Tu | Final Review [CLRS01 Ch 35] | | |
| April 30 | FINAL EXAM (3 pm - 5 pm) | | |
BooksLinks
[CLRS09] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms, 3rd Edition, McGraw-Hill, 2009 - REQUIRED [CLRS01] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms, 2nd Edition, McGraw-Hill, 2001 [HSR97] E. Horowitz, S. Sahni and S. Rajasekaran. Computer Algorithms , Computer Science Press, 1997 - REFERENCE
[L1] A compendium of NP optimization problems
[L2] ACM-SIGACT
[L4] Journals of ACM [L5] Journals of SIAM
| info | announcements | schedule | references |
Alper Üngör
(ungor@cise.ufl.edu)
Dec 2012