CSCI 270: Introduction to Algorithms and the Theory of Computing

Description

  • Intructor: David Kempe
  • Course description: The course covers the fundamentals of algorithm design and the theory of computing. Much of the work of a computer scientist is problem solving using computational artifacts (such as modern computers), and problem solving involves describing step-by-step procedures that can be followed by machines. These are called algorithms. Many fundamental techniques for algorithm design, as well as specific algorithms themselves, recur throughout all areas of computer science, and computer scientists must be able to apply design and analysis techniques to devise efficient algorithms and compare them. The flipside of algorithm design is knowing the limits of algorithm design: when are problems so intractable that they either cannot be solved at all, or can --- to the current state of scientific knowledge --- only be solved by very inefficient algorithms? Such knowledge is necessary to avoid searching for solutions to problems that simply cannot be solved. The course CSCI 270 provides an introduction to both of these complementary pieces: it covers greedy algorithms, Divide&Conquer algorithms, Dynamic Programming and their corresponding analysis techniques. It also contains an introduction to the theory of NP-completeness and computability theory. At the discretion of the instructor, it will contain a discussion of a subset of the following topics: algorithms for flows and cuts, linear programming, the role of randomization in computing, approximation algorithms, number-theory based cryptographic algorithms, and non-standard models of computing.

Syllabus

If you could not preview, download here: CSCI270_Syllabus.pdf

Personal Comments

Many students like how Professor Kempe lectures and consider this course excellent. However, due to various factors, including but not limited to the complexity of the material, the unreasonable TA-student ratio, and the academic spirit of Professor Kemp, getting an A in this course takes work.

You might be deducted for various reasons, including the necessary explanation not mentioned in class and the carelessness of the CPs (since they have to read and grade so many students). Also, there is no curve or round-up of any kind, and the final exam takes a significant portion of the grade.

Thus, not only effort but also luck is needed to get an A in this course. Anyway, if you are taking this course, good luck!