Exercises

Write a method that reverses an array of type String[]. Then make your method generic so that it works for any type of array.

Write a method that interleaves two strings: it should take one character from the first string, then one from the second string, another from the first string and so on. Once one string has no characters left it should carry on with the other string. For example, interleaving the strings "anna" and "patrik" should give the result "apnantarik" (or "paantnraik"). Use s.length() to find the length of a string and s.charAt(i) to find the character at index i.

Write a method boolean isPalindrome(String string) that checks if a given string is a palindrome (reads the same forwards and backwards). For example, isPalindrome("madamimadam") should return true.

Extend isPalindrome so that it only considers letters (i.e. it ignores punctuation and whitespace) and is case-insensitive. For example, isPalindrome("Madam, I’m Adam!") should return true. If c is a char, you can write Character.isAlphabetic(c) to check if c is a letter, and Character.toUppercase(c) to convert c to uppercase.

Implement a "guess-the-number" game using binary search: I think of a number between 1 and 10000, your program guesses a number and I reply whether my number is higher or lower. Your program makes a new guess and so on until it guesses the right number. Then extend your program so that I can pick any positive number (that fits within a Java int), not just ones up to 10000.

From Weiss: exercises 1.5, 1.11, 1.12.

Arrange the following functions in order of complexity: n⁴, log n, n log n, 4n, 3n³, 5n² + n.

Assume that you have an algorithm that takes 2ⁿ steps and each step takes a microsecond. What is the largest problem size you can solve before the death of the Sun? Assume that the Sun will die in 5 billion years.

Here are the growth rates of several algorithms. Which will run in a reasonable amount of time when n = 50?

Write the following functions in big-O notation:

What is the complexity of adding a single element to an ArrayList? What is the complexity of adding n elements, if the ArrayList contains n elements?

Suppose we want to be able to delete elements from a dynamic array. If we want to delete an arbitrary element, what is the complexity? What if deletion is allowed to change the order of the elements in the array?

This question is about adding an operation to dynamic arrays that deletes the last element of the array.

What complexity do the following algorithms have?

int result = 0;
for (int i = 1; i <= n; i *= 2)
   for (int j = 0; j <= i; j++)
       result++;

int result = 0;
for (int i = 1; i <= n; i *= 2)
   for (int j = 0; j <= n; j++)
       result++;

Suppose you have an array of n elements, then you can check if it has duplicate elements in O(n²) time, by looping over every pair of elements. But if the array is sorted, you can do it in O(n) time. How?

What is the time complexity of the following operations?

From Weiss: some interesting exercises are 2.1, 2.2, 2.3, 2.6, 2.7, 2.10, 2.11, 2.12, 2.14, 2.15, 2.25, 2.31.

What is the complexity of the following code?

for (int i = 1; i <= n; i *= 2) {
   for (int j = 0; j < n*n; j++)
      for (int k = 0; k <= j; k++)
         // O(1)
   for (int j = 0; j < n; j++)
      // O(1)
}

(Not really a question) Read through some of the stories at Accidentally Quadratic and think about why the complexity is quadratic.

Check out the following visualisations of sorting algorithms:

Sort the sequence 4 6 8 2 9 5 1 7 3 by hand with:

A sorting algorithm is stable if equal elements always remain in the same relative order before and after sorting. Which of our sorting algorithms are stable? Why?

Suppose you have an array of booleans of size n. Give an O(n) algorithm that sorts the array so that all false elements come before all true elements. Your algorithm should use O(1) extra memory.

Write a method that removes all duplicate elements from a Java array in O(n log n) time. Hint: sort the array first (you may use the sorting function from the standard library).

How can you use sorting to check if two words are anagrams of one another?

(Somewhat hard) Design a data structure for an anagram finder. It should support two operations:

Old exam questions: 2012-12 q3, 2012-04 q4.

From Weiss: 7.1-2, 7.15-16, 7.21a-c, 7.22, 7.23, 7.25-7.26 (hard), 7.28, 7.32, 7.43, 7.49, 7.53-7.54, 7.60 (hard).

Write a method with the following signature

void printSubsets(int[] array)

(Hard) Modify your solution to question 1 so that it instead returns an iterator which generates all subsets of an array:

Iterator<Set<Integer>> subsets(int[] array)

From Weiss: question 2.26.

