当前位置：网站首页>INT 102_ TTL 09

INT 102_ TTL 09

2022-04-21 22:06:00 【NONE_ WHY】

Question 01

1.1. Question

Apply Warshall’s algorithm to find the transitive closure of the following digraph
Graph

1.2. Solution

$R_0=\bigl(\begin{smallmatrix} {\color{Red} 0} & {\color{Red} 1}& {\color{Red} 0} &{\color{Red} 1} \\ {\color{Red} 0}& 0&0 &0 \\ {\color{Red} 1} & 0 & 0&1 \\ {\color{Red} 0} & 0 & 0 & 0 \end{smallmatrix}\bigr)$
$R_1=R_0 \vee (\bigl(\begin{smallmatrix} 0\\ 0\\ 1\\ 0 \end{smallmatrix}\bigr) \bigl(\begin{smallmatrix} 0 & 1 & 0 & 1 \end{smallmatrix}\bigr) ) =\bigl(\begin{smallmatrix} 0 & 1& 0 &1 \\ 0& 0&0 &0 \\ 1 & 0 & 0&1 \\ 0 & 0 & 0 & 0 \end{smallmatrix}\bigr) \vee \bigl(\begin{smallmatrix} 0 & 0 & 0 & 0\\ 0 & 0& 0 &0 \\ 0 & 1& 0 & 1\\ 0 & 0 & 0 & 0 \end{smallmatrix}\bigr) = \bigl(\begin{smallmatrix} 0 & {\color{Red} 1}& 0& 1\\ {\color{Red} 0} & {\color{Red} 0} & {\color{Red} 0} &{\color{Red} 0} \\ 1 & {\color{Red} 1}& 0 & 1\\ 0 & {\color{Red} 0}& 0 & 0 \end{smallmatrix}\bigr)$
$R_2= R_1 \vee(\bigl(\begin{smallmatrix} 1\\ 0\\ 1\\ 0 \end{smallmatrix}\bigr) \bigl(\begin{smallmatrix} 0 & 0 & 0& 0 \end{smallmatrix}\bigr) ) =\bigl(\begin{smallmatrix} 0 & 1 & 0 &1 \\ 0& 0 & 0 &0 \\ 1 & 1& 0& 1\\ 0 & 0& 0 & 0 \end{smallmatrix}\bigr) \vee \bigl(\begin{smallmatrix} 0 & 0 & 0 &0 \\ 0 &0 & 0 & 0\\ 0 &0 & 0&0 \\ 0 &0 &0 & 0 \end{smallmatrix}\bigr) = \bigl(\begin{smallmatrix} 0 & 1 & {\color{Red} 0} &1 \\ 0& 0 & {\color{Red} 0} &0 \\ {\color{Red} 1} & {\color{Red} 1}& {\color{Red} 0}& {\color{Red} 1}\\ 0 & 0& {\color{Red} 0} & 0 \end{smallmatrix}\bigr)=R_1$
$R_3= R_2 \vee(\bigl(\begin{smallmatrix} 0\\ 0\\ 0\\ 0 \end{smallmatrix}\bigr) \bigl(\begin{smallmatrix} 1 & 1 & 0& 1 \end{smallmatrix}\bigr) ) =\bigl(\begin{smallmatrix} 0 & 1 & 0 &1 \\ 0& 0 & 0 &0 \\ 1 & 1& 0& 1\\ 0 & 0& 0 & 0 \end{smallmatrix}\bigr) \vee \bigl(\begin{smallmatrix} 0 & 0 & 0 &0 \\ 0 &0 & 0 & 0\\ 0 &0 & 0&0 \\ 0 &0 &0 & 0 \end{smallmatrix}\bigr) = \bigl(\begin{smallmatrix} 0 & 1 &0 &{\color{Red} 1} \\ 0& 0 & 0&{\color{Red} 0} \\ 1&1& 0& {\color{Red} 1}\\ {\color{Red} 0} & {\color{Red} 0}& {\color{Red} 0} & {\color{Red} 0} \end{smallmatrix}\bigr)=R_2$
$R_4= R_3 \vee(\bigl(\begin{smallmatrix} 1\\ 0\\ 1\\ 0 \end{smallmatrix}\bigr) \bigl(\begin{smallmatrix} 0 & 0 & 0& 0 \end{smallmatrix}\bigr) ) =\bigl(\begin{smallmatrix} 0 & 1 & 0 &1 \\ 0& 0 & 0 &0 \\ 1 & 1& 0& 1\\ 0 & 0& 0 & 0 \end{smallmatrix}\bigr) \vee \bigl(\begin{smallmatrix} 0 & 0 & 0 &0 \\ 0 &0 & 0 & 0\\ 0 &0 & 0&0 \\ 0 &0 &0 & 0 \end{smallmatrix}\bigr) = \bigl(\begin{smallmatrix} 0 & 1 & 0 &1 \\ 0& 0 & 0 &0 \\ 1 & 1& 0& 1\\ 0 & 0& 0 & 0 \end{smallmatrix}\bigr) = R_3$

Question 02

2.1. Question

Assuming that the set of possible list is {a, b, c, d}, sort the following list in alphabetical order by the counting algorithm:
- List: b, c, d, c, b, a, a, b

2.2. Solution

Auxiliary array C

