CMSC 451: Design and Analysis of Computer AlgorithmsSummer 2005CSI 1122  MTuWThF 9:30  10:50Instructor Srinivasan Parthasarathy 

Srinivasan Parthasarathy sri@cs.umd.edu 
AVW 4140 Office hours: MTu 11.00  12.30 
Teaching Assistant:
Denis S. Filimonov den@cs.umd.edu 
AVW 1112 Office hours: Th 3.00  5.00; F 11.00  1.00 
Required Text: Algorithm Design by Jon Kleinberg and Eva Tardos 
Note: On the day of the final, I will also hand out a sheet of paper which contains all your grades until HW4. If there are any consistencies, please contact me after the final. 

Final exam instructions: Like the midterm exam, the final is also closedbook and closednotes. Unlike the midterm, you are allowed to bring two sheets of paper (i.e., four handwritten/typed sides) for reference during the final. You may require all of 80 minutes of the class time on the day of the final, so plan on being in class early. 

Here is a sample final exam: final.pdf 

If you received a change of midterm grade, and have not emailed me about it yet, please send me an email now. 

HW5 due on Thursday, 081805 in class. Solve exercises 1 (10 points), 2 (20 points), and 6 (20 points) from Chapter 8. We are yet to define NPcompleteness. For now, you can attempt to reduce some of the well known NPcomplete problems we already considered (vertex cover, independent set, 3SAT, set cover, etc.) to the diverse subset problem (exercise 2) and Monotone satisfiability problem (exercise 6). This will be a crucial part of your solution to exercises 2 and 3. 

Project: You will be required to understand the greedy algorithm for weighted interval scheduling presented in this paper (here is the .pdf version). You will also be required to implement this greedy algorithm along with the dynamic programming algorithm we discussed in class, and compare their performance. Here is the detailed project description in .ps and .pdf. 

HW4 due on Friday, 081205 in class. Solve exercises 1, 2, and 4 from Chapter 6. Each of these exercises have many parts. The final part, which is designing the algorithm, carries 10 points, and other parts carry 5 points each. Before you provide a dynamic programming algorithm, you should setup the "recursive relation" for the optimal solution, and use this recursion in your algorithm. Review the Sections we did in class and the solved exercises in the book, before you attempt these exercises. You can expect to solve similar exercise(s) in your final exam. START EARLY! 

Midterm on Wed, 080305 in class. Midterm includes everything covered until the Friday before Midterm, i.e., until 072905. 

HW3 due on Friday, 080505 in class Solve any three of your choice from the following exercises in Chapter 5: Exercises 1, 2, 3, and 6. You do not have to solve all four but any three out of these four which is your choice. All four problems have the same maximum points. 

072205: HW2 due next Friday in class Solve the following from Chapter 4: Exercises 2, 3, 7, 13, 14, 18, and 19. Exercises 2 and 19 require material which will be covered next class. HW1 instructions are still relevant. In particular, start early. 

071505: HW1 due next Friday in class Solve the following from Chapter 3: Exercises 1, 3, 5, 7, 9, 10, 11. Problems 1 and 3 require material which will be covered next class. More instructions will follow soon. These problem require thought, so start soon. . 

Note: 071105 : One of us remarked in class today about the definition of connectivity in directed graphs. The book defines nodes u and v to be strongly connected if there is a directed path from u to v as well as from v to u. This is different from the way we defined connectivity in class today for directed graphs. We will follow the definition in the book from now on. 

071105 : Chapter 2 covers most of the prerequisite material. Please read this chapter if you are unfamiliar with (or have forgotten) the background material: this includes the "big O" notation, the asymptotic growth of functions and the running time of algorithms. The ungraded homework for today's class is the set of problems at the end of Chapter 2 and proving proposition 2 which we stated in class today without proving. 
Midterm exam : August 3rd (in class: NOTE the change in date) 

Final exam : August 19th (in class) 
Date 
Lecture 
Required Reading 
Homeworks / Handouts 
071105  M  Graphs and Tree Definitions  Chapter 3  Sec. 1 
Ungraded Homework: chapter 2 problems and proof of proposition 2. 
071205  Tu  BFS and DFS Graph Traversal  Chapter 3  Sec. 2  
071305  W  BFS and DFS Graph Traversal  Chapter 3  Sec. 2  
071405  Th  BFS and DFS Implementation  Chapter 3  Sec. 3  
071505  F  BFS and DFS Implementation; Testing "Bipartiteness"  Chapter 3  Sec. 3, Sec. 4  
071805  M  Set of all connected components; Connectivity in Directed graphs  Chapter 3  Parts of Sec. 2; Sec. 5;  Connectivity slides (.pdf) 
071905Tu  Topological Ordering in DAGs  Chapter 3  Sec. 6  Topology slides (.pdf) 
072005W  Interval Scheduling and Interval Partitioning  Sec. 4.1  Scheduling slides (.pdf) 
072105Th  Minimizing Lateness in Scheduling  Sec. 4.2  Lateness slides (.pdf) 
072205F  Dijkstra's algorithm for Shortest Paths  Sec. 4.4  
072505M  Minimum Spanning Tree  Sec. 4.5  MST slides (.pdf) 
072605Tu  Divide & Conquer: Recurrence Relations, Merge Sort  Sec. 5.1, Sec 5.2  No slides from now until the end of Dynamic Programming lecture! Refer the book. 
072705W  More recurrences; Counting inversions  Sec. 5.2, Sec 5.3  HW3 .ps .pdf 
072805Th  Finding the closest pair of points  Sec 5.4  
072905F  Integer Multiplication  Sec 5.5  
080105M  Weighted Interval Scheduling  Sec 6.1  
080205Tu  Weighted Interval Scheduling  Sec 6.1 and Sec 6.2  
080305W  Midterm  
080405Th  Segmented Least Squares + Midterm discussion  Sec 6.3  
080505F  Segmented Least Squares  Sec 6.3  HW4 posted (see announcements) 
080805M  The knapsack problem  Sec 6.4  
080905Tu  RNA Secondary Structure  Sec 6.5  Detailed project description posted (see above) 
081005W  Polynomial time reductions  Sec 8.1  
081105Th  Polytime reductions: vertex cover to independent set, vertex cover to set cover  Sec 8.1  
081205F  Reduction using gadgets: 3SAT to independent set  Sec 8.2  HW5 and sample final exam posted. 
081505M  NPCompleteness  Sec 8.3  
081505Tu  NPCompleteness  Sec 8.3  
081505W  Graph Coloring  Sec 8.7  
081505Th  Review  
081505F  Final Exam 
The study of algorithms occupies a fundamental place in computer science. Algorithmic ideas arise frequently in the several subareas within computer science as well as beyond: a small sample of these areas include computer systems and networks, data mining, computer vision, social networks, economics, and biology. In this course, we will learn to formulate several "realworld" and often ("messy") problems which arise in these areas as clean algorithmic problems, design algorithms to solve them, and learn proof techniques which guarantee that our algorithms are correct and efficient. The topics covered in the course will include graph algorithms, greedy / divide and conquer / dynamic programming based algorithms, NPcompleteness and approximation algorithms. These topics mostly correspond to Chapters 3, 4, 5, 6, 8, 9, 11, and 13 in our book (there might be some material covered in class which is not in the book and some material in the chapters which we will not study in this course).
Note: If you plan to take this course, it would be very useful for you to have a basic knowledge of algorithm analysis. If you are unsure about what this is, you should look up past course pages for CMSC 351 (which is a prerequisite for CMSC 451). In any case, it is a good idea for you to review Chapter 2 from the book, Algorithm Design.