Comp210 Lab 9: Analyzing Graph-Search; Vectors

(Any questions about using read? Ask now, or forever hold your peace!)

Table of Contents

Analyzing Graph-Search

(This is an instance of the general concept of avoiding doing work twice: if we've already searched for a path from Denver and found no answer, somehow remember that fact rather than do the work over again. This is the same idea behind caching a web page.)

There were two approaches mentioned in lecture, to keep track of what cities we'd already seen.

1. Keep an accumulator of cities already seen; when we visit a city, first check that it's not already in the accumulator to avoid visiting a city twice.
2. Similar to the previous, but instead of an accumulator, keep a list already-seen, and modify this with set! as we visit new cities.
3. Within the city structure itself, add a boolean value seen?; when we visit a city, first check whether city-seen?.

Let's compare. Require the library Projects/lab9-library.ss, which contains:

(define-structure (city name nbhrs seen?))

(We provide the code, but you should be capable of writing it on your own. Note that we're dealing with cities, as well as lists of cities. So there is one function to handle cities, and another function to handle lists of cities. They happen to each call each other, which is fine.)

In reachable2, how does the size of the list already-seen act as the program runs? When visiting a city, how long does it take to find out whether you've already seen it?

When you call reachable2? twice in a row, how does it behave? What do you need to do between computations?

How does reachable2 compare with reachable3?? Time these two functions when searching for a path between sanFran and houston. (remember that time-apply expects a function of zero arguments). There are about 100 cities defined, and approximately 100²/2=5,000 edges.

Food for thought: What about approach 1, passing an accumulator around? I claim that while this approach gives the correct answer, it can be catastrophically worse than either of the two other approaches. Why? Write the code and do a small hand-eval to find out.)

Vectors in Scheme

Vectors in C

(define nums (vector 8 9 10))           int nums[] = { 8, 9, 10 };
(vector-ref nums 2)                     nums[2];
(vector-set! nums 2 1000)               nums[2] = 1000;
(vector-length nums)                    (no equivalent)

                                        int i=0, nums[3];
(define nums                            // This part must be inside a function:
  (build-vector 3                         while ( i < 3 ) {
                (lambda (i)                 nums[i] = 2*i;
                        (* 2 i))))          i = i + 1;
                                            }

The above code uses a while loop: while the condition i < 3 is true, repeatedly do the statements inside the following curly-braces. When the condition (hopefully) becomes false, continue on with whatever code follows the loop.

Exercise:Hand-evaluate the C code.

C's while-loop can be seen as a particular way of using recursion. We will see in lecture that we can write our own version of loops in Scheme, using the same ideas of recursion we've used all along.

Index-out-of-bound Errors

However, the Scheme and C handle this error in very different ways. Scheme lets you know immediately that there is an error; C doesn't! Instead, C might:

#include <stdio.h>

int main() {
  const int arrSize = 3;
  int before = 0;
  int nums[ arrSize ] = {97,98,99};
  int after = 1;

  // In a moment, you'll add some code here.

  printf( "Before is %d = 0.\n", before );
  int i = 0;
  while ( i < arrSize) {
    printf( "nums[%d] is %d.\n", i, nums[i] );
    i = i + 1;
    }
  printf( "After is %d = 1.\n", after );
  }

Now, add the following code at the indicated place:

  // ILLEGAL, OUT-OF-BOUND INDICES!
  nums[ arrSize+2 ] = 17;
  nums[ -1 ] = 19;

Exercise:

/* hasNeg:
 * Given a vector v and integer n,
 * return whether or not one of its first n elements is negative.
 * (We assume v has at least n elements.)
 */
bool hasNeg( int v[], int n ) {
  bool retVal = false;
  int i = 0;
  while ( i < n ) {
    if (...)
      retVal = ...
  }

  return retVal;
}

int main() {
  const int vSize = 10;
  int v[ vSize ];
  // fill v[0]..v[vSize] with values...


  if (hasNeg( v, vSize ))
    printf( "Some element of v is negative.\n" );
  else
    printf( "No element of v is negative.\n" );

  return 0;
  }