Lecture 25: Final Review Session 1 (Quiz Q&A) - CSCI 381 Goldberg

Administrative Updates

• Today (May 4) - Review Session 1: Focused on questions from quizzes. Students were asked to text in questions by quiz number (and question number if known). This is one of two review sessions for the final.
• Wednesday (May 6) - Review Session 2: Open to any topic - material, quizzes, or concepts.
• Final Exam - Part 1 (Keyword Exam): Monday, May 11. Worth 50% of the final exam grade.
• Final Exam - Part 2 (Cumulative Material): Wednesday, May 13. Worth 50% of the final exam grade.
• After May 13, no remaining graded material.
• All quizzes’ settings have been reset and are now fully accessible on Brightspace. (Note: professors do not see Brightspace the same way students do, so accessibility issues may not be apparent to the professor.)

Study Tips for the Final

For the cumulative material portion: go over quizzes first, then lecture notes, then keywords, then external resources if time allows. For the keyword exam, focus on the keyword list. Whatever is in the course notes is the official standard - external sources may differ.

Complexity vs. Solvability

A key point to remember is that one can always solve nondeterministic problems. It is not an issue of solvability but rather one of complexity - how much resources do you need to solve it (time and space). Turing himself clearly avoided the space question because he gave us an infinite tape; so he also was concentrating on the time requirements to solve a problem.

Solvability vs. Complexity = Effectiveness vs. Efficiency

To Turing, “effective” simply means: can it be done at all? “Efficient” means: can you do it in a reasonable amount of time? These two words map directly - solvability is about effectiveness, complexity is about efficiency.

Quiz 2: Post-Quiz Review

Ackermann’s Function and the Limits of Primitive Recursion

Based on Ackermann’s function, Davis realizes that the primitive recursive definition is NOT sufficient to model all computable functions. Davis was seeking either an extra initial function and/or another mathematical technique to add to the definition so that all computable functions can be achieved. Davis concludes that NO extra initial function is necessary but one extra technique is required: Unbounded Minimization where the searching always halts.

• Bounded Minimization was already shown to be primitive recursive.
• Computable = Partially Computable + Total, i.e., it must always halt.
• Davis further shows that if one drops the guarantee that the searching must halt, then Unbounded Minimization added to the Primitive Recursive definition will obtain ALL Partially Computable functions.
• In anticipation of the requirements for Partially/Computable being based on the Primitive Recursion definition, Davis introduces the terminology Primitive Recursive Class (PRC), which means Primitive Recursive ”+”.

Karp-21: Problems That Become P When Constant 3 Is Changed to 2

In the Karp-21, how many of those problems become P if the constant 3 is changed to 2?

Problem	KARP#	Notes
3-SAT	11	On page 89, Karp indicates that 2-SAT is in P
3D Matching	17	On page 90, Karp indicates that Bipartite (2D) Matching is in P

Mathematician vs. Computer Scientist on “Variables”

