20290 Algorithmics: The Foundations of Computer Science

Credits: 4 intermediate credits in Computer Science

Prerequisites: none

Required: At least 6 credits in Mathematics and 18 credits in Computer Science

Recommended: Data Structures and Introduction to Algorithms (or Data Structures)

The course is based on a translation of The Science of Computing: Exploring the Nature and Power of Algorithms, by D. Harel (Addison-Wesley, 1989), and on updates from Algorithmics: The Spirit of Computing (3rd ed.), by D. Harel and Y. Feldman (Addison Wesley, 2004).

The course surveys major topics in Computer Science, from the fundamentals of the field to advanced topics that are in the forefront of research. The basic concept discussed in the course is the algorithm – the “recipe” for writing a machine-executable process. The course does not deal with the physical structure of the computer or with specific programming languages.

The course is highly recommended for students of Computer Science because it shows the connections between the different topics studied in Computer Science courses. It is also recommended for teachers of Computer Science who need a broad yet deep perspective of the foundations of their field of expertise.

Topics: Introduction and historical overview; Algorithms and data; Programming languages; Algorithmic methods; The correctness of algorithms; The efficiency of algorithms; Inefficiency and intractability; Noncomputability and undecidability; Algorithmic universality and its robustness; Parallelism and concurrency; Probabilistic algorithms; Algorithmics and intelligence.