Discrete Mathematics for Algorithm and Software Design

(NRU Higher School of Economics, CS Faculty, September – October 2017)

Tentative Outline

• 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.

Course Materials

• Official course program
• 2nd home assignment (programming).
  • Choice of tasks (pick up one):
    1. Design an interpreter for (a reasonable fragment of) the LoLcode language.
    2. 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.
    3. Given a 2-CNF (in the usual notation, e.g. (~p \/ q) /\ (q \/ r) /\ (~p \/ ~r)), decide whether it is satisfiable, in polynomial time.
    4. (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.