Given a positive integer k and an array of n unordered distinct integers

A = [a0,a 1,,a n-1].

In this task we are looking at different ways to compute all pairs {ai,a j} such that ai + a j = k while i j. For each scenario, give a short description (max 3 sentences) describing how you would do it in order to achieve the specified running time. (Note that the running time is given using Theta- and not O-notation).

1. (n²)
2. (n log n)
3. (n)

Task 2

In this assignment you are to write a method detectCycle(edges) in the class Problem2.java, that takes an undirected graph G given in an adjacency list representation (see DetectCycleDriver.java) as argument and determines if it contains at least one cycle. If there is such a cycle your program should return an ArrayList containing the vertices of a cycle in the order they were discovered and if there is no cycle a NULL value should be returned. Note that the graph might not be connected. You can use the class DetectCycleDriver.java to test your program. Your program should run in time O(V + E), where V is the number of vertices and E the number of edges in G.

Example:

If the graph has the following structure, your program could return [4,5,8,7].

Task 3

Write a method findPath(maze) in the class Problem3.java, that computes and outputs the shortest path between two points A and B in a 2D maze as an ArrayList<Pos>. The maze is given as a two dimensional array of boolean values where a false value indicates a wall. The path can only contain positions containing true values that are either connected horizontally or vertically (not diagonally). If no such path exists then a NULL value should be returned. You can use the file MazeDriver.java to test your program.

Example: With the input as shown below your output should be:

[(0,0),(0,1),(0,2),(0,3),(1,3),(1,4),(1,5),(1,6),(2,6),(3,6),(3,5),(3,4),(3,3),(4,3),(5,3),(5,4)]