COT5405: ANALYSIS OF ALGORITHMS
Term: Spring 2009
Time: Tuesday 10:40am-11:30am, Thursday 10:40am-12:35pm
Location: CSE107
Professor: Alper Üngör
Teaching Assistants: Hale Erten, Nejhum Shahed, Chunchun Zhao
Contact e-mail: cot5405sp09@cise.ufl.edu
Weekly Schedule:
  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 18:30 19:00 19:30
Monday                 Hale
(CSE 309)		                
Tuesday   Lecture
(CSE 107)		                         Nejhum
CSE309		 Discussion Session
Nejhum (LIT 113)
Wednesday Chunchun
(CSE 309)		                                
Thursday   Lecture
(CSE 107)		       Alper
(CSE 534)		                
Friday

info announcements schedule references

Announcements

May 4 Letter grades are posted on the E-learning system. Cut-offs will not be announced. Have a nice summer...
May 3 The final exam grades are posted. You can see your papers tomorrow (Monday, May 4 2009) between 9-10am in E309.
Apr25 Final Exam Announcement:
All topics covered will be included in the final exam. While it is comprehensive, topics covered since the 2nd midterm will be particularly focused. It is a two-hour closed book exam. Do your best to arrive early, so that we can start at 10am sharp.
There are three types of students registered for this class which determines where, when and how your exam will be administered.
(i) Students in Section 1091 must take the exam in regular classroom CSE107 on Friday May 1 at 10am.
(ii) Students in Section 4427 must take the exam in CSE 118 on Friday May 1 at 10am. Students in this section should directly go to CSE 118.
(iii) EDGE Students must schedule their exam through EDGE office as a two hour period between Friday May 1 at 8am and Tuesday May 5 at 5pm.
Here is a sample test for FINAL Exam: Spring2006
Apr24 HW6 solution is out.
Apr21 Due to travel, Dr. Üngör's office hours on Thursday are cancelled this week. We will hold regular office hours next week also.
Apr 9 HW6 is out. It is due Apr 21 Tuesday.
Apr 7 The deadline for regrading is extended till Friday, Apr 10 2009. You can submit your written regrading request to any TA.
Apr 2 Read this note to have a better idea about your standing in this course. Letter Grade Estimates is out.
Apr 2 Midterm 2 solution is out. Solutions can be seen from here: Q1,Q2 and Q3,Q4.
Please check out the solutions and grading policies, before submitting any regrading request. Deadline for submitting a regrading request is Wednesday, Apr 8 2009.
Mar24 HW5 solution is out.
Mar23 MidTerm II Announcement:
Topic covered since the first midterm (in between Feb 17 and March 24) will be the primary focus.
It is a two-hour closed book exam. Do your best to arrive early, so that we can start at 10:40am sharp.
There are three types of students registered for this class which determines where, when and how your exam will be administered.
(i) Students in Section 1091 must take the exam in regular classroom CSE107 on Thursday Mar 26 at 10:40am.
(ii) Students in Section 4427 must take the exam in MAT 151 (Matherly Hall) on Thursday Mar 26 at 10:40am. Students in this section should directly go to MAT 151.
(iii) EDGE Students must schedule their exam through EDGE office as a two hour period between Thursday Mar 26, 10:40am and Tuesday Mar 31, noon.
Mar23 Here is a sample test for MidTerm Exam II: Fall2007 and its solution.
Mar17 HW5 is out.
Mar 9 HW4 solution is out.
Mar 2 Dr. Ungor will be out of town for a conference on Mar5, Thursday. Hence, his office hour is cancelled.
The class is still on. A pre-taped lecture on Network Flows will be shown.
TAs will also be in class to pick up the HW4 submissions.
Feb24 HW4 is out. It is due Mar 5 Thursday (beginning of the class). The original deadline which was Mar 3 is extended.
Feb18 Dr. Ungor's office hour this Thursday (Feb 19) will start late at 3pm, due to a doctors appointment.
Feb17 Midterm 1 solution is out. Solutions can be seen from here: Q1 and Q5,Q2 and Q6,Q3 and Q4.
Please check out the solutions and grading policies, before submitting any regrading request. Deadline for submitting a regrading request is Wednesday, Feb 25 2009.
Feb11 HW3 solution is out.
Feb10 Dynamic Programming Problems discussed in today's discussion session are available here
Feb10 Regarding HW2 Exercise 9.3-7: "Median" is defined as value, but when we have "closest", it can be interpreted as distance to the median in terms of index or difference to the median in terms of value. If you answered in terms of the first definition above, you can come to Chunchun's office hour tomorrow or submit a regrading request on Thursday to any of the TAs.
Feb10 Please write your homework answers in order, and begin a new page for each problem. It will be greatly appreciated.
Feb 9 Some problems discussed in our discussion sessions are posted here.
Feb 9 MidTerm I Announcement:
Exam topics include all topics covered in the first 15 lectures (in between Jan 6 and Feb 5). It is a two-hour closed book exam. Do your best to arrive early, so that we can start at 10:40am sharp.
There are three types of students registered for this class which determines where, when and how your exam will be administered.
(i) Students in Section 1091 must take the exam in regular classroom CSE107 on Thursday Feb 12 at 10:40am.
(ii) Students in Section 4427 must take the exam in MAT 151 (Matherly Hall) on Thursday Feb 12 at 10:40am. Students in this section should directly go to MAT 151.
(iii) EDGE Students must schedule their exam through EDGE office as a two hour period between Thursday Feb 12, 10:40am and Tuesday Feb 17, noon. Once you schedule your exam with an EDGE proctor, send the TA an e-mail informing its date and time.
Feb 9 Here is a sample test: MidTermI_Spring06 and its solution.
Feb 6 HW2 solution is out
Feb 5 HW3 is out. It is due Feb 10 Tuesday (beginning of the class).
Feb 2 HW1 solution is out.
Jan29 HW2 is out. It is due Feb 5 Thursday (beginning of the class).
Jan26 A new email id (cot5405sp09 [AT] cise.ufl.edu) has been created.
This group email id contains the individual email ids for all the 3 TAs.
Any student intending to correspond to any of the TAs MUST send the email to this id (absolutely no exceptions).
This will keep all the TAs abreast of what's going on, and allow us to distribute the workload.
Jan26 The regular schedule for the discussion session is Tuesday 6:15pm to 7:45pm at LIT 113.
Jan26 Nejhum's office hours are moved to Tuesday. It will be between 5:30pm-6pm in CSE309.
Right after his office hour, Nejhum will lead a discussion session from 6:15pm to 7:45pm in LIT 113.
Jan19 This week's discussion will be at 5:30pm on Jan 20 Tuesday in room CSE 404.
Jan16 HW1 is out. It is due Jan 27 Tuesday (beginning of the class).
Jan15 There will be a discussion session led by Nejhum today (Jan 15 Thursday) in room CSE 404 at 5pm.
The regular schedule on discussion session will be posted next week.
Dec15 Read the FAQs to save yourself and us some time.
Dec15 Take the self-evaluatory quiz. Once you are done, compare your answers with the solution sketch.
Dec15 Download the syllabus.
Dec15 First class meeting is on Jan 6, Tuesday.

