30398 - FUNDAMENTALS OF COMPUTER SCIENCE
Course taught in English
Go to class group/s: 25
The aim of the course is to provide students with the essential mathematical tools that are the basis of the theory of algorithms, along with a general introduction to the different classes of algorithms and data structures, and to the theory of computational complexity.
As part of the course, students are introduced to programming, starting from the basics and leading up to the implementation of data structures and algorithms discussed in the theoretical part of the course. The programming language used is Python, especially suited for a general understanding of programming techniques.
- Introduction to the notion of algorithms in Computing.
- Analyzing algorithms, growth functions and asymptotic notation.
- Recurrences and generating functions. Case study: Divide-and-Conquer algorithms.
- Probabilistic Analysis and Randomized Algorithms. Case study: Quicksort.
- Elementary Data Structures and Hash tables.
- Introduction to graph theory and Elementary Graph Algorithms (Minimum Spanning Trees, Single-Source Shortest Paths, Dijkstra’s algorithm and Karger’s randomized algorithm for the Minimum Cut problem).
- Introduction to computational complexity and NP-completeness.
- Introduction to programming. Python language.
- Implementation of data structures and algorithms.
- 2 written partial exams (max 15 points + max 16 points).
- a general written exam (max 31 points).
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, et al., Introduction to Algorithms, MIT, 3rd edition.
- A.B. Downey, Think Python, O'Reilly Media.
- C. Moore, S. Mertens, The Nature of Computation, Oxford (optional).
- Elementary differential calculus.
- Basic probability theory.