Week 103 of 125
TAOCP 7.1.1 Boolean Basics (part 2)
Sign up or sign in to tick these off and give this week a due date.
-
Part 2 finishes 7.1.1: special classes of functions that are easy to satisfy (Horn clauses and 2SAT, also called Krom functions), monotone functions, the median/majority operation, threshold functions and symmetric functions.
Time About 8 hours this week
Why it matters
Horn clauses are the basis of Prolog and Datalog, and 2SAT is one of the few satisfiability problems solvable in linear time, a classic competitive programming trick.
Before you start
- 7.1.1 part 1
How to approach it
Implement the linear-time 2SAT algorithm with strongly connected components. Implement Horn clause satisfiability with unit propagation. Read the threshold and symmetric function material for ideas.
Exercises
Do every exercise rated 00 to 20 in your head or on paper; they are quick and they check you actually absorbed the definitions. Then pick two or three rated 20 to 25 (M or not) and grind them out fully. Attempt one M25 to M30 and give yourself a hard 90-minute cap before reading the answer. Always read the answer to every exercise you attempted, even the ones you got, because Knuth's answers often teach a second technique.
Traps
- Thinking all SAT is hard. These classes are easy, and knowing that matters.