Algorithms留学生辅导、Java编程讲解、辅导Data Structures、讲解Java程序设计
辅导Python程序|辅导Datab
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