In order to be useful in practice, any computer or information system must be efficient, that is, consumes a small amount of resources, such as time and space. The efficiency of such a system relies crucially on the efficiency of the underlying algorithm(s). This course provides an introduction to the central subject of the design and analysis of efficient algorithms. In the course, we will cover
- major paradigms for algorithm design such as divide and conquer, the greedy method, dynamic programming, and randomization;
- efficient algorithms for computational problems involving graphs, strings, integers, polynomials, and geometric objects; and
- computational problems that are inherently hard to compute, and coping with such intractability if time permits.
Required textbook: "Introduction to Algorithms", 2nd Edition, by T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, MIT Press, 2001.
The prerequisite for the course is CS 1050 or an equivalent course in mathematics.
No late homeworks are allowed.
Students are encouraged to disuss course materials and homework problems in small groups. However, collaboration in homework assignments is limited to discussion of ideas only, and students must write solutions completely independently. Students are required to write the names of their collaborators, if any, on each homework assignment. Under no circumstances may a student copy solutions from any source, including another student's solutions, official solutions distributed in past terms, and solutions from courses taught at other universities. Violation of these rules may result in receiving no credit for a homework assignment, and further disciplinary actions.