The design and analysis of efficient algorithms on data structures for problems in sorting, searching, graph theory, combinatorial optimization, computational geometry, and algebraic computation. Algorithm design techniques: divide-and-conquer, dynamic programming, greedy method, and randomization, approximation algorithms.
CS 315 and engineering standing.
Students need to be familiar with basic data structures and algorithms. Students should be adept in programming in a modern object-oriented language.
A successful student will develop knowledge of various mathematical tools and algorithmic methods that are applicable in computer science. Specifically, students will be able to:
Direct Measures:
Students are evaluated on their work (homeworks, exams). Students receive back their homework and exams. These papers are marked to indicate problems, point out correct or better solutions, and improve the quality of presentation. Problems that turn out to be especially difficult are discussed in class during lectures.
NOTE: 100% lecture - 0% recitations
Indirect Measures:
These four specific outcomes will be evaluated on the basis of student work (homeworks, programming assignments, and exams) that will contain problems specifically addressing these outcomes. They will also be evaluated on the basis of student self-assessment of their mastery of the four outcomes performed at the end of the semester.
Possible Textbooks:
Introduction to Algorithms, Second Edition
T.H. Cormen, C.E. Leiserson, R.L. Rivest, Clifford Stein
MIT Press, 2001.
Introduction to Algorithms: A Creative Approach
U. Manber
Addison-Wesley, 1989.