# 期末題庫
###### tags: `演算法`, `109-2`

<!-- >  -->
<div class="newjc">
<img src="https://i.imgur.com/Dsq8qyV.gif">

<style>
.newjc {
animation: Anim 2s linear infinite;
transform: scaleX(0);
}
.newjc:hover {
/* opacity: 0.3; */
}

@keyframes Anim {
0% {
/* margin-left: 0%; */
transform: scaleX(0);
}
10% {
/* margin-left: 25%; */
transform: scaleX(1);
}
40% {
/* margin-left: 40%; */
transform: scaleX(1);
}
60% {
/* margin-left: 40%; */
transform: scaleX(-1);
}
90% {
/* margin-left: 10%; */
transform: scaleX(-1);
}

}
</style>
</div>
<!-- <br> -->

> [name=JCxYIS] [time=Jun 22]

:::info
 請利用 **Ctrl+F** 搜尋考題，比對完成後再去 SD 或 MBD 那裏找解答
:::

:::spoiler Table of Table

[TOC]

:::

## HW 8 ((p)7)

1. **-**
Given a connected Graph G = (V, E), design a algorithm to determine whether G is a euler graph.If G is a euler graph, find a euler circuit.(input is edge list)

2. **Exercise 22.1-3**
The transpose of a directed graph $G = (V, E)$ is the graph $G^T = (V, E^T)$, where $E^T ={ (v, u) ∈ V x V : (u,v) ∈ E }$. Thus, $G^T$ is $G$ with all its edges reversed. Describe efficient algorithms for computing $G^T$ from $G$, for both the adjacency-list and adjacencymatrix representations of $G$. Analyze the running times of your algorithms.

3. **Exercises 22.1-5**
The square of a directed graph $G = (V, E)$ is the graph $G^2 = (V, E^2)$ such that $(u, v) ∈ E^2$ if and only if $G$ contains a path with at most two edges between $u$ and $v$.
Describe efficient algorithms for computing $G^2$ from G for both the adjacency-list and adjacency-matrix representations of $G$. Analyze the running times of your algorithms.

4. **Exercises 22.2-7** (塗兩色問題)
There are two types of professional wrestlers: “babyfaces” (“good guys”) and
“heels” (“bad guys”). Between any pair of professional wrestlers, there may or may
not be a rivalry. Suppose we have n professional wrestlers and we have a list of r
pairs of wrestlers for which there are rivalries. Give an O(n + r)-time algorithm that
determines whether it is possible to designate some of the wrestlers as babyfaces
and the remainder as heels such that each rivalry is between a babyface and a heel.
If is it possible to perform such a designation, your algorithm should produce it.

5. **Exercise 22.2-8**
The diameter of a tree T = (V, E) is defined as maxu,v∈V δ(u, v), that is, the largest of
all shortest-path distances in the tree. Give an efficient algorithm to compute the
diameter of a tree, and analyze the running time of your algorithm.

6. **EXT. 7-3**
Design a linear time algorithm which given an undirected graph G and a particular
edge e in it, determines whether G has a cycle containing e.

7. **-**
Given a connected graph, a vertex v is called a cut-vertex if we remove v, the
graph will be disconnected. Design an algorithm to find the set of all cut-vertices.

## HW 9 ((p)7)
1. **Exercises 22.4-2**
Give a linear-time algorithm that takes as input a directed acyclic graph G = (V, E) and two vertices s and t, and returns the number of simple paths from s to t in G. For example, the directed acyclic graph of Figure
22.8 contains exactly four simple paths from vertex p to vertex v: pov, poryv, posryv, and psryv. (Your
algorithm needs only to count the simple paths, not list them.)

2. **Exercises 22.4-3**
Give an algorithm that determines whether or not a given undirected graph G = (V, E) contains a cycle. Your algorithm should run in O(V) time, independent of |E|.

3. **-**
A DFS forest can be generated by perform DFS on a directed graph. There are 4 types of edges in a DFS forest: tree edge, forward edge, back edge and cross edge. Modify DFS so that it can determine the type of each edge.

