social-network

Course Objectives

This course presents the fundamental techniques for designing efficient computer algorithms, proving their correctness, and analyzing their running times. We will discuss a number of topics, including greedy algorithms, divide and conquer algorithms, dynamic programming, network flow algorithms, NP completeness and computational intractability, approximation algorithms, and randomized algorithms.


Texts

  • Required: Algorithm Design, by Jon Kleinberg and Eva Tardos, Addison-Wesley, 2005.
  • Optional reference book: Introduction to Algorithms, (3rd Edition), by T. Cormen, C. Leiserson, R. Rivest, and C. Stein, McGraw Hill, 2009.

Prerequisites

CMSC 351. Each student is expected to have basic programming skills (programming with loops, pointers, structures, recursion), discrete mathematics (proof by induction, sets, permutations, combinations, and probability), understanding of basic data structures (lists, stacks, queues, trees, graphs, and heaps), knowledge of sorting algorithms (MergeSort, QuickSort, HeapSort) and basic graph algorithms (minimum spanning trees and Dijkstra's algorithm), and basic calculus (manipulation of logarithms, differentiation, integration). If there is any material that seems unfamiliar, please see me or the teaching assistant as soon as possible to head off any problems.


Course Work

Course work will consist of (around 5-6) homework assignments (about one every week and a half) and 2 exams (a midterm and a comprehensive final). Tentative weights: Homeworks: 25%, Midterm: 30%, Final: 45%. (Note that these weights are subject to change.)

The Midterm will be held in class, but the exact date is yet to be determined (probably in mid to late October), and the Final Exam will be Tuesday, Dec 15, 8:00am-10:00am.

Homeworks are to be turned by the start of class on the due date. No late homeworks will be accepted, but the lowest homework grade will be dropped. (In other words, turn in what you have by the start of class. If your schedule is too busy, just drop the homework. But, try your best to save the dropped homework for the latter half of the semester, when you might really need it.) In exceptional circumstances (illness, university business, religious observances) extensions may be granted. However, all extensions must be approved by me before the due date.

Homeworks must either be neatly written or typeset. Poorly written work will not be graded. When writing algorithms be sure not only that your solution is correct, but also that it is easy for the grader to understand why your solution is correct. Part of your grade will be based not only on correctness, but also on the clarity, simplicity, and elegance of your solution.

Some homeworks will have a special challenge problem. Points from the challenge problems are extra credit. This means that I do not consider these points until after the final course cutoffs have been set. There is no official scale to extra credit points, but each semester extra credit points usually account for at least few students getting one higher letter grade (e.g., from a B+ to A-).


Academic Dishonesty

All class work is to be done independently. It is best to try to solve problems on your own, since problem solving is an important component of the course, and exam problems are often based on modifications of homework problems. You are allowed to discuss class material, homework problems, and general solution strategies with your classmates. But, when it comes to formulating or writing solutions you must work alone. You may use free and publicly available sources, such as books, journal and conference publications, and web pages, as research material for your answers. (You will not lose points for using external sources.)

You must clearly and explicitly cite all outside sources and materials that you made use of. I consider the use of uncited external sources as portraying someone else's work as your own, and as such it is a violation of the University's policies on academic dishonesty. Instances will be dealt with harshly and typically result in a failing course grade.

Unless otherwise specified, you should assume that the UMD Code of Academic Integrity applies.


Topics

The following list of topics is very tentative. Depending on time, some topics may be added or dropped, and the order of topics may change.

Review of algorithm analysis:
Example: Stable Marriage Algorithms. Review of algorithm analysis (and summations and recurrences), review of basic graph theory and graph representations.
Graph Exploration:
DFS and BFS, connected components, topological sorting, strong components and cut vertices
Greedy Algorithms:
Interval scheduling and partitioning, scheduling to minimize lateness, greedy graph algorithms (Dijkstra and MSTs), Huffman coding
Dynamic Programming:
Weighted interval scheduling, longest common subsequences, chain matrix multiplication, shortest paths in graphs (Floyd-Warshall and Bellman-Ford)
Network Flow:
Network flows (Ford-Fulkerson), bipartite matching, circulations and applications
NP and Computational Intractability:
Polynomial-time reductions, the definition of NP, NP-complete problems
Approximation Algorithms:
Greedy algorithms and bounds on the optimum. Examples of approximation algorithms (vertex cover, travelling salesman, set cover)
Randomized Algorithms:
Routing in networks, minimum cut, universal hashing

  Return to CMSC 451 Home  —  The cool image at top of page is credited to the Web artist higyou