Discrete Mathematics for Algorithm and Software Design

(HSE University, CS Faculty, September – October 2019)

Tentative Outline

• propositional logic: resolution method; elements of predicate logic;
• regular expressions and lexical analysis;
• context-free grammars and parsing algorithms;
• 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

• Official course program
• Lecture notes:
  • Boolean Logic. Resolution Method
  • P and NP: Turing machines, P and NP classes, NP-completeness of SAT and 3-SAT
  • NP-completeness of the Hamiltonian path problem
  • Counting problems (#P)
• Exercises:
  • Boolean Logic
  • First-order predicate logic
  • Turing machines & Graphs
  • Polynomial computations
  • P and NP
  • Graph colorings
• Parsing with Lex & Yacc (beamer slides)
• PLY (Python Lex & Yacc) examples:
  • Polynomial simplifier
  • Calculator (from O'Reilly's Lex&Yacc book)
  • more examples

HW #2

Please bring your answers in written form to the class on Wednesday, October 10, 2019. If you are unable to attend the class, please send a scan/photo by email.

Deadline: Oct 16, 2019.

HW #1: Practice in Boolean Logic

This is a programming task. Choose one of the following two tasks and write a program which solves it.

1. Given a Boolean formula, constructed from variables using /\ (conjunction), \/ (disjunction), -> (implication), and ~ (negation), translate it into Conjunctive Normal Form andinto Disjunctive Normal Form.
2. Given a Boolean formula in 2-CNF, use the resolution method to determine whether it is satisfiable. Clauses of the 2-CNF can be of one of the two forms: α \/ β or α -> β, where α and β are literals (p or ~p, where p is a variable). The CNF is presented in the usual notation, for example: (p -> q) /\ (~r \/ s) /\ (~q -> p)

Additional Reading

• "A Compact Guide to Lex&Yacc" by Thomas Niemann