|
|
|
|
COT5405: ANALYSIS OF ALGORITHMS |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Term: Fall 2012 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Time: Tuesday 10:40am-11:30am, Thursday 9:35am-11:30am | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Location: NEB0100 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Professor: Alper Üngör | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Teaching Assistants: Dung (David) Nguyen, Huiyuan (Celia) Zhang | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Contact e-mail: cot5405fa12@cise.ufl.edu | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Weekly Schedule (office hours):
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| info | announcements | schedule | references |
| Dec 13 | Final Exams grading is complete. The scores are uploaded on Sakai. You can see your papers tomorrow only between 10am-11:30am at my office (E534). We keep the final exam papers. Letter grades will be based on curve. Please do not send me any requests regarding letter grades. HAVE a GREAT WINTER BREAK! |
| Dec 4 | This weeks office hours for Dr. Ungor and Huiyuan are rescheduled due to travels and HW submission deadlines. Dr. Ungor's office hour will be at 2pm-4pm on Wed (E534). Huiyuan's office hour will be at 2-4pm on Friday (CSE309). Recall that your HW5 submission is due on Friday 3pm. |
| Dec 3 | As it is announced on the official UF Exam Schedule site, the Algorithms final exam will be held on Dec 11, Tuesday, at 5:30pm-7:30-pm, at our regular classroom (NEB0100). EDGE students should schedule their exams through EDGE office to be held on anytime between Dec 11, Tuesday, 5.30pm to Dec 13, Thursday, 5:30pm. |
| Nov 26 | HW5 out. It is due on Dec 7 Friday by 3pm. |
| Nov 11 | Midterm 2 is graded. Please pick up at TA's office hours. The deadline to submit regrade request is Nov 21. |
| Oct 31 | HW3 is graded. Please pick up at TA's office hours. The deadline to submit regrade request is November 7. |
| Oct 28 | HW3 solution out. |
| Oct 24 | HW4 out. It is due Nov 6 Tuesday (beginning of the class). |
| Oct 22 | Midterm1 regrade requests have been completed. Please pick up at TA's office hours. |
| Oct 20 | David's office hours are moved from Monday (Oct 22) to Friday (Oct 26) for this week only. It is still from 3PM to 5PM at E309. |
| Oct 12 | HW3 out. It is due Oct 23 Tuesday (beginning of the class). |
| Oct 1 | HW2 is graded. Please pick up at TA's office hours. The deadline to submit regrade request is Oct 10. |
| Sep 26 | HW2 solution out. |
Sep 26 | EDGE Students must schedule their exam through EDGE office as a 100 minutes time period between Thursday Sep 27, 9:35am and Monday Oct 1 8pm. Once you schedule your exam with an EDGE proctor, send the TA an e-mail informing its date and time. | Sep 26 | A draft solution for HW2 will be posted here later today after 5pm, which is the submission deadline for EDGE students. | Sep 24 | Here is a sample test: MidTermI_Spring06 and its solution. |
| Sep 23 | HW1 is graded. Please pick up at TA's office hours. The deadline to submit regrade request is Oct 1. |
| Sep 23 | HW1 solution out. |
| Sep 17 | HW2 out. It is due Sep 25 Tuesday (beginning of the class). |
| Sep 6 | HW1 out. It is due Sep 13 Thursday (beginning of the class). |
| Aug 22 | Download the syllabus. |
| Aug 22 | First class meeting is on Aug 23, Thursday. |
| Date | Lecture Topic | Assignments | |
| Aug 23 Th | Introduction, Syllabus, Course structure. | | |
| ALGORITHMIC PARADIGMS AND DATA STRUCTURES | |||
| Aug 23 Th Aug 28 Tu |
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) | ||
| Aug 30 Th |
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) | | |
| Sep 4 Tu |
Sorting in Linear Time counting-sort, radix-sort [CLRS01 Ch 8] (Download the lecture slides on e-Learning) | | |
| Sep 6 Th |
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 out |
|
| Sep 11 Tu |
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) |
| |
| Sep 13 Th | Balanced Search Trees binary search trees, red-black trees, height bound, rotations, insertion [CLRS01 Ch 12,13] (Download the lecture slides on e-Learning) Augmented Data Structures dynamic order statistics, augmentation methodology, interval trees [CLRS01 Ch 14] (Download the lecture slides on e-Learning) | HW1 due | |
| Sep 18 Tu |
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) |
HW2 out |
|
| Sep 20 Th |
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] | | |
| Sep 25 Tu | Exam Review More on dynamic programming, greedy choice, Spring06 MidTerm I, knapsack problem |
HW2 due | |
| Sep 27 Th | MIDTERM EXAM I | | |
| Oct 2-4 Tu-Th | Exam Recap review of various topics, proof techniques, lower bounds, dynamic programming, greedy algorithms |
| |
| Oct 9 Tu | Amortized Analysis aggregate method, accounting method, potential method [CLRS01 Ch 17] (Download the lecture slides on e-Learning) | | |
| GRAPH ALGORITHMS | |||
| Oct 11 Th | 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 | |
| Oct 16 Tu | 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] |
|
|
| Oct 18 Th | 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] | | |
| Oct 23 Tu | Network Flows flow network, conservation of flow, positive flow, cut, residual graph, augmenting paths [CLRS01 Ch 26] | HW3 due | |
| Oct 25 Th | 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 out | |
| Oct 30 Tu | Class cancelled for study time. Extra office hour is scheduled. | | |
| Nov 1 Th | MIDTERM EXAM II | | |
| GEOMETRIC ALGORITHMS | |||
| Nov 6 Tu | 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] | HW4 due | |
| Nov 8 Th | Closest/Furthest Point Pair Problems repeated squaring, closest point pair problem furthest point pair problem [CLRS01 Ch 33] | | |
| COMPLEXITY AND APPROXIMATION | |||
| Nov 15 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] | | |
| Nov 20 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] | | |
| Nov 22 Th | THANKSGIVING BREAK | ||
| Nov 27 Tu | 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] | HW5 out | |
| Nov 29 Th | Approximation Algorithms [CLRS01 Ch 35] | | |
| Dec 4 Tu | Approximation Algorithms [CLRS01 Ch 35] | HW5 due | |
| Dec 11 Tu | FINAL EXAM | | |
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)
Aug 2012