30516 - THEORETICAL COMPUTER SCIENCE
Course taught in English
Go to class group/s: 31
Class-group lessons delivered on campus
It is recommended to have previously taken a course on computer programming that covered basic algorithms (such as sorting algorithms) and basic data structures (such as arrays, list, and preferably hash tables and trees). The course will be mathematically rigorous, and so it is also recommended to have the ability to understand complex definitions and to follow mathematical proofs.
The course provides students with the tools to understand how the time and memory requirements of algorithms scale with the data size. Students will learn algorithmic techniques that they can apply to design efficient algorithms that scale to accommodate large data sets, and they will learn mathematical techniques to reason about their code and to guarantee correctness. The students will also learn techniques to identify problems that cannot be solved exactly with efficient algorithms, they will learn the basic foundations of cryptography, and they will be able to reason about the correctness and the security of encryption schemes and signature and authentication schemes.
- Divide-and-conquer algorithms
- Graph algorithms: connectivity
- Graph algorithms: shortest path
- Graph algorithms: minimum spanning tree
- Greedy algorithms
- Dynamic programming algorithms
- P, NP, NP-completeness
- Decidability and undecidability
- Cryptography: definitions of security
- Crytpography: encryption and authentication
- Know a number of examples of divide-and-conquer algorithms and how to solve recursive equations
- Understand how to model problems as networks, and know what network problems admit efficient algorithms
- Know how to devise an "exchange argument" to prove the correctness of a greedy algorithms
- Know how to identify a useful subproblem structure in dynamic programming
- Understand the notion of NP-completeness and its applications, and be familiar with a number of known NP-complete problems
- Understand the proof of undecidability of the halting problem, and be a familiar with a number of knonw undecidable problems
- Understand precise definitions of security in encryption and authentication, and the shortcomings of simple encryption schemes such as the ECB mode of encryption
- Identify problems that admit divide-and-conquer algorithms, devise efficient recursive algorithms for such problems, analyze the running time of such algorithms
- Apply notions such as connectivity and shortest paths to network data, and how to use depth-first-search graph visit as a framework to develop new algorithms
- Recognize problems that can be optimally solved with greedy algorithms, and be able to write efficient code for such problems and to verify correctness with an "exchange argument"
- Recognize problems that can be optimally solved with a dynamic programming approach, and be able to write efficient code for such problems
- Recognize problems that are NP-complete, and be able to devise simple NP-completeness proofs
- Recognize problems that are undecidable, and be able to devise simple undecidability proofs
- Be able to apply definitions of security in encryption and authentication, and be able to spot potential problems in a proposed cryptographic protocols
- Face-to-face lectures
The details should be erased, the homeworks will be graded now
Assessment will be the same for attending and non-attending students.
Written exam (70% of the final grade) consists of open-ended questions,
some of which will test the student's understanding of the concepts
developed during the course (for example, the ability to reason about
graphs, to reason about the correctness of a given algorithm, or to analyze
the running time of a given
algorithm) and some of which will test the student's ability to apply such
concepts to new contexts, for example their ability to devise an algorithm
for a new problem, to prove the NP-completeness of a new problem, or to
prove the undecidability of a new problem.
Students can take the first partial written exam in the middle of the
semester and complete the second partial exam at the end of the course. In
this case the weight is: 35% for the first partial exam and 35% for the
second partial exam.
Alternatively, students can take a final written exam that accounts for 70%
of the final grade.
There is no required textbook. Recommended textbooks will be communicated to the students at the start of classes. Lecture notes will be provided for selected topics.