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

INT 102_TTL 09

2022-04-21 22:05: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
- 记数表格 === 未累加
  
  a b c d
  
  2 3 2 1
- 记数表格 === 已累加
  
  a b c d
  
  2 5 7 8

按原数组倒序填充新数组 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
- 前 m-1 个字符到末尾的最短距离，未出现则为该字符串长度
- 前 m-1 个中失败
  
  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 【初始化】
  - $F(i,0)=i\times Gap\ Penalty$
  - $F(0,j)=j\times Gap\ Penalty$
- Fill Score Matrix & Sign Matrix 【填表】
  -  $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 【回溯】
  - 从B[ i , j ] 最后一个位置开始往前遍历即可 i 为行，j 为列
    - 箭头是，记录，i--，j--
    - 箭头是 ↑ ，跳过，i--
    - 箭头是←，跳过，j--
  - 直到 i = 0 或者 j = 0 时停止，所有记录的字符即为所求
- Result
  - A A T G -
    
    A - - G C
  - A A T G -
    
    - A - G C
2) Optimal local alignment
- Initialize 【初始化】
  - 
  - 
- Fill Score Matrix & Sign Matrix 【填表】
  -  $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 【回溯】
  - 从最大的 B[ i , j ] 开始往前遍历即可 i 为行，j 为列
    - 箭头是，记录，i--，j--
    - 箭头是 ↑ ，跳过，i--
    - 箭头是←，跳过，j--
  - 直到 i = 0 或者 j = 0 时停止，所有记录的字符即为所求
- 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

思路
- 人==>顶点
- 握手==>无向边
- 图论：n个顶点对应(n-1)条边
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