SubjectsSubjects(version: 945)
Course, academic year 2023/2024
   Login via CAS
Intensive course in discrete mathematics and computer science II - NDMI104
Title: Intenzivní kurz diskrétní matematiky a teoretické informatiky II
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2023
Semester: summer
E-Credits: 5
Hours per week, examination: summer s.:2/1, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: cancelled
Language: English
Teaching methods: full-time
Teaching methods: full-time
Guarantor: prof. Mgr. Zdeněk Dvořák, Ph.D.
Class: Informatika Mgr. - volitelný
Classification: Informatics > Discrete Mathematics, Theoretical Computer Science
Annotation -
Last update: RNDr. Ondřej Pangrác, Ph.D. (06.05.2019)
Intensive course on one of selected fundamental topics in discrete mathematics and computer science, part of AlgoMaNet lecture series.
Syllabus -
Last update: prof. Mgr. Zdeněk Dvořák, Ph.D. (21.12.2019)

The series of lectures will provide a tutorial on fine-grained complexity. Fine-grained complexity which emerged over the past decade maps the landscape of problems solvable in polynomial time, and provides insight into their exact asymptotic complexities. By building a formal connection between the complexity of problems like the Longest Common Subsequence and the complexity of solving NP-complete problems such as SAT it provides a plausible explanation why despite lots of effort we did not manage to improve on the trivial quadratic or cubic algorithms for such problems. The course will cover the Strong Exponential Time Hypothesis (SETH) and its variants, problems in P such as Orthogonal Vectors Problem, 3SUM, Longest Common Subsequence and many others, and exhibit a striking relationships between their complexities.

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html