Lab 5: Heuristic Search

Part I: Proofs

Prove the following:

1. (Direct Proof Warmup) Prove that every odd integer is the difference of two square numbers.
2. (Proof by Contradiction Warmup) Prove that there is no largest rational number.
3. Prove or disprove, that, if $n^2$ is odd, then n is odd.
4. In logic, the contrapositive of a statement $p\Rightarrow q$ is defined as $\neg q \Rightarrow \neg p$. Prove or disprove that the contrapositive of a statement is equivalent to the original statement.
5. In logic, the inverse of a statement $p\Rightarrow q$ is defined as $\neg p \Rightarrow \neg q$. Prove or disprove that the inverse of a statement is equivalent to the original statement.
6. Prove or disprove that $sqrt(3)$ is irrational.
7. r is a rational number. i is an irrational number. Prove or disprove that r + i is irrational.
8. For $a,b\in \Re$, prove or disprove that $a^2 + b^2 \geq 2ab$.
9. Prove or disprove that every natural number divisible by 10 is the sum of two primes.
10. Prove or disprove that $x^3+x+1=0$ has no rational sotlusions for x
11. Prove or disprove that $x^3+x^2+1=0$ has no rational solutions for x.
12. Prove or disprove that every non-zero rational number is the product of two irrational numbers.
13. If $f,g:X\rightarrow Y$ and f and g are both injective, then prove or disprove that f composed with g is also injective.
14. Prove or disprove that $S(n)=\displaystyle\sum_{i=0}^n (i\cdot (i+1) \cdot (i+2)=\frac{n(n+1)(n+2)(n+3)}{4}$.
15. (Challenge) Show that $2! \cdot 4!\cdot 6! \cdots (2n)! \geq ((n+1)!)^n$.
16. (Challenge) The Tower of Hanoi game is one where you have three posts and n disks, originally all on one pole. They are arranged with the largest disk at the bottom, and each disk above it smaller than the disk below. Your goal is to move all the disks to another pole, with the only move being to take the top disk off of any stack, and placing it on another stack, with the restriction that a disk can only go on either an empty stack, or a stack with only larger disks. Prove that this game always has a solution for n disks. How many moves are required given an initial stack of n disks?
17. (Super extreme challenge) Catalan numbers come up in random situations. For example, given n pairs of parentheses, let $T_n$ be the number of ways they can be arranged in a valid mathematical expression. For example, with n = 3, there are 5 ways to rearrange the parentheses: ((())),(())(),(((()),(()()), and ()()(), so $T_3=5$ . We define $T_0=1$. Show that $T_n = \frac{1}{n+1} {2n \choose n}$.

Part II: Problem Formulation & Heuristics & Distances

1. (Warm-up) Explain, briefly, to a middle-school student not very familiar with computer science, the following terms: state, state space, search tree, search node, goal, action, transition model, branching factor, heuristic, and distance.
2. (Warm-up) (Russell/Norvig ex3.3.9) The missionaries and cannibals problem is usually stated as follows. Three missionaries and three cannibals are on on one side of a river, along with a boat that can hold one or two people. Find a way to get everyone to the other side without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place. This problem is famous in AI because it was the subject of the first paper that approached problem formulation from an analytical viewpoint (Amarel, 1968).
1. Formulate the problem precisely, making only those distinctions necessary to ensure a valid solution. Draw a diagram of the complete state space.
2. Implement in code, and solve the problem optimally using an appropriate search algorithm. Is it a good idea to check for repeated states?
3. Why do you think people have a hard time solving this puzzle, given that the state space is so simple?
3. Given the 8-puzzle, invent a heuristic function that is admissible. Run through A* search with that heuristic. Now, invent a heuristic function that sometimes overestimates. Show an initial state where it can lead to a suboptimal solution.
4. We talked about formulating the spell checker problem in class. Now, implement some code to represent this problem, and using the Lexicon from yesterday’s recursion problems, write a search to solve it. Note that the full lexicon is huge, so you may want to use the small one to test, or make a smaller one yourself.
5. (Challenge) Show that if a heuristic is consistent, then it is admissible.

Part III: Heuristic Searches

1. Explain, using f(n), g(n), and h(n), the difference between greedy best first search and A*.
2. If given an h*(n), construct the simplest search algorithm that optimally uses h*(n) in its search. Show that it is complete, optimal, and optimally efficient.
3. Using the same search grid as yesterday (Part II #2), trace through a run of A* search. Using the following heuristics
1. L1 norm.
3. Another heuristic of your choice.
4. (Challenge) Prove A* is optimal.

Part IV: Pathfinder, final day

For pathfinder, you have implemented several uninformed searches by now. Now implement Best-first search and A*. Again, use good design and coding principles when doing this. If you wish, you may look at any of the algorithms listed in Wikipedia’s List of Search Algorithms, and implement any you find interesting.

Once you’re done with this, you can do arbitrary searches correctly and efficiently!

Make some huge maps, clean up your user interface, find a good way of displaying the path, and go find some paths!

Part V: Pick a Project Topic

Once you find a topic, post a half-page vignette on the blog about your topic, what your initial thoughts are about what significant implementation you will do, and any information you’d like to know. I will try to post replies as soon as I can to all of them. This will be due by the end of lecture on Monday.

Make sure to check the categories “Student” and “Vignettes.”