4. **Exercises 22.5-2**
Show how the procedure STRONGLY-CONNECTED-COMPONENTS works on the graph of Figure 22.6. Specifically, show the finishing times computed in line 1 and the forest produced in line 3. Assume that the loop of lines 5-7 of DFS considers vertices in alphabetical order and that the adjacency lists are in alphabetical order.


5. **Exercises 22.5-7**
A directed graph G = (V, E) is semiconnected if, for all pairs of vertices u, v ∈ V, we have u ~> v or v ~> u. Give
an efficient algorithm to determine whether or not G is semiconnected. Prove that your algorithm is correct,
and analyze its running time.

6. **EXT. 7-2**
在投影片 Unit 7 P. 39 的地方有提到另一個 DFS 的實作，但其輸出的 order 可能會不同，試問該 DFS 的實作是否可以用來解 Topological Sorting 以及 Strongly-Connected-Components?
(盡量別動到 p.39 code)

7. **EXT. 7-5**
Let G = (V, E) be a connected undirected graph. Design an algorithm to determine whether the edges of G can be oriented such that the resulting directed graph is strongly connected. The algorithm should also find such an orientation if it exists. ( Is edge connectivity>=1 ?)

## HW10 ((p)8)
1. **Exercises 23.1-6**
Show that a graph has a unique minimum spanning tree if, for every cut of the graph, there
is a unique light edge crossing the cut. Show that the converse is not true by giving a
counterexample.

2. **Exercises 23.1-11**
Given a graph G and a minimum spanning tree T, suppose that we decrease the weight of
one of the edges not in T. Give an algorithm for finding the minimum spanning tree in the
modified graph.

3. **Exercises 23.2-4**
Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast
can you make Kruskal’s algorithm run? What if the edge weights are integers in the range
from 1 to W for some constant W?

4. **Exercises 23.2-5**
Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast
can you make Prim's algorithm run? What if the edge weights are integers in the range from
1 to W for some constant W ?

5. **Exercises 23.2-7**
Suppose that a graph G has a minimum spanning tree already computed. How quickly can
we update the minimum spanning tree if we add a new vertex and incident edges to G ?

6. **Problem 16-4** Scheduling variations
Consider the following algorithm for the problem from Section 16.5(unit06-演算法.pdf p26)
of scheduling unit-time tasks with deadlines and penalties. Let all n time slots be initially
empty, where time slot i is the unit-length slot of time that finishes at time i. We consider the tasks in order of monotonically decreasing penalty. When considering task aj, if there exists a time slot at or before aj's deadline dj that is still empty, assign aj to the latest such slot, filling it. If there is no such slot, assign task aj to the latest of the as yet unfilled slots.
- Argue that this algorithm always gives an optimal answer.
- Use the fast disjoint-set forest presented in Section 21.3 to implement the algorithm
efficiently. Assume that the set of input tasks has already been sorted into
monotonically decreasing order by penalty. Analyze the running time of your
implementation.

7. **-**
Consider the problem of finding minimum spanning tree (MST): Given a weighted undirected graph, find a spanning tree with the best (minimum) cost, where the cost of a
spanning tree is the sum of the weights of its edges.
.
a) Describe an efficient algorithm for solving this problem. You should also analyze the time
complexity of this algorithm and describe the data structure used by the algorithm.
.
b) Now assume that we also want to know a spanning tree with the second best cost (if
there is any which may be same as the best cost). For example, consider the graph with
vertex set {1, 2, 3} and edge set {(1, 2, 1), (1, 3, 1) (2, 3, 1)} where each triple (x, y, w)
represents there is an edge with end vertices x, y, and weight w. Then the best and second
best costs of spanning trees of this graph are both 2. For another graph with the same vertex
set and edge set {(1, 2, 1), (1, 3, 2) (2, 3, 3)}, the best and second best costs of spanning trees
of this graph are 3 and 4 respectively. Design an algorithm for solving this problem.

