Review: Week 4

1. For each of the following search methods: depth-first, breadth-first, best, beam:
   • Define them. Where possible, your definition should include terms like combiner, ranker, cost function, h(x).
   • Characterize their maximum memory and run time in terms of a search tree's branching factor "b" and search tree depth "d".
   • Comment on whether or not the algorithm s guaranteed to find an optimal solution.
   • Comment on under what conditions the the algorithm will not return an acceptable solution.
2. DFID
   1. Describe DFID
   2. Contrast DFID with breadth-first and depth-first search. Your answer should define breath-first an depth-first search, and the maximum running time and memory of each method.
   3. It can be shown that DFID visits all nodes with maximum frequency M(b,d) ≤ b^d*(1 - 1/b)^(-2) where b is the branching factor of the search space and d is the depth of the search, Here are some values from M(b,d)
      • When b=2, M(b,d) ≤ 4 * b^d
      • When b=3, M(b,d) ≤ 9/4 * b^d
      • When b=4, M(b,d) ≤ 16/9 * b^d
      • When b=5, M(b,d) ≤ 25/16 * b^d
      Using these values, describe when you would or would not recommend DFID. Make sure you explain your answers
3. ISSAMP
   1. Write down the pseudo-code for ISSAMP Make sure your code has line numbers. (Note the pseudo code for ISSAMP includes a "unit propagation" step which is a black box to you. Just assume it means "see what can be quickly inferred from the current solution").
   2. Explain the following using a paragraph or two of English and line numbers into your pseudo-code: ISSAMP search is
      • uniformed,
      • incomplete,
      • stochastic
      • does not use local search
      • uses restarts
      • and uses very little memory.
4. A* is a best-first search of graph with a *visited* list where states are sorted by "g+h". Explain all the terms in the prior sentence
5. MAXWALKSAT
   1. Write down the pseudo-code for MAXWALKSAT Make sure your code has line numbers.
   2. Explain the following using a paragraph or two of English and line numbers into your pseudo-code: MAXWALKSAT search is
      • sometimes uniformed,
      • incomplete,
      • stochastic
      • sometimes, uses local search
      • uses restarts
      • and uses very little memory.