A mathematician considers a “variable” to be a constant if it does not change throughout the process. If so, then in some of Karp’s problems, the “variables” k etc. would be treated as constants - but that cannot be, since as a result the search space will reduce to a polynomial size (we discussed this by CLIQUE (KARP#3)). But Karp is a computer scientist, and to a computer scientist, a “variable” is still a “variable” (and not a constant) even if it does not change throughout the process, but rather if initially, we imposed the non-change restriction on it (such as with keyword “final”).

Reduction Pathway from Root to Undirected Hamiltonian

Problem Name	KARP#
Satisfiability	1	Root (Cook’s theorem - not a Karp reduction)
Clique	3	Reduction #1
Node Cover	5	Reduction #2
Directed Hamiltonian	9	Reduction #3
Undirected Hamiltonian	10	Reduction #4

Karp-21 and Bitstring Representations

Karp-21 involves bitstrings, where no two bitstrings represent the same answer.

Step 1: Identify All Karp Problems That Possibly Store Solutions in Bitstrings

Problem Name	KARP#	Notes
Satisfiability	1	In Karp’s paper, boolean predicates must have boolean inputs
SAT-11	11
0/1 Integer Programming	2
Knapsack	18
Partition	20
Max Cut	21

Step 2: Remove Problems That Generate Two Bitstrings Representing the Same Solution

Partition and Max Cut involve two sets but it does not matter whether a subgroup of elements are placed in set#1 or set#2 - both situations will yield the same solution. (In fact mathematically, this situation would be a Partition - see last question below.) The remaining 4 problems (Satisfiability, SAT-11, 0/1 Integer Programming, Knapsack) each yield a unique bitstring per solution.

Knapsack is a notable case: although there is implicitly a second set (the elements left out), the problem only asks which elements go into the knapsack, so each element maps to exactly one bit (1 = included, 0 = excluded). As long as elements are distinct, each bitstring represents a different selection. The other four problems each bitstring yields a different solution.

Minimum Spanning Tree and Steiner Tree

Problem	KARP#	Notes
Minimum Spanning Tree	-	Karp mentions this on the bottom of page 89 (MST)
Steiner Tree	16

Steiner Tree is in essence a MST problem. The difference is that it considers nodes that are not provided by the ROI (region of interest). For example:

Node 17 is outside our ROI. The cost within our ROI to go from Node 18 to Node 19 is 100. But, if we relaxed the boundary imposed by the ROI, and went from Node 18 -> Node 17 -> Node 19, then the cost would be 10+20 = 30, much less. Searching outside the ROI boundary temporarily is termed relaxation in AI.

In the modern definition of Steiner Tree, nodes like 17 that lie outside the region of interest are called ghost points - they do not exist in the original input but are created (or considered) in order to reduce the total travel cost.

k-Partitions in Karp-21

The following problems involve k-partitions:

Problem	KARP#
Chromatic Number	12
Partition	20
Max Cut	21

The goal in Chromatic Number is to assign a paint (number) to each vertex such that the edges do not connect vertices of the same paint color (number). Thus, the paints (paint numbers) have a subset of vertices associated with each color (number) and in essence partition the vertices into k subsets.

As mentioned above, Partition (KARP#20) and Max Cut (KARP#21) are better suited by the partition structure than a bitstring structure alone, since there would be two different bitstrings that would encode the same situation. For example, for Partition, if the elements were 10, 20, 30, 60, both the bitstring 1110 and 0001 would encode the same situation. Because we can call the first subgroup of elements group#0 and the second group group#1 (so that group#0 = {10, 20, 30} and group#1 = {60}), but we could also call the first group as group#1 and the second as group#0 (so that group#0 = {60} and group#1 = {10, 20, 30}). However, this situation is better suited by the mathematical structure of partitions: $\{\{10, 20, 30\}, \{60\}\}$, because this is mathematically the same partition as $\{\{60\}, \{10, 20, 30\}\}$.

Note: while these would be the same partition, they would not be the same surjective mapping:

Input	Onto
10	0
20	0
30	0
60	1

Input	Onto
60	0
10	1
20	1
30	1

These are not the same surjective mapping (the output is which group or box to place the inputted elements into).

The same exact discussion applies to Max Cut (Karp#21), where the vertices of a graph are split into two groups (subsets) such that the sum of the weighted edges between them is maximum as compared to that of any other groupings of the vertices. The point is that whether we call the 1st group group#0 and the second group group#1 or vice versa will not change the result - they both will be the same partition.

Quiz 3: Post-Quiz Review

Godel and Davis Encodings of $\langle X, Y \rangle$

Given $X = 8$ and $Y = 18$:

• Godel: $\langle X, Y \rangle_g = 2^X \cdot (2Y + 1)$
• Davis: $\langle X, Y \rangle_d = \langle X, Y \rangle_g - 1$

Davis subtracts one because in his view Turing considers mapping in terms of memory configuration and not numerical value per se. As such, the memory configuration of all 0s has to always be mapped. $\langle X, Y \rangle_g$ is always greater than 1, which makes it a partial function since memory configurations are encoded by the natural numbers $N = \{0, 1, \ldots\}$.

$$\langle 8, 18 \rangle_d = 2^8 \cdot (2 \cdot 18 + 1) - 1 = 256 \cdot 37 - 1 = 9471$$

Godel Length Encoding (GLE)

Given the sequence: 35, 36, 11, 17, 30.

GLE = Godel Length Encoding. GLE also historically inspired RLE (Run-Length Encoding), which was introduced for image compression and exploits long runs of similar bits. The reason Godel and Turing were interested in encodings was two-fold:

• Maintain a snapshot of the computer at time $t$ (which step up to, encoding of all memory). These two numbers represent the “state” of the computation during runtime. With these two numbers, one could save and restart a computation.
• Encode lines of a program (Godel was interested in lines of logic).

The GLE encodes each value as a count of 0s in unary (Base 1), with 1-markers used as separators:

Total $= (35 + 36 + 11 + 17 + 30) + 6 \text{ markers} = 129 + 6 = 135$

Note: the data itself is base 1 (unary - only 0s), but the overall encoding is base 2 because the marker (1) is needed as a separator. The marker is not part of the data.