## HW11 ((p)9)
UNIT 9 (HW11)
1. **Exercises 24.1-1**
Run the Bellman-Ford algorithm on the directed graph of Figure 24.4, using vertex z as the
source. In each pass, relax edges in the same order as in the figure, and show the d and π
values after each pass. Now, change the weight of edge (z, x) to 4 and run the algorithm
again, using s as the source.

2. **Exercise 24.1-6**
Suppose that a weighted, directed graph G = (V, E) has a negative-weight cycle. Give an
efficient algorithm to list the vertices of one such cycle. Prove that your algorithm is correct.

3. **Exercises 24.2-3**
The PERT chart formulation given above is somewhat unnatural. In a more nature structure,
vertices would represent jobs and edges would represent sequencing constraints; that is,
edge (u, v) would indicate that job u must be performed before job v. We would then assign
weights to vertices, not edges. Modify the DAG-SHORTEST-PATHS procedure so that it finds a
longest path in a directed acyclic graph with weighted vertices in linear time.

4. **Exercises 24.3-1**
Run Dijkstra's algorithm on the directed graph of Figure 24.2, first using vertex s as the
source and then using vertex z as the source. In the style of Figure 24.6, show the d and π
values and the vertices in set S after each iteration of the while loop.

5. **Exercises 24.3-4**
Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm. The
program produces v.d and v. π for each vertex v ∈ V. Give an O(V + E)-time algorithm to
check the output of the professor’s program. It should determine whether the d and π
attributes match those of some shortest-paths tree. You may assume that all edge weights
are nonnegative.

6. **Exercises 24.3-8**
Let G = ( V , E ) be a weighted, directed graph with nonnegative weight function
𝑤 : E→{ 0 , 1 , …..,𝑊} for some nonnegative integer 𝑊 . Modify Dijkstra’s algorithm to
compute the shortest paths from a given source vertex s in O(𝑊𝑉 + 𝐸) time.

7. 參考新版Unit9投影片 p.12 實作考量，改進Bellman-ford速度(改進速度建議加在課本原程式裡)，寫下pseudocode。

8. 參考新版Unit9投影片 p.19~20，提到2個實作DP計算方式，把其應用在LCS，寫下 pseudocode.

## HW12 ((p)9)
UNIT 9 (HW12)
1. **Exercise 24.1-5**
Let G = (V, E) be a weighted, directed graph with weight function w : E → R. Give an O(VE)-time algorithm to find, for each vertex v ∈ V , the value $δ^*(v) = min_{u∈V}{δ(u, v)}$.

2. **Exercises 24.4-2**
Find a feasible solution or determine that no feasible solution exists for the following system
of difference constraints:

    x1 - x2 ≤ 4
    x1 - x5 ≤ 5
    x2 - x4 ≤ -6
    x3 - x2 ≤ 1
    x4 - x1 ≤ 3
    x4 - x3 ≤ 5
    x4 - x5 ≤ 10
    x5 - x3 ≤ -4
    x5 - x4 ≤ -8

3. **Exercises 25.1-10**
Give an efficient algorithm to find the length (number of edges) of a minimum-length negative-weight cycle in a graph.

4. **Exercises 25.2-1**
Run the Floyd-Warshall algorithm on the weighted, directed graph of Figure 25.2. and
answer the following questions:
(a) Show the matrix D
(k)
that results for each iteration of the outer loop.
(b) List the vertices of one such shortest path from v6 to v1

5. **Exercises 25.3-1**
Use Johnson's algorithm to find the shortest paths between all pairs of vertices in the graph
of Figure 25.2. Show the values of h and ŵ computed by the algorithm.

