Course 2019-2020 a.y.

30516 - THEORETICAL COMPUTER SCIENCE

Department of Decision Sciences

Course taught in English
Go to class group/s: 31
CLEAM (6 credits - I sem. - OP  |  INF/01) - CLEF (6 credits - I sem. - OP  |  INF/01) - CLEACC (6 credits - I sem. - OP  |  INF/01) - BESS-CLES (6 credits - I sem. - OP  |  INF/01) - WBB (6 credits - I sem. - OP  |  INF/01) - BIEF (6 credits - I sem. - OP  |  INF/01) - BIEM (6 credits - I sem. - OP  |  INF/01) - BIG (6 credits - I sem. - OP  |  INF/01) - BEMACS (6 credits - I sem. - OP  |  INF/01)
Course Director:
LUCA TREVISAN

Classes: 31 (I sem.)
Instructors:
Class 31: LUCA TREVISAN


Suggested background knowledge

Strongly recommended: - Differential calculus; - Elementary graph theory; - Probability theory; - Elementary discrete mathematics; - Basic programming skills.

Mission & Content Summary

MISSION

The aim of the course is to provide students with the mathematical tools that are the basis of the theory of algorithms, along with the mathematical methods used in modern computer science applications, such as cryptography. The rigorous approach enables the students to conjugate mathematical and algorithmic thinking. The chosen topics serve both as examples of powerful theoretical results (as well as the mathematical techniques employed to obtain them) and as key problems in Data Science which is encountered in the remainder of the education program.

CONTENT SUMMARY

  • Algorithm Design: Graph algorithms, parallel and distributed algorithms, algorithmic game theory.
  • Computational Complexity: Circuit lower bounds, communication complexity, hardness of approximation.
  • Randomness in Computation: Randomized algorithms, pseudorandomness, expander graphs, error-correcting codes.
  • Application Areas: Cryptography, Privacy.

Intended Learning Outcomes (ILO)

KNOWLEDGE AND UNDERSTANDING

At the end of the course student will be able to...
  • Recognize the fundamental mathematical problems at the root of modern computer science and its key applications in Data Science.

APPLYING KNOWLEDGE AND UNDERSTANDING

At the end of the course student will be able to...
  • Master the essential theoretical techniques which are used in analysing modern computer science problems.

Teaching methods

  • Face-to-face lectures

DETAILS

Lectures.


Assessment methods

  Continuous assessment Partial exams General exam
  • Written individual exam (traditional/online)
    x

ATTENDING AND NOT ATTENDING STUDENTS

The exam has a theoretical part, assessing the students' knowledge of some fundamental results and related proof techniques, and some exercises indended to assess their ability to apply the acquired knowledge to specific circumstances.


Teaching materials


ATTENDING AND NOT ATTENDING STUDENTS

The teaching materials are communicated before the beginning of the course.

Last change 01/06/2019 18:05