Discrete Mathematics for Algorithm and Software Design
(NRU Higher School of Economics, CS Faculty, September – October 2017)
- propositional logic: resolution method; elements of predicate logic;
- P vs. NP: NP-completeness of 3-SAT, polynomial algorithm for 2-SAT;
- #P-completeness of #2-SAT;
- elements of graph theory;
- regular expressions;
- context-free grammars and parsing algorithms.
- Official course program
- 2nd home assignment (programming).
- Choice of tasks (pick up one):
- Design an interpreter for (a reasonable fragment of) the LoLcode language.
- Translate a propositional formula (in the usual notation, using variables, logical constants 0 and 1,
and connectives /\, \/, ->, <->, ~) into Polish notation and compute
its value provided an evaluation of variables is given.
- Given a 2-CNF (in the usual notation, e.g. (~p \/ q) /\ (q \/ r) /\ (~p \/ ~r)), decide whether it is satisfiable,
in polynomial time.
- (a) Given a graph, find a Euler cycle or report that there is no Euler cycle in this graph.
(b) Given a planar graph (planarity is provided—you don't need to check it), provide a colouring of the vertices
of this graph into 5 colours such that adjacent vertices are of different colour.
- PLY (Python Lex&Yacc) examples, as a ZIP archive.