Counting table === Not accumulated
a	b	c	d
2	3	2	1

Counting table === Accumulated

a b c d

2 5 7 8

Fill the new array in the reverse order of the original array B

b, c, d, c, b, a, a, b
	Changes in Output Array								Chaenges in Auxiliary array C
	1	2	3	4	5	6	7	8	a	b	c	d
Step 0									2	5	7	8
Step 1					b				2	4	7	8
Step 2		a			b				1	4	7	8
Step 3	a	a			b				0	4	7	8
Step 4	a	a		b	b				0	3	7	8
Step 5	a	a		b	b		c		0	3	6	8
Step 6	a	a		b	b		c	d	0	3	6	7
Step 7	a	a		b	b	c	c	d	0	3	5	7
Step 8	a	a	b	b	b	c	c	d	0	2	5	7
a, a, b, b, b, c, c, d

Print B
- a, a, b, b, b, c, c, d

Question 03

3.1. Question

Consider the problem of searching for genes in DNA sequences using Horspool’s algorithm. A DNA sequence is represented by a text on the alphabet {A, C, G, T}, and the gene or a gene segment is a pattern
- 1) Construct the shift table for the following gene segment
  - TCCTATTCTT
- 2) Apply Horspool’ s algorithm to locate the pattern in the following DNA sequence
  - TTATAGATCTGGTATTCTTTTATAGATCTCCTATTCTT
  - CTATTCTT

3.2. Solution

1) Shift Table
- front m-1 The shortest distance from a character to the end , If it does not appear, it is the length of the string
- front m-1 One failed
  
  A C G T
  
  5 2 10
  1

2）Horspool’ s algorithm

Question 04

4.1. Question

Using a gap penalty of d=-5 and scoring matrix as below

	A	C	G	T
A	2	-7	-5	-7
C	-7	2	-7	-5
G	-5	-7	2	-7
T	-7	-5	-7	2

And applying dynamic programming
- 1) to find the optimal global alignment of AATG and AGC
- 2) to Find the optimal local alignment of AATG and AGC

4.2. Solution

1) Optimal global alignment
- Initialize 【 initialization 】
  - $F(i,0)=i\times Gap\ Penalty$
  - $F(0,j)=j\times Gap\ Penalty$
- Fill Score Matrix & Sign Matrix 【 Fill in the form 】
  -  $F(i,j)=\max \begin{cases} F(i-1,j-1)+s(x_i,y_j) \\ F(i-1,j)+d \\ F(i,j-1)+d\end{cases}$
  - $B[i,j]= \begin{cases} \nwarrow & \text{ if } x_i=y_j \\ \ \uparrow & \text{ if } C[i-1,j]\geq C[i,j-1]\\ \ \downarrow& \text{ if } C[i-1,j]< C[i,j-1] \end{cases}$
- Trace back 【 to flash back 】
  - from B[ i , j ] The last position can be traversed forward i For the line ,j Column
    - The arrow is , Record ,i--,j--
    - The arrow is ↑ , skip ,i--
    - The arrow is ←, skip ,j--
  - until i = 0 perhaps j = 0 Stop when , The characters of all records are the required
- Result
  - A A T G -
    
    A - - G C
  - A A T G -
    
    - A - G C
2) Optimal local alignment
- Initialize 【 initialization 】
  - 
  - 
- Fill Score Matrix & Sign Matrix 【 Fill in the form 】
  -  $F(i,j)=\max \begin{cases} F(i-1,j-1)+s(x_i,y_j) \\ F(i-1,j)+d \\ F(i,j-1)+d \\0\end{cases}$
  - $B[i,j]= \begin{cases} \nwarrow & \text{ if } x_i=y_j \\ \ \uparrow & \text{ if } C[i-1,j]\geq C[i,j-1]\\ \ \downarrow& \text{ if } C[i-1,j]< C[i,j-1] \end{cases}$
- Trace back 【 to flash back 】
  - from Maximum Of B[ i , j ] Start traversing forward i For the line ,j Column
    - The arrow is , Record ,i--,j--
    - The arrow is ↑ , skip ,i--
    - The arrow is ←, skip ,j--
  - until i = 0 perhaps j = 0 Stop when , The characters of all records are the required
- Result
  - A
    
    A
  - A
    
    A
  - G
    
    G

Question 05

5.1. Question

Suppose there are 10 people in a room. Each person shakes hands with some other people in the room. Prove that the number of people having an odd number of handshakes is even.
(Challenge: This puzzle is equivalent to the question in an undirected graph, prove that the number of vertices with odd degree is even". Try to think why the two questions are equivalent.)

5.2. Solution

Ideas
- people ==> The vertices
- handshake ==> No to the edge
- graph theory ：n Vertices correspond to (n-1) side
General case: there are n>0 people in a room. Each person shakes hands with some other people in the room. Prove that the number of people having an odd number of handshakes is even.
For such a problem we construct a graph G=(V, E), where each vertex in V represents one person. (vi, vj) is in E if and only if vi and vj shake hands. Then deg(vi) is the number of persons with which vi shakes hands.
With such representation, the problem now can be rephrased as follows:
- In the graph G=(V, E), the number of vertices with odd degree is even.
By the fact that the sum of all degrees in a graph is even, the number of vertices with odd degree must be even