Assignment
Exercise 1.
Given the following undirected graphs, indicate whether they are bipartite or no. Justify your answer.
Exercise 2.
Given the following directed graphs, specify the strongly connected components:
Exercise 3.
Solve the following problems for undirected graphs with BFS searches:
a) For a given graph whose vertices represent integer numbers and a specified vertex, complete the getClosestFrom() method from the edu.uoc.mecm.eda.search.ClosestPrimeNumber class, so as it returns the closest prime vertex in the graph (distance measured based on the number of edges that separate them).
b) For a given graph whose vertices represent integer numbers ans a specified vertes, complete the edu.uoc.mecm.eda.search.AnEvenNumber class, so as to find an even vertex at a distance less than x edges away from the initial vertex.
Exercise 4.
In this exercise you will design an artificial intelligence algorithm for a simple 2D videogame. In this videogame you will control a little thief who wants to steal all the treasures in a dungeon and escape it. Many different treasures can be found in the dungeon. To complete the level, the thief must first collect all the dungeon treasures. Once all the treasures have been collected, the thief can complete the level by exiting the dungeon. At the end of the level, the lesser the movements performed, the more the points awarded.
Example of a dungeon. The red squares show positions in which the enemies will capture the thief, whereas the black squares show non-walkable positions.
However, it is not going to be easy for the thief, since there are enemies skulking around the dungeon which will try to avoid the thief to steal all of the treasures. Even though these enemies are static in the map, these will capture the thief if it goes within 1 square radius around the enemy. In such case, the game will be lost. Moreover, some squares are non-walkable (e.g. pits, walls, etc).
The edu.uoc.mecm.eda.game.map.Dungeon class represents a game level and it contains several methods which provide information about the map:
• The getWidth() method returns the size of the map in the X axis.
• The getHeight() method returns the size of the map in the Y axis.
• The canMove (x, y, movement) method tells if the thief can move (walkable square in the map) from the (x,y) square in the direction indicated by movement.
• The move (x, y, movement) method returns the resulting square from moving from (x,y) in the direction indicated by movement.
• The getMovement(x1,y1,x2,y2) method returns the performed movement from square (x1,y1) to (x2,y2).
• The getAdjacentTiles(x,y) method returns the adjacent squares (up, down, left and right) to square (x,y).
• The getAdjacentDiagonalTiles(x,y) method returns the adjacent squares in diagonal to square (x,y).
• The getWatchArea(x,y) method returns the squares in a 1 distance radius to square (x,y), thus corresponding to an enemy watch radius.
• The getMovableArea() method returns the walkable squares to which a thief can move from (x,y).
• The isWalkable(x,y) method returns if the square (x,y) is walkable or not.
• The hasEnemy(x,y) method returns whether the square (x,y) contains an enemy.
• The hasTreasure(x,y) method returns whether the square (x,y) contains a treasure. To simplify the problem, in each level there will be exactly 3 treasures only.
• The hasExit(x,y) method returns whether square (x,y) has an exit.
• The isStartingPoint(x,y) method determines whether square (x,y) is the thief starting point square.
The coordinate origin (0,0) is found in the leftmost lower square of the map. For each and every one of these methods there also exists another version to work with unidimensional coordinates where square 0 is the leftmost lower square in the map.
Note that the Dungeon class constructor is initialized with a file that contains the dungeon map. These maps are represented by some text files that you can find in the resources/ejercicio4 folder of the Eclipse project. In these maps, the different squares are defined as:
• S - thief starting point square
• M - square containing a monster
• E - dungeon exit
• T - square containing a treasure
• X - non-walkable square (pit, wall, ...)
The class edu.uoc.mecm.eda.game.player.Thief represents the thief. You must modify the getPlan() method in order to return a list of movements to perform so as to complete the level. The thief can move to the directly adjacent squares (UP, DOWN, LEFT, RIGHT). Once the thief enters a square with a treasure, he acquires it automatically.
Solve this problem by achieving the minimum number of movements in all the levels by using the algorithms and data structures that you have studied in this course.
A hint to solve the exercise is the following:
• First determine the positions of the treasures, exit, start point, and non- walkable squares
• Build the graph
• Find the shortest path from the start point to the rest of interest points with all the available combinations
• Find the optimum plan
To help you in the resolution of the exercise, you can use the edu.uoc.mecm.eda.game.player.RestrictedBreadthFirstPaths class, which is a modified and optimized class that performs a BFS on the graph to find the shortest path from an origin vertex to a set of interest vertices.
To check that your method works as planned, you must execute and pass all the unit tests that you can find in the main() method of the Dungeon class.
Format your assignment according to the following formatting requirements:
1. The answer should be typed, double spaced, using Times New Roman font (size 12), with one-inch margins on all sides.
2. The response also include a cover page containing the title of the assignment, the student's name, the course title, and the date. The cover page is not included in the required page length.
3. Also Include a reference page. The Citations and references should follow APA format. The reference page is not included in the required page length.
Attachment:- Data-File.zip