[SOLVED] INF102 Assignment 3

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

A = [a​0,a_​ ​1,…,a_​ ​n-1]._​

In this task we are looking at different ways to compute all pairs {a​i,a_​              ​j}_​ such that a​i + 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 Detect​CycleDriver.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)]