About this course
This course is an introductory course on the design and analysis of algorithms. It serves as a recommended, and sometimes necessary, prerequisite for almost all courses in the area of theoretical computer science offered in the CSE department. The emphasis is on understanding some basic design principles that can be applied in a variety of algorithmic questions. That said, these principles are neither exhaustive nor applicable in all situations. The hope is that the student gets sufficient background to think in a principled manner when confronted with a new computational question.
Prerequisites: The course on programming and data structures (CS2700/CS2705) is a necessary prerequisite for the course. In particular, I will assume that you know the following (which are typically covered in CS2700/CS2705):
- The concept of an abstract data type and the difference between ADTs and data structures.
- Basic ADTs like stacks, queues, priority queues. Basic data structures like arrays, linked lists, heaps, simple BSTs and operations on them.
- The concept of pseudocode, and the difference between pseudocode and a computer program.
- Algorithms for sorting, searching, and basic algorithms on graphs.
- The concept of asymptotic analysis, and the definitions of \(O(\cdot), \Omega(\cdot)\), and \(\Theta(\cdot)\) as well as \(o(\cdot)\) and \(\omega(\cdot)\).
The course will require you to design algorithms, and then mathematically prove their correctness. There will not be any programming component for this course, though you may be required to implement a few of the algorithms if you take the lab course Object-Oriented Analysis, Implementation and Algorithms (OOAIA, CS2810).
Course contents
The course will look at some basic algorithm design techniques using examples. The contents of the course include the following topics:
- Recursion and divide-and-conquer algorithms
- Dynamic programming
- Greedy algorithms
- Graph algorithms like shortest path, minimum spanning trees
- Brief introduction to intractability
- Advanced topics (based on time): Randomization in algorithms, network flows, linear programming
The topics included above will be covered at different depths, and the order in which they are covered will also vary.
Course resources
There are many textbooks and resources (both offline and online) that cover most of the material presented in the list above. We will not be following one textbook. Our main sources of reference will be the following textbooks.
- Algorithms by Jeff Erickson - This book is freely available online and contains a large number of exercises with varying degrees of difficulty. This is a fairly recent book.
- Algorithm Design by Jon Klienberg and Eva Tardos - A slightly older textbook than the one by Erickson, this contains most of the material given in the course contents. It also contains chapters on topics that one might see in a slightly more advanced course. Copies are available in the library and the Indian edition is not too pricey (in case you are planning to buy).
- Introduction to Algorithms by Cormen ,Leiserson, Rivest and Stein (referred to as CLRS) - An old textbook, currently in its 4th edition. Copies are available in the library, and Indian editions (for the 2nd and 3rd editions) are not pricey.
- Algorithms by Dasgupta, Papadimitriou and Vazirani - Another nice book on algorithm design. Contains some topics that are not dealt properly in the three earlier books. Copies of the book are available in the library, but I am unable to find a cheap Indian edition of this book.
Apart from this, there are a lot of resources available online. We may refer to them occasionally. All these books contain a number of exercise problems for practice.