## 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 HW1 .ps .pdf DFS slides (.pdf) 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 HW2 .ps .pdf 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.