Weekly exercises

Kattis: uib.revpolishtoinfix, uib.dijkstratwostack, backspace
Book: 1.4.5, 1.4.6

Queues. A queue is similar to a stack, except that when you take stuff out of it, you get the earliest added element, and not the latest. Just as stacks, queues can be implemented using both (dynamically resizable) arrays and linked lists. Write two classes, MyArrayQueue and MyLinkedListQueue, who both implement the interface IQueue Links to an external site.. What are the runtimes of enqueue() and dequeue() in your implementation? Can you make both O(1) on average?

Kattis: uib.fakeboolquickfind, guess, unionfind*
Book: 1.4.{12, 14, 24}  1.5.{8, 9, 14}

Binary Search. In lecture we made a binary search function which worked for an array of integers, and returned true or false depending on whether the item existed in the array. However, the software engineer inside you cringes at an algorithms which only work for a single data type; you want to create a BinarySearch class with search methods that work for any Comparable type.

Simply returning true or false is also dissatisfying - you want to return the index of the found element, or -1 if the target value does not appear. Construct your search function indexOf(T key, T[] arr) such that, if the target value occurs multiple times, the first index where it occurs is returned (or make both version - indexOf(T key, T[] arr) returning the first index, lastIndexOf(T key, T[] arr) returning the last index).

Include some reasonable sanity tests for your functions. You may use https://github.com/torsteins/inf102f18-lectures/blob/master/src/week35/BinarySearch.java Links to an external site. as a starting point if you wish.

* time limits for unionfind are very tight - you need to adhere to every advice from General troubleshooting of Time Limit Exceeded on Kattis. This task can be combined with 1.5.14.

Kattis: uib.trollbook, classy
Book: 2.1.{1, 4, 9}, 2.2.2, 2.3.{1, 2, 12, 15, 20, 28}

Kattis: guessthedatastructure, uib.nuclearmalware
Book: 2.4.{2, 5, 6, 7, 20}

MinMax priority queue. Design a data structure that supports the following operations: add, poll the maximum, and poll the minimum (all in logarithmic time); and peek (find) the minimum and peek the maximum (both in constant time).

Hint: Use two heaps - one minHeap, and one maxHeap. Let the heaps contain elements of a "wrapper" object type, which has three fields; the comparable element itself, the index in the minheap and the index in the maxheap.

When you insert an element, insert it on both heaps. Make sure your swap function updates the indices in the wrapper correctly. When you poll an element, remove it from both heaps - swap it with the last element of the heap, decrement the size, and sink/swim the swapped element.

To test your data structure, you should write some reasonable sanity tests; or test it out on uib.greedytaxcollecto

Deadline mandatory 0 Wednesday Sept 26 at 23:59

Kattis: grandpabernie, uib.perfecthash
Book: 3.3.{1, 5, 6, 38} 3.4.{1, 4, 5}

Set. A set is basically a symbol table, except we don't care about the values. A set should (at minimum) support the following API:

         Set()              // create an empty set
    void add(Key key)       // add key to set
    void delete(Key key)    // remove key from set
 boolean contains(Key key)  // is the key in the set?
     int size()             // number of keys in the set

Use one of the symbol table implementations from lecture (BST, red-black BST, or ChainingHashTable) as the underlying data structure, and implement a `XxxSet` class.

Kattis: wheresmyinternet, countingstars, torn2pieces, amazing
Book: 3.4.{10, 13, 14}, 4.1.{2, 9, 11, 12}

About 4.{2, 9, 11}: Assume the graph is created from the file by first creating an AdjListGraph object with n=V vertices, and then each of the edges are added in the order given (this is also pretty much exactly what happens in the code these exercises refers to in the book (see page 526))

Hint: In countingstars, create a graph with n x m vertices. Let vertex x correspond to the location in row (x/n) and column (x%n) in the picture. In the general case, the vertex x is then next to the vertices x+1, x-1, x-n and x+n (but beware of edge cases at the border). Add an edge between two vertices if they are next to each other and both are "-". Then try, from each unvisited "-" -vertex, to run a new dfs. The number of times this happens is your answer.

Hint: In torn2pieces you only need a regular dfs or bfs with parent pointers, but the problem is complicated by that the vertices are provided as strings rather than the more convenient indices. Use a symbol table to translate between strings and vertex id's; have one symbol table<String, Integer> stationToId, which maps strings to indices, and vice versa an array idToStation which maps indices back to to strings (you could for instance make stationToId first, then create idToStation in linear time afterwards).

Hint: In amazing, follow the dfs-strategy of laying down stones on locations you have visited already. As an input to your dfs function, it could be beneficial to (in addition to the current location) provide the direction where you came from, should you need to retrace your steps. More hints: Use symbol tables to put down stones; index into your symbol table using a custom immutable location type. This task can be quite hard.

Deadline mandatory 0 Wednesday Oct 17 at 23:59

Kattis: birthday, builddeps

Kattis: minspantree, reversingroads

Previous exams: https://github.com/marcbezem/INF102/tree/master/oldexams Links to an external site.

Kattis: allpairspath (try to convert the code from lecture to the Floyd-Warshall algorithm (thus changing runtime from O(n³log n) to O(n³). See lecture on ASPS)

Previous exams: https://github.com/marcbezem/INF102/tree/master/oldexams Links to an external site.