Induction step

We assume that the property is true for some n, and show that it is true for n+1. We select two sets of n dogs A and B such that all of the n+1 dogs occurs in at least one of the sets A or B, And there is one dog that appears in both sets (call this dog ``Rover''). Since A and B are of size n, we know from the Induction Hypothesis that the dogs in each set are the same color. Moreover, since Rover is in both sets, both sets must be the same color. So, the property holds for n+1 dogs. QED.

1.

The base case does not cover sets with no dogs (n=0), so we can't conclude that all dogs are the same color for any number of dogs.

2.

We did not mention what happens for n>1, so we have not proven the property for any number of dogs.

3.

The given Induction Step does not work when n=1, so the property does not hold for larger n.

4.

None of the above.

A number of people selected choice (b). The proof doesn't need to explicitly mention what happens for n>1, because the induction step, in combination with the base case, takes care of that. So, implicitly, this proof did mention n>1. It just had flawed reasoning.

The flaw is that the induction step does not work when n=1. Consider what would happen with the set with n+1=2 dogs when n=1. According to the induction step, there is a dog, Rover, who is in both sets. With n=1, the induction step uses sets of 1 dog each, for sets A and B.

If Rover is in both sets, then there's only one dog total (same dog in both sets). If the two sets have different dogs, then Rover doesn't have a place.

So, it's choice (c).

In C, strings are implemented as arrays. They could be implemented using linked lists, specifically a linked list of characters. In the string ``Data Structures are supercool'', the head of the list would be the letter 'D', the next node would be 'a', the next node would be 't', etc.

We could use a singly linked list or a doubly linked list. For which of the following operations, would you want to use a doubly-linked list (assuming the program performed this operation frequently)? Assume that only big-O time is significant.

1.

Find character (e.g., does some string contain the letter 'A'?)

2.

Count length of string (e.g., given ``Data'', the length is 4)

3.

Reverse string (e.g., given ``Data'', output ``ataD'')

4.

Find previous (i.e., given a pointer to a character, find the previous character)

5.

Concatenate strings (e.g., given ``Data'' and ``Structures'', output ``DataStructures'')

note: To get full credit on an answer like this in the future, you'll need to show why the other choices aren't correct. That is, you have to demonstrate that you understand not only why Find previous is difficult for singly linked lists, but also why all of the other choices are just as easy.

• Find character. Clearly, we can just follow next pointers through the list, looking for our character. So both singly and doubly linked lists are $\Theta(n)$ worst case for this.
• Count length. Like find character, we can follow next pointers, counting the number of characters in the string. So both singly and doubly linked lists are $\Theta(n)$ for this.
• Reverse string. A straightforward way to implement this is to push everything onto a stack, and then pop it off. (This does mean that you'll need to use a doubly-linked list or an array in order to implement the stack, but dynamically creating a doubly-linked list still preserves the linear time bound).

  Alternately, you can go through the list reversing next pointers, as the following (C++ style) pseudocode shows. Note that you could copy to a new singly linked list beforehand in linear time, if you were concerned about clobbering the input.

    p=listHead
    If p==NULL
      Return
    End If
    p2=p->nextPtr
    p->nextPtr=NULL // p will become the tail of the reversed list
    While p2!=NULL
      p3=p2->nextPtr
      p2->nextPtr=p
      p=p2
      p2=p3
    End While
    listHead=p
  

  So, it's $\Theta(n)$ time for doubly and singly linked lists.

• Find previous. Correct answer. For a doubly-linked list, you can follow the prev pointer in $\Theta(1)$. However, for a singly linked list, you have no choice but to walk the whole list, in $\Theta(n)$ worst case (and probably average case).

• Concatenate strings. The prev pointers of the doubly-linked list don't help. You create a new list, then walk the first input list using its next pointers, copying its nodes to the end of the new list (you'll need the tail pointer of the new list for this, but only temporarily). Then you copy the nodes from the second input list to the end of the new list. This is $\Theta(n)$ for either kind of linked list.