Schedule

Date Lecture Topic Assignments
Jan 6 Tu Introduction, Syllabus, Course structure.

ALGORITHMIC PARADIGMS AND DATA STRUCTURES
Jan 8 Th Algorithm Design and Analysis, The Basics
correctness, time and space complexity, greatest common divisor, 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 13 Tu Randomized Algorithms
quicksort, partitioning, worst-case, randomization, expected-time analysis
[CLRS01 Ch 5,7] (Download the lecture slides on E-learning)
Jan 15 Th Sorting in Linear Time
lower bound on comparison sorts, decision-tree model, linear time sorting, counting-sort, radix-sort
[CLRS01 Ch 8] (Download the lecture slides on E-learning) 		HW1 out
Jan 20 Tu Median and Order Statistics
selection, median, quickselect, deterministic selection
[CLRS01 Ch 9] (Download the lecture slides on E-learning)
Jan 22 Th 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
[CLRS01 Ch 28] (Download the lecture slides on E-learning)
Jan 27 Tu 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)
 HW1 due
Jan 29 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) 		HW2 out
Feb 3 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)
Feb 5 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] 		HW2 due
HW3 out
Feb 10 Tu Exam Review
More on dynamic programming, greedy choice, Spring06 MidTerm I, knapsack problem
 HW3 due
Feb 12 Th MIDTERM EXAM I
Feb 17 Tu Amortized Analysis
aggregate method, accounting method, potential method
[CLRS01 Ch 17] (Download the lecture slides on E-learning)
GRAPH ALGORITHMS
Feb 19 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]
Feb 24 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] 		HW4 out
Feb 26 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]
Mar 3 Tu Network Flows
flow network, conservation of flow, positive flow, cut, residual graph, augmenting paths
[CLRS01 Ch 26]
Mar 5 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 due
Mar 7-15 SPRING BREAK
GEOMETRIC ALGORITHMS
Mar 17 Tu 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]
HW5 out
Mar 19 Th Convex Hull Algorithms
Jarvis March (gift wrapping), Graham's Scan, Divide and Conquer
[CLRS01 Ch 33]
Miscellaneous Topics
on understanding problems, sorting vs. sortedness, computing vs. determining convex hulls
a lower bound on computing convex hull, reduction from sorting
Mar 24 Tu Closest/Furthest Point Pair Problems
repeated squaring, closest point pair problem
furthest point pair problem
[CLRS01 Ch 33] 		HW5 due
Mar 26 Th MIDTERM EXAM II
SELECTED TOPICS
Mar 31 Tu String Matching
searching patterns in text, naive algorithm, redundant comparisons
finite state machines
 [CLRS01 Ch 32]
Apr 2 Th String Matching
Knuth-Morris-Pratt algorithm, failure function
 [CLRS01 Ch 32]
COMPLEXITY AND APPROXIMATION
Apr 7 Tu 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 Th 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] 		HW6 out
Apr 14 Tu 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]
Apr 16 Th Approximation Algorithms
[CLRS01 Ch 35]
Apr 21 Tu Approximation Algorithms
[CLRS01 Ch 35] 		HW6 due
May 1 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