Discrete Mathematics for Algorithm and Software Design

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

Tentative Outline

• propositional logic, elements of predicate logic;
• elements of graph theory;
• algorithms on strings;
• regular expressions;
• context-free grammars and parsing algorithms.

Course Materials

• Official course program
• Preliminary (withdrawal) test
• Home assignment #1: propositional logic
• Home assignment #3 (parsing using PLY):
  • PLY examples
  • Problems:
    1. Given a propositional formula (in the usual notation, using variables, logical constants 0 and 1, and connectives /\, \/, ->, <->, ~), decide whether it is satisfiable.
    2. Translate a propositional formula into Polish notation.
    3. Design an interpreter for (a reasonable fragment of) the LoLcode language.
    4. Design an interpreter for (a reasonable fragment of) Fortran.
    5. Design an interpreter for SimplePascal (the smallest non-trivial fragment of Pascal).