Taocp

I enjoy reading and analyzing The Art of Computer Programming book series. This page summarizes the notable algorithms I have studied and serves as an index for the programs I have written.

[Vol4a Section 7] Extension Question: How to find a cycle in a graph with odd length?

On page 17, Theorem B presents the algorithm for coloring a bipartite graph. This concept, derived from Exercise 48, can be implemented using a breadth-first search approach. We can slightly modify the algorithm so that during the coloring process, if any vertex has a neighbor with same color, then the two paths leading back to the starting vertex forms a cycle with odd length.

For example, if \(v\) is the starting vertex, then the following breadth-first search procedure \[ \begin{eqnarray} v(0) & \rightarrow a (1) \rightarrow b(0) \rightarrow & c(1) \\ & \searrow x(1) \rightarrow y(0) \rightarrow z(1) \nearrow & \end{eqnarray} \] will find the odd length cycle \( v \rightarrow a \rightarrow b \rightarrow c \rightarrow z \rightarrow y \rightarrow x (\rightarrow v) \).

[Vol4b Section 7.2.2.1] Dancing Links

On page 69, Algorithm X presents a backtracking algorithm based on Dancing Links, an advanced data structure. This structure is highly efficient for undo operations. One example of its use case is solving Exact Cover Problems.

See code example about solving Sudoku game. A sample output looks like:

2024-06-16 18:04:09 INFO  cmd/sudoku/main.cc:80: Problem:
+-----+-----+-----+
|8    |     |     |
|    3|6    |     |
|  7  |  9  |2    |
+-----+-----+-----+
|  5  |    7|     |
|     |  4 5|7    |
|     |1    |  3  |
+-----+-----+-----+
|    1|     |  6 8|
|    8|5    |  1  |
|  9  |     |4    |
+-----+-----+-----+
2024-06-16 18:04:09 INFO  cmd/sudoku/main.cc:90: total options count 254
2024-06-16 18:04:09 INFO  cmd/sudoku/main.cc:91: top 10 options:
2024-06-16 18:04:09 INFO  cmd/sudoku/main.cc:94:   x 0, y 1, k 1
2024-06-16 18:04:09 INFO  cmd/sudoku/main.cc:94:   x 0, y 1, k 2
2024-06-16 18:04:09 INFO  cmd/sudoku/main.cc:94:   x 0, y 1, k 4
2024-06-16 18:04:09 INFO  cmd/sudoku/main.cc:94:   x 0, y 1, k 6
2024-06-16 18:04:09 INFO  cmd/sudoku/main.cc:94:   x 0, y 2, k 2
2024-06-16 18:04:09 INFO  cmd/sudoku/main.cc:94:   x 0, y 2, k 4
2024-06-16 18:04:09 INFO  cmd/sudoku/main.cc:94:   x 0, y 2, k 5
2024-06-16 18:04:09 INFO  cmd/sudoku/main.cc:94:   x 0, y 2, k 6
2024-06-16 18:04:09 INFO  cmd/sudoku/main.cc:94:   x 0, y 2, k 9
2024-06-16 18:04:09 INFO  cmd/sudoku/main.cc:94:   x 0, y 3, k 2
2024-06-16 18:04:09 INFO  cmd/sudoku/main.cc:150: Found solution:
+-----+-----+-----+
|8 1 2|7 5 3|6 4 9|
|9 4 3|6 8 2|1 7 5|
|6 7 5|4 9 1|2 8 3|
+-----+-----+-----+
|1 5 4|2 3 7|8 9 6|
|3 6 9|8 4 5|7 2 1|
|2 8 7|1 6 9|5 3 4|
+-----+-----+-----+
|5 2 1|9 7 4|3 6 8|
|4 3 8|5 2 6|9 1 7|
|7 9 6|3 1 8|4 5 2|
+-----+-----+-----+

[Vol4b Section 7.2.2.2] Satisfiability: Backtracking Algorithms

On page 215, Algorithm B (Satisfiability by Watching) introduces an efficient lazy data structure that eliminates the need for undo operations. Each literal can exist in one of three states: true, false, or unknown. During backtracking, the state of the watched literal transitions from true to unknown, which is entirely permissible. This approach also eliminates the need for recovering linked list data structures.

A few clear issues with Algorithm B include:

• It scans each clause to find an available literal to swap with the watched literal, which is highly inefficient in terms of memory reads.
• It attempts to branch on a literal that is already forced to take a specific value due to a unit clause.

See code example about dependency resolution problem.