Heuristic Selection Lab

Retrieval Prompts

1. When is working backwards more effective than forward search?
2. What is the smallest interesting case, and why is it usually not n=1?
3. What is the difference between surface similarity and structural analogy?
4. Name three heuristics from Cluster 2 and a problem type each is best for.
5. How do you test a pattern you spotted in 3 small cases?

Heuristic Classification

For each problem, name the heuristic that fits best and defend the choice in one sentence:

1. find a positive integer that leaves remainder 1 when divided by 3, remainder 2 when divided by 5, and remainder 3 when divided by 7
2. prove that among any 5 points in a unit square, two of them are at distance at most sqrt(2)/2
3. find the number of ways to place 8 non-attacking rooks on a chessboard
4. prove that the equation x^2 + y^2 = 3z^2 has no non-trivial integer solutions
5. find the longest palindromic substring of a given string
6. show that any set of n >= 1 distinct positive integers contains a subset whose sum is divisible by n
7. compute the number of integer partitions of n
8. prove that a group of people at a party always contains two people with the same number of friends at the party

Pattern-Hunting Drill

Compute the first 6 terms of each sequence by hand, then identify the pattern and write a formula or recurrence:

1. number of ways to tile a 2 x n board with dominoes
2. number of binary strings of length n with no two consecutive 1s
3. number of subsets of \{1, ..., n\} with no two consecutive elements
4. number of lattice paths from (0,0) to (n,n) using only right and up moves

After all four, write one sentence: "these problems share the structure because ..."

Working-Backwards Drill

Solve two problems entirely by working backwards, writing each step as a backward implication:

1. given three jugs of capacity 12, 7, 5 (starting full at 12, rest empty), measure exactly 6 liters in the 12-jug
2. starting from (0, 0), using moves (+1, +2) or (+2, +1), can you reach (100, 100)? If yes, find a sequence; if no, explain why

For each, include a forward-written final solution.

Special-Cases Drill

For each general claim, solve three small instances by hand, identify the structural reason the pattern holds, then state the general proof strategy:

1. in any tournament on n players, there is a player who beat everyone or is beaten by everyone via at most 1 intermediary
2. for any natural number n, n^3 - n is divisible by 6
3. the sum of the first n Fibonacci numbers equals F(n+2) - 1

Analogy Drill

For each target problem, identify a problem you have already solved that shares the abstract shape, then adapt the solution:

1. find the length of the longest common prefix of two strings (hint: think of binary search on length)
2. count the number of distinct trees (unordered, unlabeled) with n nodes (hint: think of recursion on root-subtree decompositions)
3. decide if a string of n characters is a valid balanced parenthesization (hint: running invariant)

Evidence Check

This page is complete only if you can pick the right heuristic for a fresh problem, in one sentence, and justify the pick before attempting a solution.