Every week there will be exercises you can answer. They are completely optional, but are meant to help you master the course. You can go to the exercise sessions to get help with the exercises.
The exercise sessions are:

Mondays 1012, room EC (EDIT building)

Thursdays 810, usually in room ML1 (Mhuset), but in week 51 (20th December) it will be in EC (EDIT building).
You can find directions to the rooms here.
Generally, you should try to go to one exercise session per week. Of course, you are welcome to come to more if there is space, and it is not compulsory to come.
The week numbers in the exercises indicate which week’s lectures the exercises correspond to. Therefore, the exercise sessions may lag slightly behind the numbering here. Also, the exercises for later weeks may change without notice!
Week 1
Introduction

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 caseinsensitive. 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.
Hint: To check if two characters are the same in a caseinsensitive fashion, you can see if they come out the same when converted to uppercase.
Hint: Define two indexes into the string, one that starts at the beginning and move forwards, and the other that starts at the end and moves backwards.

Implement a "guessthenumber" 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.
Complexity
Note: you will only be able to do most of these exercises after Friday’s lecture.

Arrange the following functions in order of complexity: n^{4}, log n, n log n, 4n, 3n^{3}, 5n^{2} + n.

Assume that you have an algorithm that takes 2^{n} 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?

10 × 2^{n}

10000 × log_{2} n

100000 × n

10 × n!


Write the following functions in bigO notation:

34x + x^{2}

1x + 2x + 3x + 4x + 5x + 6x + 7x

10^{4000}x + 0.005 x^{2} + 103/x^{3}

10 log_{2} x + 2 log_{10} x

2^{x} + 10^{x}

(x–2) (x–1) x


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.

The last element of a dynamic array can be deleted in O(1) time. How?

Suppose that we do not try to resize the underlying array when deleting the last element. Then the dynamic array can end up with unlimited overhead  for example, we can end up with an array of capacity 1024 but only one element stored in it. How?

To solve this problem, we might decide on the following rule: if the array ever becomes halfempty, resize it to half its current size. Unfortunately, this ruins the efficiency of the design: the time complexity of performing n operations (adds and deletes) is O(n^{2}) in the worst case. Find a sequence of operations that demonstrates this.

(Harder) Tweak the rule in part (c) so that the O(n) runtime is preserved. Persuade yourself that your design works.

(Much harder, extremely optional) Learn about the potential method (not covered in this course, unless we have spare time later) and use it to prove that your design works.


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++;
(In the first one, the forloop condition is j <= i; in the second one it’s j <= n.)

Suppose you have an array of n elements, then you can check if it has duplicate elements in O(n^{2}) 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?

Finding an element in an unsorted array of n elements

Finding an element in a sorted array of n elements

Adding an element to an unsorted array of n elements, assuming there is an empty space at the end of the array

Adding an element to a sorted array of n elements, assuming there is an empty space at the end of the array (the resulting array should also be sorted)
The moral is that all data structures make tradeoffs—choosing a different representation will make some operations faster but others slower.


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.
Week 2
Sorting

Check out the following visualisations of sorting algorithms:

Sorting out sorting, an 80stastic video comparing different sorting algorithms

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

Insertion sort

Quicksort (picking the first element as the pivot)

Quicksort (using the medianofthree pivot)

Mergesort


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:

Create the data structure given a list of words. This operation should have complexity O(n log n), where n is the number of words (assuming that words have a bounded length).

Given a word, find all its anagrams in the data structure. This operation should have complexity O(m + log n), where m is the number of anagrams found for that word and n is the total number of words in the data structure.
Hint: part (a) should sort the list of words. But you need to sort them in a particular order so that part (b) can be solved efficiently…
Hint 2: answer question 6 first. Can you think of a way to sort the list of words so that anagrams always end up next to each other?


Old exam questions: 201212 q3, 201204 q4.

From Weiss: 7.12, 7.1516, 7.21ac, 7.22, 7.23, 7.257.26 (hard), 7.28, 7.32, 7.43, 7.49, 7.537.54, 7.60 (hard).
Complexity of recursive functions

Write a method with the following signature
void printSubsets(int[] array)
that prints out all subsets of the input array. Use recursion. What is its complexity? Start by writing a recurrence relation. Assume that printing out a single subset is O(1).

(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)
where Set is the standard Java set class.

From Weiss: question 2.26.

This question is about the sorting algorithm stooge sort.

