Instructor: Instructor: Dr. István MIKLÓS

Text: handout. We will also use some chapters from Dasgupta-Papadimitriou-Vazirani: Algorithms and Miklós: Computational Complexity of Counting and Sampling.

Prerequisite: General mathematical experience up to the level of elementary algebra, calculus and combinatorics is expected. Very elementary probability theory is also needed.

Course description: The central and steady question of computer science is: “how to compute it?”. What changed during time is what we wanted to compute. In the ‘60s, decision and optimization problems were centre of interest. Nowadays, in the age of exabytes and the internet of things, we would like to mine information and knowledge from data, and want to teach computers to automatically do tasks (like classifying objects). The aim of this course is to give an overview of the most important algorithms invented in the last 60 years. There will be special emphasis to highlight the similarities between the classical and modern approaches. This course is an introductory course, however, it gets demanding quite rapidly.

Topics: