This course extends the study of algorithms introduced in CS-285. Topics include searching, sorting, selection, graph structures, and traversal algorithms. Applications such as dynamic memory management, data compression, optimization problems, and database indexing are also discussed. Laboratory activities include the implementation and comparison of problem-specific algorithms, as well as the use of generic algorithms from the C++ standard library. (prereq: CS-285, SE-280, MA-230) (3-2-4)

On successful completion of this course, the student will:

• Be able to use generic algorithms from the STL and implement additional generic algorithms.
• Be able to apply asymptotic time complexity analysis to choose among competing algorithms.
• Understand how sorting algorithms such as heapsort and quicksort work.
• Understand how graph and tree structures are implemented.
• Be familiar with engineering applications for many of the fundamental algorithms discussed in the course.
• Be familiar with dynamic programming.

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)

You will be required to complete the PSP spreadsheet for each lab assignment. The spreadsheet filename should begin with your MSOE login. In addition, you should make a hyper-link to the spreadsheet from within your report. This can be done with the following line:

<a href="385taylorPSPL1.xls">PSP data for lab 1</a>

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:

• -3 points: substantially incorrect
• 0 points: minor mistakes, unorganized, or unclear
• 3 points: Clearly presented and correct

* I would like to have lunch with you individually or as a group to get to know you better. If we eat in RWJ, housing will pick up my lunch bill. If you would prefer to eat elsewhere, we will each be responsible for our own bill. Feel free to suggest another time if the time above does not work for you.

© 2001-2006 Dr. Christopher C. Taylor

Office: CC-36C

Phone: 277-7339