Algorithms for problems such as sorting, graph reachability, matching etc., are at the heart of almost all real-life computer applications. Efficiency/correctness of these algorithms directly influence the overall efficiency/correctness of these applications. Hence it is important to come up with very fast and correct solutions to these basic computational problems. As the name suggests, this course has mainly two aspects: designing algorithms for basic computational problems and analyzing their correctness and efficency. These two aspects goes hand in hand with each other. Since the issues that it deals with are widely applicable in all areas of computer science, it is a core course in the computer science curriculum.
The main learning goal of the course is to teach students how to design correct and efficient algorithms. That is, through this course students will develop skills in a) employing various design methodologies to come up with new algorithms and b) using mathematical methods in analyzing the quality of algorithms. The course will also introduce students to the notion of intractability of computational problems via the theory of NP-completeness.
The emphasis of this course will be on relatively high level description of the algorithms rather than lower level implementation details. This makes it a higher, abstract level course than many other programming based courses. In particular, all the main analysis tools will be mathematical in nature.
Prerequisites.
The prerequisites for the course is CSCE 310, Data Structures and Algorithms, or equivalent background.
Textbook
Most of the lectures will be based on the well-known text book Introduction to Algorithms , by T. H. Corman, C. E. Leiserson, R. L. Rivest and S. Stein. We will distribute handouts for any additional materials that we cover.