Assignment 7

General

The questions for this assignment are below. Record your answers in this response document. Do not copy the questions into your response document; only fill in your answers. When you are ready to turn it in, save it to your computer as a PDF with File→Download→PDF Document. Then submit that PDF to elearn by the due date.

Searching and Sorting

    1. What is a disadvantage of linear search compared to binary search?
    2. What is needed to do a binary search that is not needed to do a linear search?

  2. Show the work needed to find 19 in this list using binary search.

    Index0123456789
    Value281219343542484950

  3. Sort this list of letter alphabetically using the following two algorithms. For each, show the state of the list after each step of the algorithm, i.e. when the sorted portion of the list has grown by one item.

    N D L Y G P W C

    1. Sort the list using insertion sort.
    2. Sort the list using selection sort.
For both problems in this section, most of the points are for the search tree produced by following the algorithm, not just finding the best path.

  1. In the map below, assume that the numbers by each line are minutes it would take to travel from one location to another. Show the search tree generated by Weighted Breadth-First Search finding the fastest path from location 1 to location 3. (This is probably easiest to do on paper and then paste in a readable picture of your work.)

    0–3 120 minutes;0–4 140 minutes;0–2 30 minutes;1–2 40 minutes;1–5 100 minutes;1–6 110 minutes;2–4 30 minutes;2–6 50 minutes;3–7 140 minutes;4–6 45 minutes;4–7 105 minutes;5–7 85 minutes;6–7 80 minutes

  2. Consider a run of Heuristic Search trying to solve an eight-puzzle, with the same goal state and heuristic cost function as in the example in the reading. The next step in the algorithm is to expand this state, which was reached after 2 moves so far and still has 3 tiles out of place.

    123
    845
    76

    Cost: 2 + 3 = 5

    Show all of the states that can be reached as a result of making one move from this state, and show their cost calculations. You do NOT need to keep going to find a full solution.

    (This is probably easiest to do on paper and then paste in a readable picture of your work.)