This question is about the sorting algorithm stooge sort.

Give an algorithm that removes all comments from a program. Assume that comments are written as (* ... \*) and can be nested (i.e. (* a comment with (* another comment *) inside *)). Write your algorithm in natural language or pseudocode if you like. What is the complexity of your algorithm?

Write a program that reads a postfix expression and evaluates it.

Implement a bounded queue class using circular arrays as in the lecture. Then build an unbounded queue class using the size-doubling trick. The implementation of your unbounded queue should use the bounded queue class (i.e. call its methods), rather than modifying the bounded queue code.

In the queue implementation in the lecture we record the size of the queue in a field. You might think that we don’t need to do this: the size is simply the number of elements between front and rear, i.e., (rear - front + 1) % capacity. Instead of storing the size, we could compute it using this formula whenever we need to know it. But this doesn’t work. Why?

Given a circular buffer (i.e. the array, and variables front and rear), write down an expression giving the sequence represented by the buffer.

Old exam questions: 2012-08 q1, 2012-12 q5, 2013-04 q5.

From Weiss: 3.21-22, 3.25a, 3.27, 3.28, 3.33.

How would you implement a priority queue using:

A max heap is a heap which operates on the maximum element instead of the minimum. That is, it has operations findMax and deleteMax instead of findMin and deleteMin.

Insert the following elements in sequence into an empty heap: 6, 8, 4, 7, 2, 3, 9, 1, 5. Draw both the tree and array representations of the heap. Then illustrate building a heap from the same data.

(Harder) Remember from the lectures that a binary tree is complete if all its levels are completely full, except for the bottom level which is filled from left to right. The following diagram illustrates a complete binary tree.

Suppose you want a data structure with only the operations insert and findMin. What is the most efficient way to implement it? Be careful with your answer!

Old exam questions: 2013-04 q3, 2013-08 q4, 2012-11 q1, 2013-08 q2.

From Weiss: 6.2a, 6.3, 6.10ab, 6.37b, 6.38.

As mentioned in the lectures, we can use a priority queue to implement sorting as follows: start with an empty priority queue, add all elements of the input list in turn, and then repeatedly find and remove the smallest element. Perform this sorting algorithm by hand on the list [3,1,4,2,5] using a leftist heap.

It’s hard to efficiently implement merge for ordinary binary heaps, even even we represent them as trees rather than arrays. What is the problem?

Leftist heaps don’t try to keep the tree balanced, but just try to stop it from becoming right-heavy. Why can’t we use the same trick to make an efficient BST?

Is the following statement true or false? Why?

How many nulls are there in a binary tree of n nodes? Why?

Try implementing binary search trees in Java.

Define a recursive function that, given a binary search tree, prints out all its elements in ascending order.

Insert the values 2,1,4,5,9,3,6,7 into:

Insert the values 1,2,3,4,5,6,7,8 into:

We saw that requiring the tree be perfectly balanced is too strong an invariant for a balanced BST, because it only allows trees of certain sizes. Alternatively, we could have the invariant that the tree is complete, like we did for binary heaps. But this doesn’t work well. Why not?

Work out an algorithm for doing lazy deletion in a binary search tree (see the lecture slides). Your invariant should probably be: a deleted node can only have deleted children.

Old exam questions: 2012-11 q2, 2012-12 q1, 2013-04 q1, 2012-08 q3, 2011-12 q2, 2012-04 q1,2, 2011-12 q3, 2012-12 q4, 2011-12 q1.

From Weiss: 4.1-5, 4.8, 4.41, 4.9, 4.11-12, 4.16, 4.19, 4.25, 4.35, 4.37, 4.49.

Repeat last week’s question 5 and 6 with:

In a B-tree, the bigger value of k (node size) we choose, the shallower the trees get and the less often we have to do splitting. Is there a disadvantage to increasing k?

In 2-3 trees, we split a 4-node into three 2-nodes. We can’t split a 3-node into two 2-nodes, though. Why not?

(not really a question) We skipped over 2-3 tree deletion, which is more complicated than insertion. If you want, you can read about it in these notes: http://www.cs.princeton.edu/~dpw/courses/cos326-12/ass/2-3-trees.pdf.

In AA trees, we only allowed the right child to have the same level as its parent. We could weaken the invariant, so that either child (but not both) can have the same level as its parent. In other words, a 3-node is constructed by a node and either of its children. What happens if you do this? Is there an advantage to doing it? Is there a disadvantage?

