# Discrete Mathematics for Algorithm and Software Design

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

### Tentative Outline

- regular expressions and lexical analysis;
- context-free grammars and parsing algorithms;
- propositional logic: resolution method; elements of predicate logic;
- P vs. NP: NP-completeness of 3-SAT, polynomial algorithm for 2-SAT;
- #P; #P-completeness of #2-SAT;
- elements of graph theory.

### Course Materials

### Home assignment #1: parsing

PLY examples (in a ZIP archive)
Each student can freely choose **one** of the following tasks;
deadline: October 16, 2018.
**Interpreter for an imperative language.** Write an interpreter for the Lolcode language,
as of Specification 1.2,
with the following restriction: no functions (sect. “Functions” in the end of the specification)
allowed.
**Compiler for an imperative language.** Write a translator from the Lolcode language,
as of Specification 1.2, into
a simplified version of the three-address code (“Assembler”). Restrictions
on Lolcode: no functions; the only basic type is `NUMBR` (in particular, no Boolean operations allowed:
logical expressions used in `O RLY?` are just comparisons of integers).
**Interpreter of a functional language.** Write an interpreter of a simple functional language,
of the following specification.

### Home assignment #2: formal languages and logic

Problems for HW2. This assignment should be done **in written form** and submitted
not later than the **deadline on Wednesday, October 17** (either physically in class, or by e-mail).