Solutions for those exercises.

Multiple Choices

1. Put a checkmark in the box corresponding to true statements.

   • Any datatype can be used for keys, but they tend to be “simpler” than the datatype used for values.
   • Two pairs (or Cells) with the same key can be stored in a dictionary, provided they have different values.
   • A collision occurs when two keys (or, in general, two pieces of data) have the same hash.
   • Open addressing and (separate) chaining are two methods to resolve collisions.
   • Clustering is what makes dictionaries process data faster.

Problem

1. Consider the implementation of “simple” dictionary SDictionary below:

   using System;
    
   public class SDictionary
   {
     private class Cell
     {
       public string Value { get; set; }
       public string Key { get; set; }
    
       public Cell(
         string keyP,
         string valueP
       )
       {
         Key = keyP;
         Value = valueP;
       }
    
       public override string ToString()
       {
         return Key + ":" + Value;
       }
     }
    
     private Cell[] table;
    
     public SDictionary(
       int size = 31
     )
     {
       table = new Cell[size];
     }
    
       public int GetIndex(string keyP, int countP)
       {
           return ((int)(keyP[0]) + countP) % table.Length;
       }
       public void Add(string keyP, string valueP)
       {
           int count = 0;
           int index = GetIndex(keyP, count);
           while (
             table[index] != null
           )
           {
               count++;
               index = GetIndex(keyP, count);
           }
           table[index] = new Cell(
             keyP,
             valueP
           );
       }
   }

   (Download this code) Remember that, for example, "Bob"[0] is 'B' and use the correspondence below between characters and their integer representation to help you (i.e., (int)'B' is 66):

   A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
   65	66	67	68	69	70	71	72	73	74	75	76	77	78	79	80	81	82	83	84	85	86	87	88	89	90

   1. Fill the table array below after the following have been performed:

      SDictionary friends = new SDictionary(11);
      friends.Add("Bob", null);
      friends.Add("Pete", null);
      friends.Add("Mary", null);
      friends.Add("Lora", null);

      0	1	2	3	4	5	6	7	8	9	10

   2. What would happen if friends.Add("Lora", null); was executed again? Is it what is expected from a dictionary?

   3. Write a ToString method for the SDictionary class, that returns a string containing all the keys and values stored in the dictionary.

   4. What would happen if we were to try to insert 12 elements in our friends object?

   5. Consider the following Delete method:

          public bool Delete(string keyP)
          {
              int count = 0;
              int index = GetIndex(keyP, count);
              bool found = false;
              while (table[index] != null && !found)
              {
                  if (table[index].Key.Equals(keyP))
                  {
                      found = true;
                      table[index] = null;
                  }
                  count++;
                  index = GetIndex(keyP, count);
              }
              return found;
          }

      (Download this code) Complete the series of instructions below such that demo.Delete(error) would return false even though the string error is the key of a value present in the demo dictionary object.

      class Program{
          static void Main(){
          SDictionary demo = new SDictionary(    ); // Complete it.
       
          string error =                            // Fill me
          // To be completed.
          Console.WriteLine($"{error} was in demo: {demo.Delete(error)}.");
          }
      }