Starting from:
$30
INF102-Assignment 3 Solved
Task 1
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).
a) Θ(n2)
b) Θ(n log n)
c) Θ(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)]
Appendix: Style Guide
The following rules applies to all source code that is handed in. These guidelines are loosely based on Google Java Style Guide, though with some minor differences.
Most important
Make your code easy to read.
Comment tricky parts of the code.
Use descriptive and logical variable names and function names. Break the code into appropriate functions for readability and code reuse; no function should ideally be more than 30 lines of code (with the exception of extremely monotone code, such as sanity tests).
Write javadoc comments for functions that are not self-explanatory All files should use UTF-8 character encoding.
Also important
The only whitespace characters allowed are spaces and newlines (tabs are not allowed).
Each indentation level increases by 4 spaces.
No line may exceed 120 characters - lines exceeding this limit must be line-wrapped.
Some exceptions, e.g. very long URL's that don't fit on one line. File name should be the same as the name of the class, written in UpperCamelCase.
Function names, parameter names and variable names should be written in lowerCamelCase.
Constants should be written in ALL_CAPS.
No line breaks before open braces ({).
Blank lines should be used sparingly, but can be used to separate logic blocks and to increase readability.
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).
a) Θ(n2)
b) Θ(n log n)
c) Θ(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)]
Appendix: Style Guide
The following rules applies to all source code that is handed in. These guidelines are loosely based on Google Java Style Guide, though with some minor differences.
Most important
Make your code easy to read.
Comment tricky parts of the code.
Use descriptive and logical variable names and function names. Break the code into appropriate functions for readability and code reuse; no function should ideally be more than 30 lines of code (with the exception of extremely monotone code, such as sanity tests).
Write javadoc comments for functions that are not self-explanatory All files should use UTF-8 character encoding.
Also important
The only whitespace characters allowed are spaces and newlines (tabs are not allowed).
Each indentation level increases by 4 spaces.
No line may exceed 120 characters - lines exceeding this limit must be line-wrapped.
Some exceptions, e.g. very long URL's that don't fit on one line. File name should be the same as the name of the class, written in UpperCamelCase.
Function names, parameter names and variable names should be written in lowerCamelCase.
Constants should be written in ALL_CAPS.
No line breaks before open braces ({).
Blank lines should be used sparingly, but can be used to separate logic blocks and to increase readability.
1 file (86.1KB)
