CS71: Quiz 2 Study Guide

You are responsible for all material covered through the end of Feb 28.

You should understand the following terms and concepts:

• Basic C#
• C# Class syntax, access modifiers, object polymoprhism
• Containership and inheritance diagrams
• Exceptions
  • Syntax (Try/Catch/Throw)
  • Best practices: when to use; how to use
  • Try/Do pattern
• Specifications
  • Pre and post conditions
  • Testing
  • Declarative vs. operational
  • Deterministic vs. underdetermiined
  • Stronger vs. weaker
• Graphical User Interfaces
• Event-driven system
• Model-View-Controller pattern
• Publisher/Subscriber pattern
• Listener pattern
• Callback functions

Sample practice problems:

1. Is the following specification deterministic? Why or why not?

static int find(int[] arr, int val)
  requires: val occurs exactly once in arr
  effects: returns index i such that arr[i] = val

2. Is the following specification deterministic? Why or why not?

static int find(int[] arr, int val)
  effects: returns largest index i such that
           arr[i] = val, or -1 if no such i

3. Is the following specification deterministic? Why or why not?

static int find(int[] arr, int val)
  requires: val occurs in arr
  effects: returns largest index i such that arr[i] = val

4. Is the following specification deterministic? Why or why not?

static int find(int[] arr, int val)
  requires: val occurs in arr
  effects: returns index i such that arr[i] = val

5. Consider the following spec and implementation for find

// effects: returns largest index i such that
            arr[i] = val, or -1 if no such i
static int find(int[] arr, int val) {
    for (int i = arr.length - 1 ; i >= 0; i--) {
        if (arr[i] == val) return i;
    }
    return -1;
}

1. True or False: The following input demonstrates that find does not satisfy the spec: [ 1, 2, 2 ], 2

2. True or False: The following input demonstrates that find does not satisfy the spec. [ 1, 2, 3 ], 2

3. True or False: The following input demonstrates that find does not satisfy the spec. [ 1, 2, 2 ], 4

4. True or False: find's implementation does satisfy the spec!

6. Consider the following specification

// Requires: tiles has length 7 & contains only uppercase letters.
//           crossings contains only uppercase letters, without duplicates.
// Effects: Returns a list of strings
public static List<string> scrabble(string tiles, string crossings) {
    if (tiles.Length != 7) { throw new Exception(); }
    return new List<string>();
}

1. Which of the following are parts of the postcondition of scrabble?

• tiles has only uppercase letters
• crossings has no duplicates
• scrabble takes two arguments
• scrabble returns a list of strings

2. Which of the following are parts of the precondition of scrabble?

• tiles has length 7
• crossings is a string of uppercase letters
• scrabble’s arguments are of type String and String
• scrabble returns an empty ArrayList

3. Which parts of the spec are statically checked?

• tiles is a string of uppercase letters
• crossings has no duplicates
• when tiles.length() != 7, scrabble throws an Exception
• scrabble takes two arguments

4. Does scrabble's implementation satisfy the specification?

5. Is the following specification stronger or weaker than the original one?

// Requires: tiles has length 7 & contains only uppercase letters.
//           crossings contains only uppercase letters, without duplicates.
// Effects: Returns a list of all possible words where each word can be 
//          made by taking
//          letters from tiles and at most 1 letter from crossings. Returns 
//          empty list only if no words can be found.
public static List<string> scrabble(string tiles, string crossings) 

6. Is the following specification stronger or weaker than (e)?

// Requires: tiles has length 7.
//           crossings contains letters, without duplicates.
// Effects: Returns a list of all possible words where each word can be 
//          made by taking
//          letters from tiles and at most 1 letter from crossings. Returns 
//          empty list only if no words can be found.
public static List<string> scrabble(string tiles, string crossings) 

7. Suppose Alice writes a function to compute the gcd and Bob writes a function to test it.

// Alice writes
public static int gcd(int a, int b) {
    if (a > b) {
        return gcd(a-b, b);
    } else if (b > a) {
        return gcd(a, b-a);
    }
    return a;
}

// Bob writes
[TestMethod]
public void gcdTest() {
    Assert.AreEqual(6, gcd(24, 54));
}

1. True or False: Alice should write a > 0 in the precondition of gcd
2. True or False: Alice should write b > 0 in the precondition of gcd
3. True or False: Alice should write gcd(a, b) > 0 in the precondition of gcd
4. True or False: Alice should write a and b are integers in the precondition of gcd
5. True or False: If Alice adds a > 0 to the precondition, Bob should test negative values of a
6. True or False: If Alice does not add a > 0 to the precondition, Bob should test negative values of a

8. Consider the following function. Does the implementation satisfy the pre-condition? (Hint: what about implicit preconditions?)

// requires: nothing
// effects: Returns a list containing lowercase strings from list. 
static List<string> ToLowerCase(List<string> list)
{
   for (int i = 0; i < list.Count; i++)
   {
      list[i] = list[i].ToLower();
   }
   return list;
}

9. Consider the function from question (8). Does the client satisfy the pre-condition with the following call?

List<string> result = ToLowerCase(null);

10. What is the output of the following code?

class Talker
{
   public virtual void HandleMessage(string message)
   {
      Console.WriteLine(message);
   }
}

class Counter : Talker
{
   int _counter = 0;
   public Counter()
   {
   }

   public override void HandleMessage(string message)
   {
      Console.WriteLine(message + " : " + _counter++);
   }
}

class Program
{
   public static void Main()
   {
      Talker talker1 = new Counter();
      Talker talker2 = new Talker();

      talker1.HandleMessage("Yay!");
      talker1.HandleMessage("Yay!");
      talker2.HandleMessage("Yay!");
      talker2.HandleMessage("Yay!");
   }
}

11. What is the output of the following code?

class Fancy 
{
   public delegate void CallbackCb();
   List<CallbackCb> _cbs = new List<CallbackCb>();

   public Fancy()
   {
   }

   public void AddCallback(CallbackCb cb)
   {
      _cbs.Add(cb);
   }

   public void InvokeCallbacks()
   {
      foreach (CallbackCb cb in _cbs)
      {
         cb();
      }
   }
}

class Program
{
   public static void Function1()
   {
      Console.WriteLine("Foo #1!");
   }

   public static void Function2()
   {
      Console.WriteLine("Foo #2!");
   }

   public static void Function3()
   {
      Console.WriteLine("Foo #3!");
   }


   public static void Main()
   {
      Fancy fancy = new Fancy();
      fancy.AddCallback(Function1); 
      fancy.AddCallback(Function3); 
      fancy.AddCallback(Function2); 

      fancy.InvokeCallbacks();
   }
}

12. Draw a containership diagram for the following GTK user interface.

using Gtk;
 
class MysteryApp : Window 
{
    string text = @"All of creation in a math equation?";
    public MysteryApp() : base("Modest Mouse")
    {
        BorderWidth = 8;
        SetPosition(WindowPosition.Center);
        
        DeleteEvent += delegate { Application.Quit(); };

        Label lyrics = new Label(text);
        Add(lyrics);
        
        ShowAll();
    }

    public static void Main()
    {
        Application.Init();
        new MysteryApp();
        Application.Run();
    }

13. How do event-based applications differ from non-event driven applications?

14. Suppose we wish to build an application that keeps track of how many miles a user walks every day. This application should allow the user to record and view their data using some kind of graphical interface (such as GTK). Describe a Model-View-Controller (MVC) design for this application.