# 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):
- 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.