6. **Problem 24-3** Arbitrage
**_Arbitrage_** is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that $1$ U.S. dollar buys $49$ Indian rupees, $1$ Indian rupee buys $2$ Japanese yen, and $1$ Japanese yen buys $0.0107$ U.S. dollars. Then, by converting currencies, a trader can start with $1$ U.S. dollar and buy $49 \times 2 \times 0.0107 = 1.0486$ U.S. dollars, thus turning a profit of $4.86$ percent.
.
Suppose that we are given $n$ currencies $c_1, c_2, \ldots, c_n$ and an $n \times n$ table $R$ of exchange rates, such that one unit of currency $c_i$ buys $R[i, j]$ units of currency $c_j$.
.
**a.** Give an efficient algorithm to determine whether or not there exists a sequence of currencies $\langle c_{i_1}, c_{i_2}, \ldots, c_{i_k} \rangle$ such that
.
$$R[i_1, i_2] \cdot R[i_2, i_3] \cdots R[i_{k - 1}, i_k] \cdot R[i_k, i_1] > 1.$$
.
Analyze the running time of your algorithm.
.
**b.** Give an efficient algorithm to print out such a sequence if one exists. Analyze the running time of your algorithm.

7. **Problem 25-1** Transitive closure of a dynamic graph textbook, page 705)
Suppose that we wish to maintain the transitive closure of a directed graph $G = (V, E)$ as we insert edges into $E$. That is, after each edge has been inserted, we want to update the transitive closure of the edges inserted so far. Assume that the graph $G$ has no edges initially and that we represent the transitive closure as a boolean matrix.
.
**a.** Show how to update the transitive closure $G^\* = (V, E^\*)$ of a graph $G = (V, E)$ in $O(V^2)$ time when a new edge is added to $G$.
.
**b.** Give an example of a graph $G$ and an edge $e$ such that $\Omega(V^2)$ time is required to update the transitive closure after the insertion of $e$ into $G$, no matter what algorithm is used.
.
**c.** Describe an efficient algorithm for updating the transitive closure as edges are inserted into the graph. For any sequence of $n$ insertions, your algorithm should run in total time $\sum_{i = 1}^n t_i = O(V^3)$, where $t_i$ is the time to update the transitive closure upon inserting the $i$th edge. Prove that your algorithm attains this time bound.

8. 給三個整數 m, n, p 設計一個有效率的演算法，算出 $m^n\ mod\ p$

## HW13 ((p)10)
1. **Exercises 26.1-7**
Suppose that, in addition to edge capacities, a flow network has vertex capacities. That is each vertex v has a limit l(v) on how much flow can pass through v. Show how to transform a flow network G = (V, E) with vertex capacities into an equivalent flow network G’= (V’, E’) without vertex capacities, such that a maximum flow in G ’ has the same value as a maximum flow in G. How many vertices and edges does G’ have?

2. **Exercises 26.2-3**
Show the execution of the Edmonds-Karp algorithm on the flow network of Figure 26.1(a).

3. **Exercises 26.2-11**
The edge connectivity of an undirected graph is the minimum number k of edges that must be removed to disconnect the graph. For example, the edge connectivity of a tree is 1, and the edge connectivity of a cyclic chain of vertices is 2. Show how to determined the edge connectivity of an undirected graph G = (V, E) by running a maximum-flow algorithm on at most |V| flow networks, each having O(V) vertices and O(E) edges. ( find the value of edge connectivity)

4. **Exercises 26.2-13**
Suppose that you wish to find, among all minimum cuts in a flow network G with integral capacities, one that contains the smallest number of edges. Show how to modify the capacities of G to create a new flow network G’ in which any minimum cut in G ’ is a minimum cut with the smallest number of edges in G.

5. ** Exercise 26.3-4**
A perfect matching is a matching in which every vertex is matched. Let G = (V, E) be an undirected bipartite graph with vertex partition V = L ∪ R, where |L| = |R|. For any X ⊆ V, define the neighborhood of X as
N(X) = { y ∈ V : (x, y) ∈ E for some x ∈ X },
that is, the set of vertices adjacent to some member of X. Prove Hall's theorem: there exists a perfect matching in G if and only if |A| ≤ |N(A)| for every subset A ⊆ L.

6. **EXT 10-1**
There are two extended ways used to find the augmenting path that we have mentioned in class (refers to slides p.14, Unit 10), please design an efficient algorithm with the argument of second method to find the augmenting path that makes the flow maximum. Argue that your algorithm is correct and also analyze the time-complexity.