(hard) Can you design a version of AA trees that corresponds to 2-3-4 trees instead of 2-3 trees? You will want to represent a 4-node as a node where both children have the same level. (This structure is normally called a red-black tree.)

(very hard) In a 2-3-4 tree, you can use a more efficent insertion algorithm called top-down insertion. In top-down insertion, as you move down the tree looking for the insertion point, whenever you reach a 4-node you split it and absorb it into its parent (note that its parent won’t be a 4-node because it will already have been split). After splitting the leaf, it will be a 2- or 3-node, so there will be room for the inserted value. Thus you avoid having to go up the tree splitting after insertion.

Implement a Java class for directed graphs using an adjecency list representation. Nodes should have labels of an arbitrary type (use generics, class Graph<T>) and edges have no labels. You can use map from node labels to lists of node labels where each element in the list represents one edge. The class should have the following constructor and methods:

Add, to the Java implemention from question 1, a method/function isCyclic which determines whether the graph/a given graph is cyclic (contains a cycle) and returns a boolean value.

Extend the class in question 1 to a class UndirectedGraph<T> which represents undirected graphs by overriding addEdge and nEdges.

Add a method to the class in question 1 that transposes the graph.

Old exam questions: 2012-12 q2, 2012-08 q4, 2013-08 q5, 2012-04 q6, 2011-12 q4, 2012-12 q6, 2011-12 q6.

From Weiss: 9.1-2, 9.5, 9.7a, 9.10b, 9.15-16 (ignore Kruskal’s algorithm), 9.20, 9.26, 9.31, 9.38, 9.41-42, 9.44-45, 9.51-53.

What complexity does inserting an element at the front of a singly linked list of n elements have?

What complexity does inserting an element at the back of a singly linked list of n elements have?

Try implementing circular linked lists in your favourite language.

Old exam questions: 2012-08 q5, 2012-04 q3, 2013-04 q6.

From Weiss: 3.2, 3.6, 3.11, 3.15, 3.29, 3.31-32, 3.34.

Insert the values 2,1,4,5,9,3,6,7 into:

2-3 tree insertion works by splitting 4-nodes; deterministic skip list insertion works by raising the level of nodes that break the invariant. But they are really the same thing. Can you work out in detail the connection between 2-3 trees and deterministic skip lists?
Start by making sure you understand how to translate a 2-3 tree to a deterministic skip list, as illustrated in the slides. Then take a small 2-3 tree and do some insertions that cause nodes to split. Translate your original tree into a deterministic skip list and repeat the insertions. The process should be very similar. What is going on?

We can view any deterministic skip list as a 2-3 tree. Likewise, we should be able to view an arbitrary skip list as a tree of some kind (not a 2-3 tree though).
What sort of tree corresponds to a skip list? It will be a pretty weird one! Can you adapt the skip list insertion/deletion algorithms to work on this kind of tree?

(hard) Work out how to use skip lists to implement a sequence data type. A sequence is like an array, in that you can get or set the ith index. Unlike an array, you can also efficiently insert a new element anywhere in the array, or delete an arbitrary element (given the index).
Hint: you will probably want to augment each link in the skip list so that it records how many nodes it skips over.

Old exam questions: 2011-12 q3 with skip lists.

From Weiss: 10.37, 10.39.

What are the advantages and disadvantages of hash tables compared to binary search trees?

Write down a suitable invariant for:

Remember that in linear probing we have to use lazy deletion. Construct an example where this is necessary, i.e., simply deleting the item gives the wrong result.

When using linear probing, we might try to avoid lazy deletion as follows. To delete an element x, we first find the element, then find the last element in that cluster (call it y), and overwrite x with y in the array (and delete y).
The idea is that this keeps the cluster in one piece, thus not breaking the invariant. However, it doesn’t work. Find an example where it goes wrong.
Can you think of a way to fix this method, without going back to lazy deletion? It may help to think about the hash table’s invariant.

In early versions of the PHP programming language, the hash function used for strings was the length of the string. Can you think of any problems this would cause?
After thinking a bit, read the answer here.

Old exam questions: 2012-08 q2, 2011-12 q1, 2012-11 q3, 2013-04 q4.

From Weiss: 5.1a-b, 5.17.