Every week there will be exercises you can answer. They are completely optional, but are meant to help you master the course. You can ask for help with them at the lab sessions.

Answers to the exercises will appear, eventually, here. But please try the exercises before looking at the answers!

Week 1

Introduction

  1. Write a method int insert(int[] a, int i, int x) whose behaviour is as follows. It takes an array a, an index i and a value x. It makes a space at index i by moving all elements with index i or higher one step up, then it stores x at index i. Your method should return whatever was the last element of the array before, since there is no room for it in the array anymore.

  2. Write a method that reverses an array.

  3. 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"). You may use s.length() to find the length of a string and s.charAt(i) to find the character at index i.

  4. In Java, there is a random number generator Math.random() that gives a double in the range [0.0..1.0) with uniform distribution. Using this, define your own function that takes two integer parameters min and max, and gives a random integer between min and max. Check the method by calling it different numbers of times and writing out each time a table showing the relative frequency of each generated number.

  5. Do exercise 5.9 ("For the binary search routine…") from Weiss.

Complexity

  1. Arrange the following functions in order of growth: n4, log n, n log n, 4n, 3n3, 5n2 + n

  2. Assume that you have an algorithm that takes 2n 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.

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

    • 10 · 2n

    • 10000 · log2 n

    • 100000 · n

    • 10 · n!

  4. Write the following functions in big-O notation:

    • 34x + x2

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

    • 104000x + 0.005 x2 + 103/x3

    • 10 log2 x + 2 log10 x

    • 2x + 10x

    • (x–2) (x–1) x

  5. What is the complexity of adding a single element to an ArrayList? What is the complexity of adding n elements?

  6. What is the complexity of the two methods you wrote earlier (insert and the string interleaving method)? Say why they have this complexity.

  7. Do exercises 5.16 (For 1,000 items…), 5.21 (Occasionally, multiplying the sizes…) and 5.23 (Unlucky Joe…) from Weiss.

  8. (Harder) What complexity do the following algorithms have?

    (In the first one, the for-loop condition is j <= i; in the second one it’s j <= n.)

  9. In the lecture, the algorithm for deciding if an array had duplicate elements was O(n2). Suppose that the array is sorted. Can you find an algorithm that takes O(n) time instead?

Week 2

Sorting

  1. Many people have tried to visualise sorting algorithms. Check out:

  2. What complexities do the following operations have?

    • 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

    • Adding an element to a sorted array of n elements (the resulting array should also be sorted)

    (The moral is that all data structures make tradeoffs.)

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

    • Insertion sort

    • Selection sort

    • Quicksort (picking the first element as the pivot)

    • Quicksort (using the median-of-three pivot)

    • Mergesort

  4. 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?

  5. 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.

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

  7. Do exercise 8.9 from the book.

  8. Define the function splitInHalf :: [a] → ([a], [a]) that is necessary for mergesort. It should take a list and split it into two equal pieces. Can you do it while making only one iteration through the list?

Complexity of recursive functions

  1. Do exercises 7.15, 7.19, 7.20 from the book.

  2. Write a method with the following signature

    that prints out all subsets of the input array. Use recursion. Alternatively, write a Haskell function

    that returns all subsets of a list. What is its complexity? Assume that printing out a single subset is O(1).

Week 3

Lists

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

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

  3. What representation would you choose for a list of unbounded length (no fixed capacity) where you must be able to quickly insert elements into the front and back of the list, and to delete from the front of the list?

  4. What representation would you choose for a list of unbounded length where you must be able to insert elements into the front of the list, and to delete from the front and back of the list? Draw a picture to explain why this is a good representation.

  5. Suppose you want a data structure with only the operations insert and findMin. How would you implement it? What is the time complexity of the operations? Can you find an implementation where both operations are O(1)?

  6. Do exercises 6.14, 17.3, 17.4, 17.5 (harder), 17.7 from the book.

Stacks and queues

  1. Do exercises 6.6, 16.1, 16.9 and 16.10 from the book.

  2. 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?

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

Binary trees

  1. In what order will the elements of the following tree be traversed in a preorder traversal, an inorder traversal, a postorder traversal, and a level-order traversal?

    binarytree.png

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

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

  4. Do exercises 18.1, 18.2, 18.8 and 18.11 from the book.

  5. (Harder) 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.

    completebinarytree.png

    Write a O(n) function that checks if a binary tree is complete or not.

Week 4

Binary heaps

  1. How would you implement a priority queue using:

    1. a sorted array?

    2. an unsorted array?

    3. 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.

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

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

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

  3. 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 using buildHeap on the same data.

  4. Is heapsort stable? (See exercise 4 about sorting for what stable means.)

  5. Do exercises 21.2, 21.11, 21.15, 21.17, 21.24 and 21.26 from the book.

Hash tables

  1. Do exercises 20.1, 20.2, 20.4, 20.12, 20.13, 20.15, 20.16, 20.17 from the book.

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

Week 5

Balanced binary search trees

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

    1. A binary search tree

    2. An AVL tree

    3. A red-black tree

    4. A 2-3 tree

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

    1. A binary search tree

    2. An AVL tree

    3. A red-black tree

    4. A 2-3 tree

  3. Do exercises 19.10 and 19.11 from the book.

  4. We treated 2-3 trees quite informally. Write down the search and insertion algorithms for a 2-3 tree in pseudocode.

  5. Remember from the lectures that a red-black tree is a clever encoding of a 2-3-4 tree. Compare the operations on red-black trees and 2-3-4 trees and work out the correspondence for yourself. You may want to check, for example, what operation in a red-black tree corresponds to splitting.

    Also, the insertion algorithm that we saw for 2-3-4 trees corresponds to bottom-up insertion on red-black trees. Can you work out how top-down insertion would work in a 2-3-4 tree?

Week 6

Tail recursion

  1.  

    1. Define a Haskell function member :: Eq a ⇒ a → [a] → Bool that tests whether a given element is a member of a list. Your function should be tail-recursive.

    2. Now imagine a Java type corresponding to the Haskell list type: class List<E> { E value; List<E> next; }. Translate the function from part a into a tail-recursive Java method boolean member(E value, List<E> list). Do this with as little thought as possible: just mechanically translate the Haskell into Java.

    3. Now make your Java method iterative (a loop), using the technique from the lecture.

  2. Imagine that we want to search for a value in a binary tree that is not a binary search tree (i.e. the elements can appear in any order). The tree is represented by a class Tree<E> as follows:

    Note that each tree node contains a height field giving the height of the node.

    1. Write a method boolean member(E value, Tree<E> tree) that searches for a value in the tree. What is its space (memory) complexity? Remember to include the call stack in your calculation!

    2. Alter the method so that it uses O(log n) space. Hint: look at the quicksort example. Start by making a method that would use O(log n) space in a language with tail call optimisation, then transform the tail recursion to a loop.