Algorithms are the soul of computing. Algorithmic thinking, unlike the very young electronic machinery it brings alive, is rooted in ancient mathematics. It can be roughly described as creating "recipes" (well defined sequences of computational steps) for getting "things" (computational problems specifying an input-output relation) "successfully" (correctly) "done" (in finite steps and time). Algorithm design and analysis provide the theoretical backbone of computer science and are a must in the daily work of the successful programmer. The goal of this course is to provide a solid background in the design and analysis of the major classes of algorithms. At the end of the course students will be able to develop their own versions for a given computational task and to compare and contrast their performance.
This course introduces basic methods for the design and analysis of efficient algorithms emphasizing methods useful in practice. Different algorithms for a given computational task are presented and their relative merits evaluated based on performance measures. The following important computational problems will be discussed: sorting, searching, elements of dynamic programming and greedy algorithms, advanced data structures, graph algorithms (shortest path, spanning trees, tree traversals), string matching, elements of computational geometry, NP completeness.
MET CS 248 Discrete Mathematics, MET CS 341 Data Structures with Java, or MET CS 342 Data Structures with C++.
New material will be presented in lecture format. Reviews, exercises and homework solutions will take place in discussion. Participation in the discussions, although not mandatory, is strongly recommended and may result in extra credit.
Weekly mandatory homework, a midterm and a final examination will provide the basis for the grade. Homework is due one week after assigned. Late homework will not be accepted unless permission by the instructor was given prior to the due date.
No predetermined scale will be used. The final grade will be assigned based on the following weighting
Cheating and plagiarism will not be tolerated. They will result in no credit for the homework or examination. This should not be understood as a discouragement for discussing the material or your particular approach to a problem with other students in the class. On the contrary - I urge you to share your thoughts, questions and solutions. Naturally, if you choose to work in a group, I will be expecting more than one and highly original solutions rather than the same mistakes.
T. H. Cormen, C. E. Leiserson, R. L. Rivest. Introduction to Algorithms The MIT Press, Cambridge, Massachusetts, 2d edition. (required).
Parberry. Problems on Algorithms Prentice Hall, Englewood Cliffs, New Jersey 07632, 1995. (recommended). Available as free download at http://hercule.csci.unt.edu/ian/books/poa.html
Metropolitan College Statement on Communication Skills
Metropolitan College students, in addition to achieving mastery of subject matter and professional terminology, must be proficient in written and spoken English in order to achieve success in their academic studies and professional careers. Please be advised that papers and oral presentations that do not meet the high normative standards of university education will be downgraded or returned for revision.
Help is available at every stage of the writing process and with oral communication and presentations. Please ask your instructor, academic advisor or check the MET website www.bu.edu/met/students. Also, please also see the Student Code of Conduct www.bu.edu/met/students/conduct_code.html