This course extends the study of algorithms introduced in CS-2851. Topics covered include searching, sorting, selection, graph structures, traversal algorithms, and P/NP complete problems. Applications such as data compression, optimization problems and database indexing are also discussed. Laboratory activities include the implementation and comparison of problem-specific algorithms. (prereq: CS-2851, SE-280, MA-230) (3-2-4)
Upon successful completion of this course, the student will:
The above course description and goals were taken from the official course description.
Please review the general course policies webpage.
Introduction to Algorithms e/2, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, MIT Press and McGraw-Hill, 2001. (errata list)
Each student will be responsible for a 10 minute oral presentation of an algorithm or concept related to this course. The topic should be unique and not covered in class. A one paragraph abstract identifying the topic is due by the end of week 5. Presentations will be scheduled for week 10. Students are advised to take this assignment seriously as it is worth more than a lab grade. A typical student should plan to allocate 0.5-2 hours selecting a topic, 4 hours researching the topic, 4 hours developing a presentation, and 1 hour practicing.
Homework assignments will be given throughout the quarter. You are encouraged to work on the homework in groups, but you should not turn in any solutions that you do not understand completely (I may quiz you on what you submit). At least 25% of the midterm and final will be problems from the homework or directly related to homework problems.
Each problem will be graded on the following scale:
Unless stated otherwise, all laboratory assignments will be completed in teams of two. One lab report should be submitted for each team. All Lab assignments are worth 50 points per week (i.e., a two week lab assignment is worth 100 points).