CMSC 435 ALGORITHM ANALYSIS & DESIGN
MR 2:00 - 3:15 LT 002
Fall 2009 Text: Algorithm Design
James Ten Eyck Kleinberg & Tardos
LT 115 x2606 Addison Wesley.
e-mail: James.TenEyck@marist.edu
Office hours: Mon 3:30 - 5:30; Tue 10:00 - 12:00; Thursday 10-12, 3:30 – 4:30;
TOPIC OUTLINE FOR ALGORITHMS
1. Design and Analysis of Algorithms (read text Ch. 1)
2. Big-O Notation (and other asymptotic limits) (read text Ch. 2)
3. Depth-first and breadth-first search (read text Ch. 3)
4. Basic Graph Algorithms
5. Greedy Algorithms (read text Ch. 4)
First Exam
6. Analyzing recursive and non-recursive algorithms (writing recurrence
relations for the time complexity of a recursive algorithm) (read instructor's notes)
7. Divide and Conquer Algorithms (the Master Theorem) (read text Ch. 5)
8. Sorting Algorithms
9. Using loop invariants in the design of algorithms
10. Dynamic Programming (read text Ch 6)
Second Exam
11. NP-Completeness (read text Ch 8)
Additional Topics (Student Preparations)
12. Backtracking Algorithms (read instructor's notes)
13. Branch and Bound Technique (read instructor's notes)
14. Network Flow (read text Ch 7)
15. Solving Quantified Problems and Games in PSPACE (read text Ch 9)
16. Extending the limits of tractability (read text Ch 10)
17. Approximate Algorithms (read text Ch 11)
18. Local Search (read text Ch 12)
Objectives:
This course will emphasize the following skills:
1. The construction of algorithms using induction -- structuring the solution to a problem in terms of one or more similar problems of smaller size.
2. Using loop invariants and a goal directed approach to construct correct iterative algorithms.
3. The ability to write a relation that expresses the time complexity of a given recursive or iterative algorithm.
4. The ability to solve the relation for the time complexity of an algorithm (either recursive or iterative), and express the solution in terms of big-O and big-theta.
The ability to classify a problem as belonging to a class with a particular algorithmic approach (such as greedy, divide and conquer, dynamic programming, backtracking) and then develop an algorithm consistent with that approach.
Understanding the theoretical basis of computation and the classification of tractable and intractable problems.
The choice of topics will be based upon their appropriateness to illustrate use of the above skills, and to broaden the student's background beyond topics with which he/she already has at least some familiarity. The topics covered will consist of a set of core topics all of which will be covered and a set of additional topics which will be covered by student presentation.
Grading
The grade for this course will be based upon two exams -- together worth 30 % of the grade -- a comprehensive final (20%) that will be more heavily weighted toward the material at the end of the course, problem assignments and periodic quizzes (15%) -- both announced and unannounced -- that will test your effort with and understanding of the homework, programming assignments (15%), and student preparation of problems in topics not directly covered in the class. Teams of 3-4 students will be assigned a topic to prepare after the first exam in the course and will make a presentation that includes solved problems during the last two weeks of the semester. (20%).
Not all assigned homework will be graded; but the course material is challenging, and only those people who put in a consistent effort can expect to benefit from it. Those papers that reflect a lack of real effort and are just an attempt to throw together something to turn in will be easily recognized and discounted.
Quizzes will assess the student's regular outside preparation and his or her understanding of the material recently presented in class and in homework assignments. The exams will assess the student's understanding of a larger range of material and his/her ability to demonstrate use of an appropriate methodology on a particular problem. The programming assignments provide the student with an opportunity to evaluate empirically the run-time efficiency of an algorithm (or make a comparison between competing algorithms). The student presentation requires the student to use the literature and demonstrate an ability to understand, evaluate (for efficiency), and explain algorithmic solutions to problems not otherwise covered in class.
Attendance
Students who are not in class cannot participate in activities during that period. Missed quizzes will not be made up. Only students whose absences have been excused on or before the day of an exam will be permitted a chance to schedule a make-up.
Collaboration
Collaboration between members of a software team and the reuse of previously developed software are two tenets of modern programming practice and, hence, are to be encouraged. Plagiarism and appropriation of whole assignments from sources on the web do not in any way benefit the person involved and are unacceptable. The distinction between collaboration and plagiarism lies in the mutual contribution of all parties. I will be the final arbiter of what constitutes plagiarism in any particular instance, but you will know that you have committed plagiarism when you have wholly used the work of another without making any significant contribution to that effort yourself.
All collaboration must be indicated in assignments by citing the names of the people with whom you have collaborated. Public domain software and other material appropriated from the web must be cited. Most programs assigned for this course are the algorithmic components that may be included in a larger system. Reuse of public domain software must be limited to auxiliary components such as front ends or analysis engines. Any submitted work that is caught not citing the contributions of others will be graded zero.
Class website: http://www.academic.marist.edu/~jzbv
References
Introduction to Algorithms in Pascal
Thomas W. Parsons
Wiley 1995
Introduction to Algorithms -- A Creative Approach
Udi Manber
Addison-Wesley 1989
Algorithms from P to NP (vol. 1)
B. M. E. Moret & H. D. Shapiro
Benjamin Cummings 1990
Algorithms and Complexity
Herbert S. Wilf
Prentice-Hall 1986
The Design and Analysis of Computer Algorithms
Aho, Hopcroft, & Ullman
Addison Wesley 1974
Fundamentals of Algorithmics
Brassard & Brantley
Prentice Hall 1996
Concrete Mathematics -- A Foundation for Computer Science
Graham, Knuth, & Patashink
Addison Wesley 1990
Parallel Computing -- Theory & Practice
Michael J. Quinn
McGraw Hill 2ed (1987) 1994
The Art of Computer Programming (3 vols)
Donald Knuth
Addison Wesley latest editions 1973-1981
Algorithms
Cormen, Leiserson, Rivest, Stein
McGraw-Hill
Algorithms
Johnsonbaugh & Schaefer
Pearson (Prentice-Hall) 2004
Algorithmics, 2nd Ed.,
D. Harel
Addison-Wesley,
Foundations of Algorithms Using C++ Pseudocode
Richard Neapolitan & Kumarss Naimipour
Jones & Bartlett, 3rd ed.