Data Structure Exercises

Question 5

In this problem, we use the LinkedList class from problem (2). Suppose a list has been initialized to look as follows: see image.

Now suppose that we added the following method to the LinkedList class:

public int m() {
ListNode c = head;
ListNode c2 = head;
while(c2 != null && c2.next != null) {
c2 = c2.next.next;
c = c.next;
}
return c.data;
}

(a) Determine what is returned when we invoke list.m();. Follow the code step by step and explain how this happens (ie, show a "memory diagram" for the c and c2 pointers).

(b) Suppose there are n elements in the list and list.m(); is invoked. Analyze the asymptotic running time of this method (in terms of n).

Question 6

The following code shows how one might implement a binary tree node:

public class TreeNode {
public int data;
public TreeNode left;
public TreeNode right;

public TreeNode(int d, TreeNode l, TreeNode r) {
data = d;
left = l;
right = r;
}
}

Suppose we have the following binary tree (with root being the node at the top): see image.

The following method is an instance method in the TreeNode class.

public void p() {
System.out.println(data);
if(left != null) {
left.p();
}
if(right != null) {
right.p();
}
}

Suppose root.p() is called. What is output? Show memory diagrams and/or stack frames to explain what the recursive calls are.

Question 7

In this problem, you will determine what the following method does.

public static void rra(int[] list, int start, int end) {
if(start >= end) {
return;
}
int tmp = list[start];
list[start] = list[end];
list[end] = tmp;

// recursion!
rra(list, start+1, end-1);
}

Suppose list = [0, 2, 4, 6, 8, 10, 12, 14, 16].

(a) What happens to list when rra(list, 0, 4) is called? Show memory diagrams and/or stack frames to explain what the recursive calls are.

(b) What happens to list when rra(list, 0, list.length - 1) is called? Show memory diagrams and/or stack frames to explain what the recursive calls are.

Question 8

In this problem, we will implement a simple coin flipping game for two players. The game is played as follows:

• Player one declares a number of times we will flip the coin.
• A coin is flipped that many times.
• Player one guesses how many times he expects the coin to come up heads.
• Player one two responds with another guess of how many times he expects the coin to come up heads.
• The player who came closest to the actual number of heads wins.

Suppose our Player interface looks like this:

public interface Player {
int declareNumFlips();
int guessFirst(int numFlips);
int guessSecond(int numFlips, int otherGuess);
}

and our Coin interface looks like this:

public interface Coin {
public static final int HEADS = 0;
public static final int TAILS = 1;

int flip();
}

(a) Implement a FairCoin class, whose flip method returns HEADS and TAILS with equal likelihoods.

i. First determine the instance and/or static variables:

public class FairCoin implements Coin {
// include your instance variables here
// you may also include any static constants you wish to have

ii. Implement a constructor for the class and the flip method:

public FairCoin() {
}

public int flip() {
}

Question 2

The following code is a skeleton for a LinkedList data structure.

public class ListNode {
public int data;
public ListNode next;

public ListNode(int d, ListNode n) {
data = d;
next = n;
}
}

public class LinkedList {
private ListNode head = null;
// note: no tail!
private int size = 0;

public int getFirst() {
// ...
}

(a) Implement the get method in the LinkedList class: this method should return the ith element of the list. For example, if the list has elements 5, 2, 7, then get(2) should return 7.

public int get(int i) {
}

(b) Suppose the list has n elements and then we call list.get(n - 1). What is the asymptotic running time ("Big Oh") of the method? Explain your reasoning.

Question 3

Write the method sequentialSearch, which should look for a number in an array. It should return i if list[i] == number, and it should return -1 if the number is not in the list. Note: do not assume that the list is sorted (ie: do NOT use binary search!).

(a)

public static int sequentialSearch(int[] list, int number) {
}

(b) suppose the array has n elements. Analyze the asymptotic running time ("Big Oh") of this method, in terms of n. Explain your reasoning.

Question 4

In this problem, we will implement a method which just checks if a list is sorted in descending order. We define a list ot be sorted in reverse order if every element in the array is greater than or equal to the next element of the array. (This means it's sorted in reverse order, greatest to smallest.) It should return true if the list is sorted in descending order and false if it is not.

(a) Implement the isSortedDescending method (using Java or pseudocode):

public boolean isSortedDescending(int[] list) {
}

(b) Suppose there are n elements in the list. Analyze the asymptotic running time ("Big Oh") of this method, in terms of n. Explain your reasoning.