7. **Exercise 26.2-12**
Suppose that you are given a flow network G, and G has edges entering the
source s. Let f be a flow in G in which one of the edges v , sentering the source has fv , s=1. Prove that there must exist another flow f' with f'v , s=0 such that f= f' Give an O(E ) time algorithm to compute f' 0, given f , and assuming that all edge capacities are integers.

## HW14 ((p)11)

1. Show that any comparison-based algorithm needs (n log n) time to solve the
following problem: Given n points in the 2D plane, find the points that form the
smallest convex polygon from these points which can contain all the points on the
plane.(convex hull problem)

2. **Exercises 34.1-5**
Show that if an algorithm makes at most a constant number of calls to polynomialtime subroutines and performs an additional amount of work that also takes
polynomial time, then it runs in polynomial time. Also show that a polynomial
number of calls to polynomial-time subroutines may result in an exponential-time
algorithm.

3. **Exercises 34.1-6**
Show that the class $P$, viewed as a set of languages, is closed under union, intersection, concatenation, complement, and Kleene star. That is, if $L_1, L_2 \in P$, then $L_1 \cup L_2 \in P$, $L_1 \cap L_2 \in P$, $L_1L_2 \in P$, $\bar L_1 \in P$, and $L_1^* \in P$.

4. **Exercises 34.2-3**
Show that if HAM-CYCLE ∈ P, then the problem of listing the vertices of a Hamiltonian
cycle, in order, is polynomial-time solvable.
(Note 1: HAM-CYCLE is defined as “Does a graph G have a Hamiltonian cycle?”)
(Note 2: “HAM-CYCLE ∈ P” means that HAM-CYCLE is polynomial-time solvable.)

5. **Exercises 34.2-7**
Show that the Hamiltonian-path problem can be solved in polynomial time on directed
acyclic graphs. Give an efficient algorithm for the problem.

6. **Exercises 34.2-9**
Prove that P ⊆ co-NP. (Hint: P ⊆ NP ∩ co-NP.)

7. **Exercises 34.2-10**
Prove that if NP≠co-NP, then P≠NP.

## HW15 ((p)11)
1. **Exercises 34.4-7**
Let 2-CNF-SAT be the set of satisfiable Boolean formula in CNF with exactly 2 literals per
clause. Show that 2-CNF-SAT ∈ P. Make your algorithm as efficient as possible.
(Hint: Observe that x ∨ y is equivalent to ¬x → y. Reduce 2-CNF-SAT to an efficiently
solvable problem on a directed graph.)
**(Note: To show a problem is NP-complete, you have to show the problem is NP first.)

2. **Exercises 34.2-6**
A hamiltonian path in a graph is a simple path that visits every vertex exactly once.
(a). Show that the language HAM-PATH = { (G, u, v): there is a hamiltonian path from
u to v in graph G } belongs to NP.
(b). Show that the Hamiltonian path problem is NP-complete.
(Hint: Reduce from HAM-CYCLE.)

3. **Exercises 34.5-1**
The subgraph-isomorphism problem takes two undirected graphs G1 and G2
, and it asks
whether G1
is isomorphic to a subgraph of G2
. Show that the subgraph -isomorphism
problem is NP-complete.

4. **Exercises 34.5-2**
Given an integer m x n matrix A, and an integer m-vector b, the 0-1 integer- programming
problem asks whether there exists an integer n-vector x with elements in the set {0, 1} such
that Ax ≤ b. Prove that 0-1 integer programming problem is NP-complete.
(Hint: Reduce from 3-CNF-SAT.)

5. **Exercises 34.5-7**
The longest-simple-cycle problem is the problem of determining a simple cycle (no repeated
vertices) of maximum length in a graph. Formulate a related decision problem, and Show
that the decision problem is NP-complete.

6. **Exercises 35.1-4**
Give an efficient greedy algorithm that finds an optimal vertex cover for a tree in linear time.

7. **JIN-WEN HELL**
用上課所提到的BK-0演算法跑此圖例，並寫下執行過程。