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