COT5405: Analysis of Algorithms

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 moved to CSE534)
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

Announcements

Aug 11: Final Exam has been graded and Final grades of the course will be available in ISIS
Students of group (ii) and (iii) can see their graded exam tomorrow Aug 12, 2008 from 3.00PM to 4.00PM in CSE 309.
Students of group (i) can have thier graded exam by sending email request to the TA with a FAX#, TA will FAX their graded exam.
Aug 9: Scores and Comments about Homework 5 are available here.
Aug 7: Dr. Ungor's office is moved to CSE 534.
Aug 5: Solution of Homework 5 are available here.
Aug 1: Next week's TA office hours will be on Monday, Aug 4, 3.00PM - 5.00PM. You can submit your homework 5 during TA office hours. There there will be no office hours on Tuesday,Aug 5.
Aug 1: Final Exam All topics are included. The final exam is comprehensive with focus on the topics covered after the 2nd midterm. It will be a two-hour closed book exam. Sample exam questions will not be posted this time. You should expect an exam format similar to the midterms.
We have three groups of students registered for this class. (i) EDGE students who are not in Gainesville (ii) EDGE students who are in Gainesville (iii) On-Campus Students.
Students of group (ii) and (iii) should take in-class Exam. Date, Time and Place of Exam is Aug 8, 3.30PM-5.30PM in ROOM CSE118. Please send an email to TA Shahed Nejhum to let us know that you know date, time and place of FINAL Exam.
Students of group (i) [EDGE students not in Gainesville], should schedule 2-hour Exam Time within August 6 Wednesday 8am - August 8 Friday 5PM by making arrangements with the proctors (through EDGE officials). Once you schedule your exam with an EDGE proctor, send the TA an e-mail informing its date and time.
Jul 28: Regrade request period of Midterm-2 is July 28 to August 4. Please send email to TA if you have any questions regarding grades.
Jul 28: Solution of Midterm-2 is out.
Jul 28: Score of Midterm-2 is out here.
Students of group (ii) and (iii) can pick up their graded exam on TA office hours. (Next TA Office is on July 29)
Students of group (i) can have thier graded exam by sending email request to the TA with a FAX#, TA will FAX their graded exam.
Jul 28: Solution of Homework 4 are available here.
Jul 24: HW5 is out. It is due by Mon Aug 4 (5pm).
Jul 18: Scores and Comments about Homework 4 are available here. Please send TA email, if you have any questions on grading by July 28.
Jul 11: Two Sample Midterms are posted.
Sample-1 Fall2007 and its solution.
Sample-2 Spring2006 and its solution.
Jul 11: String Matching will not be covered in Midterm-2 Exam.
Jul 9: MidTerm Exam 2 topics include everything covered from Lecture 17 to Lecture 29 and Amortized Analysis from Lecture 15. It will be a two-hour closed book exam. Sample exam questions will be posted soon.
We have three groups of students registered for this class. (i) EDGE students who are not in Gainesville (ii) EDGE students who are in Gainesville (iii) On-Campus Students.
Students of group (ii) and (iii) should take in-class Exam. Date, Time and Place of Exam is Jul 16, 3.30PM-5.30PM in ROOM CSE118. Please send an email to TA Shahed Nejhum to let us know that you know date, time and place of MIDTERM-2.
Students of group (i) [EDGE students not in Gainesville], should schedule 2-hour Exam Time within July 15 Tuesday 8am - July 18 Friday 5PM by making arrangements with the proctors (through EDGE officials). Once you schedule your exam with an EDGE proctor, send the TA an e-mail informing its date and time.
Jul 9: Scores and Comments about Homework 3 are available here. Please send TA email, if you have any questions on grading by July 15.
Jul 9: Solution of Homework 3 are available here.
Jul 1: Regrade request period of Midterm-1 is July 2 to July 8. Please send email to TA if you have any questions regarding grades.
Jun 29: Solution of Midterm-1 is out.
Jun 20: Score of Midterm-1 is out here. Also, check your email to know your 4-digit ID.
Solution of MidTerm-1 will be available by Sunday. Please read and understand the solution before any regrade request.
Students of group (ii) and (iii) can pick up their graded exam on TA office hours. (Next TA Office is on July 1)
Students of group (i) can have thier graded exam by sending email request to the TA with a FAX#, TA will FAX their graded exam.
Jun 19: HW4 is out. It is due by Tue July 8 (5pm).
Jun 19: Due to Summer Break, HW3 deadline is extended to Jul 1 (5pm).
Jun 12: HW3 is out. It is due by Tue June 24 (5pm). Extended to July 1.
Jun 9: You can download a copy of the Midterm-I Fall 2007
Jun 7: Solution of HW2 is out.
Jun 5: MidTerm Exam I topics include everything covered from Lecture 1 to Lecture 16 (excluding Amortized Analysis). It will be a two-hour closed book exam. Please watch video lecture 16, which is the Exam Review of Fall 2007 Midterm-I. Here is another sample test: Midterm I Spring06 and its Solutions
We have three groups of students registered for this class. (i) EDGE students who are not in Gainesville (ii) EDGE students who are in Gainesville (iii) On-Campus Students.
Students of group (ii) and (iii) should take in-class Exam. Date, Time and Place of Exam is Jun 11, 3.30PM-5.30PM in ROOM CSE118. Please send an email to TA Shahed Nejhum to let us know that you know date, time and place of MIDTERM-1.
Students of group (i) [EDGE students not in Gainesville], should schedule 2-hour Exam Time within June 10 Tuesday 8am - June 13 Friday 5PM by making arrangements with the proctors (through EDGE officials). Once you schedule your exam with an EDGE proctor, send the TA an e-mail informing its date and time.
Jun 4: Solution of HW2 will be available by Saturday.
Jun 4: Grades of HW1 and HW2 are out. Please check your email.
Jun 4: Solution of HW1 is out.
May 28: HW2 is out. It is due by Tue June 3 (5pm).
May 23: HW1 is out. It is due by Tue May 27 (5pm).
May 22: The TA for this class has been replaced.
May 15: Dr. Ungor's office hours today are cancelled. Please send him e-mail if you have any questions.
May 13: There was a mistake uploading the lecture videos by the sysadmins. This shall be corrected very soon. Thanks for your patience.
Apr 15: Read the FAQs to save yourself and us some time.
Apr 15: Take the self-evaluatory quiz. Once you are done taking the test, compare your answer with the solution sketch.
Apr 15: Download the syllabus.
Apr 15: First class meeting is on May 12. However, this is a pre-recorded class and you can find all the lecture slides and videos on UF E-learning. The Video# in the schedule below refers to those on the UF E-learning website.

Schedule

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

References

Books

[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.

Links

[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

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 moved to CSE534)

Teaching Assistant: Nejhum Shahed, ( smshahed [AT] cise.ufl.edu)

TA Office Hours: 2-4pm Tuesdays (CSE309)

Catalogue number: 9189

Credit hours: 3

Announcements

Schedule

References

[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