Algorithms留学生代写、Java编程代做、代写Data Structures、代做Java程序设计

日期：2019-04-17 10:29

Data Structures and Algorithms

Home Quiz 1

Problem 1 (4 points)

We have a connected graph G = (V, E), and a specific vertex u ∈ V. Suppose we compute a depth-first

search tree rooted at u, and obtain a tree T that includes all nodes of G. Suppose we then compute a

breadth-first search tree rooted at u, and obtain the same tree T. Prove that G = T. (In other words, if T

is both a depth-first search tree and a breadth-first search tree rooted at u, then G cannot contain any

edges that do not belong to T.)

Problem 2 (3 + 3 points)

Given is a undirected graph and two of its vertices s and t. Give an O(n+m) algorithm that computes

the number of shortest paths from s to t.

Note: You get 3 points if you describe the solution correctly (i.e. pseudocode) and 3 points if you

implement it in Java.

Problem 3 (0.5% extra points for implementation)

Given is an a × b matrix where every cell corresponds to either an empty space, denoted with a dot (.)

or a wall, denoted with X. This matrix represents a maze and in it there are also two creatures: creature

One (1) and creature Two (2). Creatures start at different empty spaces. And, somehow, they got

synchronized: They do exactly the same movements when (1) goes west, so does (2); when (1) goes

east, so does (2); and the same happens when they go south or north. They move at the same time: for

example, if (1) is east of (2) and they move east, both creatures move. They cannot go to a location

where there is an obstacle (or the other creature, unless it is moving away). For example, if there is an

obstacle east of (1) but not of (2), if they go east only (2) moves. Or, if east of (1) there is an obstacle

and west of it there is (2), if they try to move east, they will stay in their current locations as (1) is

blocked by the obstacle and (2) is blocked by (1).

Creatures want to get out of this mysterious maze, and they want to do so at the very same time (that is,

they want to leave the house with the same move). Creatures get out of the maze if they move north in

row 1, south in row a, west in column 1, or east in column b. This is proving to be very tricky. Please

help them by designing an O((ab)2

) algorithm that computes the smallest number of moves for them to

get out (or it will tell them that the task is impossible).

Problem 4 (0.5% extra points for implementation)

In the small land of Akrokeraunaia, there are a number of magic cities. One of them is the capital.

Cities are connected to each other through roads. Every year a single person from each city can visit the

capital. Visitors are selected based on a competition. The rules are as follows:

1. The candidates will start running from their cities. (at the same times)

2. The entry into the capital will be permitted only for a fixed amount of time (T) from when

they all start running.

3. Whoever can enter the capital during that fixed time will surely be permitted to visit the

capital city.

Given the connections and the distances between the cities and the capital, the aim is to write a

program that finds out how many candidates can visit the capital. In designing the program you can

assume the candidates will find a route so that they can get to the capital before the entry closes, if

there is one.

Note that all the cities are numbered from 0 to V-1.

Input:

First line will contain the number of cities (V), number of roads (E) and time for which gate will be

open for the capital (T).

E lines will follow, each containing 3 integers in the format:

c1c2t

where, c1 and c2 are the two cities having a road between them and it takes time t to go from one

city to another. Note that all the roads are bidirectional and the city numbered 0 is the capital city.

Output:

A single integer representing number of candidates that can visit the capital

Constraints:

1 <= V <= 100

1 <= E <= 100

1 <= t <= 100