CMSI 282 Data Structures and Algorithms II
Home Page and Course Syllabus
spring, 2009
Brief contents
- Personnel
- Professor: Philip Dorin - Doolan 102 - (310) 338-2832 - pdorin@lmu.edu
- Secretary: Jacqi Davis - Doolan 101 - (310) 338-7351 - jadavis@lmu.edu
- Lectures: Tuesdays and Thursdays, 1:35-2:50 pm
- Objectives and Topics
- We will build upon the material of CMSI 281 to investigate algorithm paradigms, with an emphasis on combinatorial search. Among other things, we will look at divide-and-conquer algorithms, greedy methods, dynamic programming, randomized algorithms, some modern heuristics (e.g., genetic programs, simulated annealing), problems on strings (such as string matching and determining longest common subsequences), advanced sorts and order statistics, how to generate combinatorial objects, graph algorithms, and some computational geometry, with a little cake-cutting thrown in for good measure.
- A major theme of the course is the notion of algorithm paradigms which transcend specific problems to serve as more general program models.
- Here's a superset of the topics covered in this course.
- Prerequisites, Coursework, and Grading
- The prerequisite course is CMSI 281 (Data Structures and Algorithms I).
- Expect (roughly) bi-weekly assignments that include problems to be worked out, proofs, and, of course, lots of programming.
- There will be a two-hour final exam, 11:00 am - 1:00 pm, Thursday, May 7.
- Refer to the LMU Bulletin for a description of the grading system.
- Textbooks and References
- There are appropriate textbooks, but- quite intentionally- none has been ordered for the LMU Bookstore.
In a nutshell, several excellent books could easily serve this purpose, e.g., Cormen, Leiserson, Rivest, and Stein;
Dasgupta, Papdimitriou, and Vazirani; Kleinberg and Tardos; Levitin; Aho, Hopcroft, and Ullman, which is somewhat dated,
but still outstanding; and Skiena). There are also several useful "auxiliary" books, including Gonick and Wheelis; and, Robertson and Webb.
(I will have more to say about textbooks at the initial class meeting.)
- Here's an annotated list of references
- Problem Sets
Revised: April 24, 2009