Educational Materials

Static Electricity

Use the code below to answer the following questions.

public class Pokemon {
  public String name;
  public int level;
  public static String trainer = "Ash";
  public static int partySize = 0;

  public Pokemon(String name, int level) {
    this.name = name;
    this.level = level;
    this.partySize += 1;
  }

  public static void main(String[] args) {
    Pokemon p = new Pokemon("Pikachu", 17);
    Pokemon j = new Pokemon("Jolteon", 99);
    System.out.println("Party size: " + Pokemon.partySize);
    p.printStats();
    int level = 18;
    Pokemon.change(p, level);
    p.printStats();
    Pokemon.trainer = "Ash";
    j.trainer = "Brock";
    p.printStats();`
  }

  public static void change(Pokemon poke, int level) {
    poke.level = level;
    level = 50;
    poke = new Pokemon("Voltorb", 1);
    poke.trainer = "Team Rocket";
  }

  public void printStats() {
    System.out.println(name + " " + level + " " + trainer);
  }
}
    

1. Write what would be printed after the main method is executed.
2. On line 28, we set level equal to 50. What level do we mean? An instance variable of the Pokemon class? The local variable containing the parameter to the change method? The local variable in the main method? Something else?
3. If we were to call Pokemon.printStats() at the end of our main method, what would happen?

"Senior class"

For each line in the main method of our testPeople class, if something is printed, write it next to the line. If the line results in an error, write next it whether it is a compile time error or runtime error, and then proceed as if that line were not there.

public class Person {
    public String name;
    public int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    public void greet(Person other) {
        System.out.println("Hello, " + other.name);
    }
}


public class Grandma extends Person {

    public Grandma(String name, int age) {
        super(name, age);
    }
    
    @Override
    public void greet(Person other) {
        System.out.println("Hello, young whippersnapper");
    }
    
    public void greet(Grandma other) {
        System.out.println("How was bingo, " + other.name + "?");
    }
}

public class testPeople {
    public static void main(String[] args) {
        Person n = new Person("Neil", 12);
        Person a = new Grandma("Ada", 60);
        Grandma v = new Grandma("Vidya", 80);
        Grandma al = new Person("Alex", 70);
        n.greet(a);
        n.greet(v);
        v.greet(a);
        v.greet((Grandma) a);
        a.greet(n);
        a.greet(v);
        ((Grandma) a).greet(v);
        ((Grandma) n).greet(v);
    }
}

ADT Matchmaking

Match each task to the correct Abstract Data Type for the job by drawing a line connecting matching pairs.

Runtime Analysis on Disjoint Sets

A Side of Hashbrowns

We want to map food items to their yumminess. We want to be able to find this information in constant time, so we've decided to use java's built-in HashMap class! Here, the key is a String representing the food item and the value is an int yumminess rating.

For simplicity, let's say that here a String's hashcode is the first letter's position in the alphabet (A = 0, B = 1... Z = 25). For example, the String "hashbrown" starts with "h", and "h" is 7th letter in the alphabet (0 indexed), so the hashCode would be 7. Note that in reality, a String has a much more complicated hashCode() implementation.

Our HashMap will compute the index as the key's hashcode value modulo the number of buckets in our HashMap. Assume the initial size is 4 buckets, and we double the size our HashMap as soon as the load factor reaches 3/4.

a) Draw what the HashMap would look like after the following operations.

HashMap<Integer, String> hm = new HashMap<>();
hm.put("Hashbrowns", 7);
hm.put("Dim sum", 10);
hm.put("Escargot", 5);
hm.put("Brown bananas", 1);
hm.put("Burritos", 10);
hm.put("Buffalo wings", 8);
hm.put("Banh mi", 9);

b) Do you see a potential problem here with the behavior of our hashmap? How could we solve this?

A Tree's Take on Graphs

Your friend at Stanford has made some statements about graphs, but you believe they are all false. Provide counterexamples to each of the statements below:

• "Every graph has one unique MST."
• "No matter what heuristic you use, A* search will always find the correct shortest path."
• "If you add a constant factor to each edge in a graph, Dijkstra's algorithm will return the same shortest paths tree."

Minimalist Moles

Mindy the mole wants to dig a network of tunnels connecting all of their secret hideouts. There are a set few paths between the secret hideouts that Mindy can choose to possibly include in their tunnel system, shown below. However, some portions of the ground are harder to dig than others, and Mindy wants to do as little work as possible. In the diagram below, the numbers next to the paths correspond to how hard that path is to dig for Mindy.

How can Mindy figure out a tunnel system to connect their secret hideouts while doing minimal work?

Extra: Find a valid MST for the graph above using Kruskal's algorithm, then Prims. For Prim's algorithm, take A as the start node. In both cases, if there is ever a tie, choose the edge that connects two nodes with lower alphabetical order.

Extra: Are the above MSTs different or the same? Is there a different tie-breaking scheme that would change your answer?

The Shortest Path To Your Heart

For the graph below, let g(u, v) be the weight of the edge between any nodes u and v. Let h(u, v) be the value returned by the heuristic for any nodes u and v.

Below, the pseudocode for Dijkstra's and A* are both shown for your reference throughout the problem.

function dijkstrasAlgorithm:
  PQ = new PriorityQueue()
  PQ.add(A, 0)
  PQ.add(v, infinity) # (all nodes except A).

  distTo = {} # map
  distTo[A] = 0
  distTo[v] = infinity # (all nodes except A).

  while (not PQ.isEmpty()):
    popNode, popPriority = PQ.pop()
    for child in popNode.children:
      if PQ.contains(child):
        potentialDist = distTo[popNode] + edgeWeight(popNode, child)
        if potentialDist < distTo[child]:
          distTo.put(child, potentialDist)
          PQ.changePriority(child, potentialDist)
    

function aStarSearch:
  PQ = new PriorityQueue()
  PQ.add(A, h(A))
  PQ.add(v, infinity) # (all nodes except A).

  distTo = {} # map
  distTo[A] = 0
  distTo[v] = infinity # (all nodes except A).

  while (not PQ.isEmpty()):
    poppedNode, poppedPriority = PQ.pop()
    if (poppedNode == goal): terminate

    for child in poppedNode.children:
      if PQ.contains(child):
        potentialDist = distTo[poppedNode] + edgeWeight(poppedNode, child)
        if potentialDist < distTo[child]:
          distTo.put(child, potentialDist)
          PQ.changePriority(child, potentialDist + h(child))
    

Run Dijkstra's algorithm to find the shortest paths from A to every other vertex. You may find it helpful to keep track of the priority queue. We have provided a table to keep track of best distances, and the edge leading to each vertex on the currently known shortest paths.

Extra: Given the weights on the graph above, as well as the heuristic values listed below, what path would A* search return, starting from A and with G as a goal?

• h(A, G) = 7
• h(B, G) = 6
• h(C, G) = 3
• h(D, G) = 6
• h(E, G) = 3
• h(F, G) = 1

Sorta Interesting, Right

1. What does it mean to sort "in place", and why would we want this?
2. What does it mean for a sort to be "stable"? Which sorting algorithms that we have seen are stable?
3. Which algorithm would run the fastest on an already sorted list?
4. Given any list, what is the ideal pivot for quicksort?
5. So far, in class, we've mostly applied our sorts to lists of numbers. In practice, how would we typically make sure our sorts can be applied to other types?