# Algorithm | 计算机组成原理 – HW

### HW

Algorithm | 计算机组成原理- 这个题目属于一个计算机组成原理的代写任务, 是比较典型的数制换算等代写方向

#### a

The number of bits are bits.

#### b

The number of hexadecimal characters is.

#### c

###### ii

####### 0: 0

####### 3: 10000

####### 6: 100010

####### 9: 100011

####### C: 10010

####### E: 10011

####### 7: 10100

####### D: 101010

####### A: 1010110

####### 2: 1010111

####### B: 101100

####### 4: 1011010

####### 5: 1011011

####### 8: 101110

####### 1: 101111

####### F: 11

###### iii

the total number of bits is

bits

#### 2

##### a

Appearently, the answer for the permutation of length is.

##### b

According to a) since in terms for , there are one-pass permutations. So the length of bits is

##### c

We can encoding the permutation in these way:

##### d
• for [2,1,4,3,5,6]:[0,1,0,1,1]
• for [1,4,2,3,6,5]:[1,0,1,1,0]
• for [1,2,3,5,4,6]:[1,1,1,0,1]
##### e
• For 00110, it is non-decodable.
• For 10101, it is[2,1,4,3,6,5]
• For 11110, it is non-decodable.

#### 3

##### a
###### i

as it must need 6 ‘N’s and 9 ‘E’s, the bits is 15.

###### ii

####### 001111010101110

###### iii

####### 100011100011111

iv

EEEEEEEENENNNNN

###### v

####### NENNNENENENNNEE

##### b

The theoretically optimal number of bits needed to uniquely encode each path is .

##### c

The encoding Algorithm is as follow:

``````EncodePermutation(a[1],...a[n] array of integers)
``````
1. For i from 2 to n
2. If a[i]>a[i-1] then
3. let i-1-th bit of encoding as 1
4. else
5. let i-1-th bit of encoding as 0
6. return code
##### d

The path is : ENNNEEENNNEEEEE

So for the process encoding:

E 1 N 0 N 0 N 0 E 1 E 1 E 1 N 0 N 0 N 0 E 1 E 1 E 1 E 1 E 1

So the code is 100011100011111

##### e

It is non-decodable.

#### 4

##### a

Since each letter in QWERTYUIOP needs four bits to encode, bits are required to encode each -character string over the alphabet

##### c
###### i

the encode for the string is 0000 0110 0111 0010 0100

###### ii

the encode for the string is 0100 0011 1000 0110 1001

``````EncodePath(a[1],...a[15] array of the path)
``````
1. For i from 1 to 15
2. If a[i]==’N’ then
3. the i-th bit of code is 0
4. else
5. the i-th bit of code is 1
6. return code
``````EncodeString(a[1],...a[n] array of the string)
``````
1. For i from 1 to n
2. If a[i]==’Q’ then
3. the i-th bit of code is 0000
4. else if a[i]==’W’ then
5. the i-th bit of code is 0001
6. else if a[i]==’E’ then
7. the i-th bit of code is 0010
8. else if a[i]==’R’ then
9. the i-th bit of code is 0011
10. else if a[i]==’T’ then
11. the i-th bit of code is 0100
12. else if a[i]==’Y’ then
13. the i-th bit of code is 0101
14. else if a[i]==’U’ then
15. the i-th bit of code is 0110
16. else if a[i]==’I’ then
17. the i-th bit of code is 0111
18. else if a[i]==’O’ then
19. the i-th bit of code is 1000
20. else if a[i]==’P’ then
21. the i-th bit of code is 1001 22.return code
###### iii

the decode for the string is QWERT.

###### iv

It is non-decodable.

##### d

According to the theory of huffman code construction, the number of bits required for the theoretically optimal encoding of each -character

string over the alphabet is

##### e

Let me assume the probability of each letter occuring in the string is equal. So we using huffman code to construct the code for each letter as follow:

• O 000
• P 001
• Q 0100
• W 0101
• E 0110
• R 0111
• T 100
• Y 101
• U 110
• I 111
###### i

for ‘QUIET’, the encode for it is 0100 110 111 0110 100

###### ii

for ‘TROUP’, the encode for it is 100 0111 000 110 001

###### iii

For 00000001001000110 the decode for it is non-decodable.

###### iv

For 10001001101010111 the decode for it is TQUYR