Read about the algorithm at the link above. Convince yourself that it works. Hint: suppose that the input list has 3n elements, and consider the largest n elements of the list. Initially they can be anywhere in the list. Where can they be after the first recursive call? Where can they be after the second recursive call?

Write down a recurrence relation for the algorithm.

(Hard) Solve the recurrence relation to find the complexity of the algorithm.

Stacks and queues

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 sizedoubling 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: 201208 q1, 201212 q5, 201304 q5.

From Weiss: 3.2122, 3.25a, 3.27, 3.28, 3.33.
Week 3
Binary heaps

How would you implement a priority queue using:

a sorted array?

an unsorted array?

a binary search tree?
What complexity do the resulting operations have? In part c, give two answers depending on whether the tree is balanced (has height O(log n)) or unbalanced.


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.

Suppose you have an implementation of a min heap. How would you change it into a max heap?

Java provides a class PriorityQueue<E> that implements a min heap. Define a class that uses PriorityQueue<E> to implement a max heap. Hint: you will need to use a custom Comparator when you initialise the priority queue. Here is a nice explanation about how comparators work.


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.
Write a O(n) function that checks if a binary tree is complete or not.
Hint: you will need a helper function that calculates these three pieces of information at once:

Whether the tree is complete or not.

The height of the tree.

Whether the bottom level of the tree is full.


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: 201304 q3, 201308 q4, 201211 q1, 201308 q2.

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

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 rightheavy. Why can’t we use the same trick to make an efficient BST?
Binary trees, binary search trees and AVL trees

Is the following statement true or false? Why?
Inserting a set of objects into a binary search tree, you get the same tree regardless of what order you insert the objects in. 
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:

A binary search tree

An AVL tree


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

A binary search tree

An AVL tree


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: 201211 q2, 201212 q1, 201304 q1, 201208 q3, 201112 q2, 201204 q1,2, 201112 q3, 201212 q4, 201112 q1.

From Weiss: 4.15, 4.8, 4.41, 4.9, 4.1112, 4.16, 4.19, 4.25, 4.35, 4.37, 4.49.
Week 4
23 trees, Btrees and AA trees

Repeat last week’s question 5 and 6 with:

A 23 tree

An AA tree


In a Btree, 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 23 trees, we split a 4node into three 2nodes. We can’t split a 3node into two 2nodes, though. Why not?

(not really a question) We skipped over 23 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/cos32612/ass/23trees.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 3node 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 234 trees instead of 23 trees? You will want to represent a 4node as a node where both children have the same level. (This structure is normally called a redblack tree.)

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

Describe this algorithm in pseudocode using splitting and absorption.

Adapt your redblack tree from question 6 to use this algorithm. Congratulations, you now have the fastest balanced BST!

Week 5
No solutions for this week
Graphs

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:

Graph() constructor that creates an empty graph

void addNode(T label) which adds a node with given label or does nothing if there is already a node with this label

void addEdge(T node1, T node2) which adds an edge from node node1 to node2 provided that the two nodes exist

int nNodes() which returns the number of nodes

int nEdges() which returns the number of edges

Iterable<T> nodes() which returns an iterable with all nodes

Iterable<T> neighboursOf(T node) which returns an iterable with all nodes adjecent to node


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: 201212 q2, 201208 q4, 201308 q5, 201204 q6, 201112 q4, 201212 q6, 201112 q6.

From Weiss: 9.12, 9.5, 9.7a, 9.10b, 9.1516 (ignore Kruskal’s algorithm), 9.20, 9.26, 9.31, 9.38, 9.4142, 9.4445, 9.5153.
Week 6
Linked lists

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: 201208 q5, 201204 q3, 201304 q6.

From Weiss: 3.2, 3.6, 3.11, 3.15, 3.29, 3.3132, 3.34.
Skip lists

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

A probabilistic skip list (you can use this link to flip a virtual coin).

A deterministic skip list.


23 tree insertion works by splitting 4nodes; 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 23 trees and deterministic skip lists?
Start by making sure you understand how to translate a 23 tree to a deterministic skip list, as illustrated in the slides. Then take a small 23 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 23 tree. Likewise, we should be able to view an arbitrary skip list as a tree of some kind (not a 23 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: 201112 q3 with skip lists.

From Weiss: 10.37, 10.39.
Hash tables

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

Write down a suitable invariant for:

Hash tables with linear chaining.

Hash tables with linear probing.


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: 201208 q2, 201112 q1, 201211 q3, 201304 q4.

From Weiss: 5.1ab, 5.17.