Announcements

bullet

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

Final exam instructions: Like the midterm exam, the final is also closed-book and closed-notes. 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.

bullet

Here is a sample final exam: final.pdf
bullet

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

HW5 due on Thursday, 08|18|05 in class. Solve exercises 1 (10 points), 2 (20 points), and 6 (20 points) from Chapter 8. We are yet to define NP-completeness. For now, you can attempt to reduce some of the well known NP-complete problems we already considered (vertex cover, independent set, 3-SAT, 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.
bullet

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

HW4 due on Friday, 08|12|05 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 set-up 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!

bullet

Midterm on Wed, 08|03|05 in class. Midterm includes everything covered until the Friday before Midterm, i.e., until 07|29|05.
bullet

HW3 due on Friday, 08|05|05 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.

bullet

07|22|05: 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.
bullet

07|15|05: 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. . 

bullet

Note: 07|11|05 : 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. 

bullet

07|11|05 : Chapter 2 covers most of the pre-requisite 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 un-graded 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.

Important Dates

bullet

Mid-term exam  :  August 3rd    (in class: NOTE the change in date)
bullet

Final exam        :  August 19th (in class)

Lectures, reading, homeworks, and handouts

Date

Lecture

Required Reading

Homeworks / Handouts
07|11|05 - M Graphs and Tree Definitions Chapter 3 - Sec. 1

Ungraded Homework: chapter 2 problems and proof of proposition 2.
07|12|05 - Tu BFS and DFS Graph Traversal Chapter 3 - Sec. 2  
07|13|05 - W BFS and DFS Graph Traversal Chapter 3 - Sec. 2  
07|14|05 - Th BFS and DFS Implementation Chapter 3 - Sec. 3  
07|15|05 - F BFS and DFS Implementation; Testing "Bipartiteness" Chapter 3 - Sec. 3, Sec. 4
  1. HW1 .ps .pdf
  2. DFS slides (.pdf)
  3. Bipartite slides (.pdf)
07|18|05 - M Set of all connected components; Connectivity in Directed graphs Chapter 3 - Parts of Sec. 2; Sec. 5; Connectivity slides (.pdf)
07|19|05-Tu Topological Ordering in DAGs Chapter 3 - Sec. 6 Topology slides (.pdf)
07|20|05-W Interval Scheduling and Interval Partitioning Sec. 4.1 Scheduling slides (.pdf)
07|21|05-Th Minimizing Lateness in Scheduling Sec. 4.2 Lateness slides (.pdf)
07|22|05-F Dijkstra's algorithm for Shortest Paths Sec. 4.4
  1. HW2 .ps .pdf
  2. All figures on the class slides are from the book. Refer Sec 4.4
07|25|05-M Minimum Spanning Tree Sec. 4.5 MST slides (.pdf)
07|26|05-Tu 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.
07|27|05-W More recurrences; Counting inversions Sec. 5.2, Sec 5.3 HW3 .ps .pdf
07|28|05-Th Finding the closest pair of points Sec 5.4  
07|29||05-F Integer Multiplication Sec 5.5  
08|01|05-M Weighted Interval Scheduling Sec 6.1  
08|02|05-Tu Weighted Interval Scheduling Sec 6.1 and Sec 6.2  
08|03|05-W Midterm    
08|04|05-Th Segmented Least Squares + Midterm discussion Sec 6.3  
08|05|05-F Segmented Least Squares Sec 6.3 HW4 posted (see announcements)
08|08|05-M The knapsack problem Sec 6.4  
08|09|05-Tu RNA Secondary Structure Sec 6.5 Detailed project description posted (see above)
08|10|05-W Polynomial time reductions Sec 8.1  
08|11|05-Th Polytime reductions: vertex cover to independent set, vertex cover to set cover Sec 8.1  
08|12|05-F Reduction using gadgets: 3-SAT to independent set Sec 8.2 HW5 and sample final exam posted.
08|15|05-M NP-Completeness Sec 8.3  
08|15|05-Tu NP-Completeness Sec 8.3  
08|15|05-W Graph Coloring Sec 8.7  
08|15|05-Th Review    
08|15|05-F Final Exam    

 

Course Description

The study of algorithms occupies a fundamental place in computer science. Algorithmic ideas arise frequently in the several sub-areas 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 "real-world"  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, NP-completeness 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 pre-requisite for CMSC 451). In any case, it is a good idea for you to review Chapter 2 from the book, Algorithm Design.