COT 5405: Design and Analysis of Algorithms (Fall 2010)

Instructor

Dr. Pawel Wocjan
Office: HEC Room 339
Voice: (407) 823-2844
E-mail: wocjan@eecs.ucf.edu
Web: http://www.cs.ucf.edu/~wocjan/
Office Hours:
MoWe 15:00pm - 16:15pm

Teaching Assistant

Yuan Li (E-mail:liy@cs.ucf.edu)
Office Hour: meeting by appointment

Class Meeting Room:  HEC 103
Class Meeting Time:   MoWe 16:30PM - 17:45PM
Class Meeting Dates:  23/08/2010 - 13/12/2010

Textbooks

Abbr Book Titles Authors
CLRS book Introduction to Algorithms (Third Edition) T. H. Cormen
C. E. Leiserson
R. L. Rivest
C. Stein
DPV book Algorithms S. Dasgupta
U. Vazirani

Exams

No. Exams Dates
1 First midterm exam
Solution
Oct 042010 (Mon)
2 Second midterm exam
solution
Nov 10 2010 (Wed)
3 Final exam Dec 13 2010 (Mon), 4:00pm-6:50pm

Homework Assignments

No. Assignments Solutions
1 Homework 1 (doc)
Homework 1 (pdf)
Homework 1 solution
2 Homework 2 (pdf)
Homework 2 solution
3 Homework 3 (pdf) Homework 3 solution
4 DP bonus assignment for Exam 2 DP bonus solution
5 Bonus homework --

Materials and Resources
Syllabus
Lecture 1 and 2 (by Arup Guha on 23/08 and 25/08)

Lecture 3 (01/09)

 Adjacency matrix, adjacency list Depth-first search in undirected graphs Procedures explore(G,v) and dfs(G) DFS search tree/forest Types of edges (tree and back edges) Connected components in undirected graphs Previsit and postvisit orderings

Lecture 4 (06/09)

 Depth-first search in directed graphs Types of edges (tree, forward, back, and cross edges) Topological sorting Strongly connected components

Lecture 5 (08/09)

 Algorithm for finding strongly connected components (variant in DPV book) Breadth first search

Lecture 6 (13/09)

 Algorithm for finding strongly connected components (variant in CLRS book) Dijkstra's algorithm

Lecture 7 (15/09)

 Analysis of Dijkstra's algorithm (array and heap implementations of priority queue) Bellman-Ford algorithm

Lecture 8 (20/09)

 Finding shortest paths in DAGs with negative edge weights Kruskal' algorithm, cut property

Lectrure 9 (22/09)

 Data structure for disjoint sets, union by rank Overview of path compression

Lecture 10 (27/09)

 Prim's algorithm Approximation algorithm for set cover

Lecture 11 (29/09)

 Randomized algorithm for min-cut based on Kruskal's algorithm Randomized algorithm for min-cut based on edge contraction

Lecture 12 (04/10)

 First midterm exam

Lecture 13 (11/10)

 Reading assignment: Huffman encoding and Horn formulas Shortest paths in DAGs Longest increasing subsequences Knapsack with repetition

Lecture 14 (13/10)

 Reading assignment: edit distance, chain matrix multiplication and independent sets in trees Knapsack without repetition Shortest reliable paths All-pairs shortest paths, Floyd-Warshall algorithm

Lecture 15 (18/10)

 Reading assignment: sections 7.1 and 7.2 in DPV book Dynamic programming algorithm for traveling salesman problem Flow networks (section 26.1 in CLRS book)

Lecture 16 (20/10)

 Ford-Fulkerson method Residual networks Augmenting paths Cuts of flow networks

Lecture 17 (25/10)

 Max-flow min-cut theorem Analysis of Ford-Fulkerson method

Lecture 18 (27/10)

 Analysis of Edmonds-Karp algorithm

Lecture 19 (01/11)

 Introduction to linear programming

Lecture 20 (01/11)

 Reduction of max-flow to linear programming Bipartite matching Duality

Lecture 21 (08/11)

 Overview of the simplex method

Lecture 22 (10/11)

 Second midterm exam

Lecture 23 (15/11)

 Solution of the DP problems on the second exam Dealing with NP-completeness, backtracking

Lecture 24 (17/11)

Branch-and-bound
Approximation algorithm, approximation ratio
Approximation algorithm for vertex cover
Lecture 24 (22/11)

Approximation algorithm for clustering
Approximation algorithm for metric TSP
Lecture 24 (24/11)

 Solution to LP problem on second exam Approximation for knapsack without repetition