Week 11 Tutorial — Sample Solutions

1. 1. BST
   2. No
   3. No
   4. No
   5. BST
   6. No (but would be a BST if duplicates were allowed)
2. 1. The resulting BST

   10 / \ 5 20 / \ 15 30 / 28 / 24 \ 26

   has height 5

   2. After deleting node 5:

      10 \ 20 / \ 15 30 / 28 / 24 \ 26

      After deleting node 30:

      10 \ 20 / \ 15 28 / 24 \ 26

      To delete node 20:

      • 24 is the immediate successor of 20
      • note that 24 can have no left child (do you see why?)
      • 24's right child becomes left child of its parent
      • now 24 is isolated and can replace 20

      10 \ 24 / \ 15 28 / 26

      Final tree has height 3
3. 1. Output such as the following would be possible (for 20 rolls of the die):

      25426251423232651155 Counts = {3,6,2,2,5,2}

      • the list of digits shows the sequence of numbers that are rolled
      • the count shows how often each number 1, 2, ..., 6 appeared

   2. • There are 6 outcomes of dice rolling: the numbers 1 to 6.
      • so we'll need a fixed array count of length 6 to count how many of each
      • this needs to be initialised to all zeros
      • We roll the die NROLLS times, just like we tossed the coin
      • the outcome each time will be roll = 1 + random()%6
      • this is a number between 1 and 6 (easy to see?)
      • We increment the count for this roll
      • count[roll-1]++
      • We conclude by printing the contents of the count array.

4. We pick a random number between 0 and 11 (as there are 12 letters in the given string, and they will be stored at indices 0 .. 11), and then print that element in the array string.

   srandom(1); // an arbitrary seed char *string = "hippopotamus"; int size = strlen(string); int ran = random()%size; // 0<=ran<=size-1 printf("%c\n", string[ran]);

   You can write this more concisely, which however makes reading and debugging harder:

   srandom(1); // an arbitrary seed char *string = "hippopotamus"; printf("%c\n", string[random()%strlen(string)]);

5. We pick a random number between 0 and j-i, and add that number to i. Note that we must compute random() modulo (j-i+1) because the number j-i should be included.

   srandom(1); // an arbitrary seed int ran = random()%(j-i+1); // 0<=ran<=j-i int num = i + ran; // i<=num<=j printf("%d\n", num);

6. In essence:

   • Use three pointers — say *prev,*cur,*temp — to walk through the list
   • redirect cur->next to prev in every step

     // Start: prev cur // | | // NULL [1]->[2]->[3]->[4]-> ... // // Step 1: prev cur temp // | | | // NULL [1]->[2]->[3]->[4]-> ... // // prev cur temp // | | | // NULL<-[1] [2]->[3]->[4]-> ... // // Step 2: prev cur temp // | | | // NULL<-[1] [2]->[3]->[4]-> ... // // prev cur temp // | | | // NULL<-[1]<-[2] [3]->[4]-> ... // // Step 3: prev cur temp // | | | // NULL<-[1]<-[2] [3]->[4]-> ... // // ... // Step n: prev cur temp // | | | // NULL<-[1]<- ... <-[n-1] [n]->NULL // // prev cur temp // | | | // NULL<-[1]<- ... <-[n-1]<-[n] NULL // // Finish: prev cur // | | // NULL<-[1]<- ... <-[n-1]<-[n] NULL

   • at the end, prev points to the head of the reversed list and should be returned by reverseList()