# BEST代写-线上编程学术专家

Best代写-最专业靠谱代写IT | CS | 留学生作业 | 编程代写Java | Python |C/C++ | PHP | Matlab | Assignment Project Homework代写

# C语言代写 | CS 211: Final : 100 points

### C语言代写 | CS 211: Final : 100 points

CS 211: Final : 100 points
Full Name Here:
RUID:
Question Max Points Points
1 20
2 12
3 23
4 22
5 23
6 (Extra Credit) 40
1
Problem 1: C Programming (20 points)
1. (5 points) Complete the following function to multiply two matrices and returns the pointer to the
result matrix. The arguments to the function are pointers to matrix A and matrix B. The number
of rows and columns in matrix A are provided as arguments m1 and m2. The number of rows and
columns in matrix B are provided as arguments n1 and n2. You have to allocate space for the result
matrix. Your code should compile and should not experience segmentation faults.
int** matrix_multiply(int** A, int **B, int m1, int m2, int n1, int n2){
2
2. (5 points) You are implementing a hash table with open chaining where each node is of the following
type.
struct node{
int key;
int value;
struct node * next;
};
Given that the hash table is implemented as an array of pointers to hash table nodes, implement the
following hash search function to search a key in the hash table. If the key is found, the search
function returns the value associated with the key. Otherwise, returns -1. The value MAX ENTRIES
is the number of buckets in the hash table. Your code should carefully handle all corner cases, should
compile, and should not experience segmentation faults on any input. Use the modulo function as the
hash function.
struct node * hash_table[MAX_ENTRIES];

int hash_search(int key){
3
3. (10 points) Complete the function traverse below that prints the values at each node of the tree in
breadth-first order. In breadth-first order, all the nodes at height h are printed before the nodes at
height h+1. Nodes at the same height are printed in left-to-right order.
If necessary, you may define additional functions and data structures. The tree passed to traverse
should not be modified.
struct Tree {
int value;
struct Tree *left;
struct Tree *right;
};
void traverse(struct Tree *tree){
4
Problem 2: Data Representation (12 points)
1. (5 points) Write code for a function with the following prototype to perform rotating left shift. Your
function should follow bit-level integer coding rules. It is undefined behavior in C if the shift amount
is greater than or equal to the bitwidth of the data type. Be careful of the case n = 0.
/* Do rotating left shift. Assume 0<= n < w.
Examples when x = 0x12345678 and w =32:
n = 4 -> 0x23456781
n= 20-> 0x67812345
*/
unsigned rotate_left(unsigned x, int n)
5
2. (2 points) Can every 32-bit integer be represented as a 32-bit float? Give reasons.
3. (5 points) You are given a 5-bit floating representation based on IEEE-754 representation with one
sign bit, two exponent bits and two fraction bits. Writing the bit pattern is sufficient.
• What is the smallest positive number in this representation?
• What is the smallest normalized positive value in this representation?
• What is the largest normalized positive value in this representation?
• What is the largest denormal positive value in this representation?
• What is positive infinity in this representation?
6
Problem 3: Assembly (23 points)
1. (7 points) Write C code for the following assembly code.
.globl test
.type test, @function
test:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %eax
movl 12(%ebp), %edx
cmpl \$-3, %eax
jge .L2
cmpl %edx, %eax
jle .L3
imull %edx, %eax
jmp .L4
.L3:
leal (%edx, %eax), %eax
jmp .L4
.L2:
cmpl \$2, %eax
jg .L5
xorl %edx, %eax
jmp .L4
.L5:
subl %edx, %eax
.L4:
popl %ebp
ret
7
2. (8 points) Consider the assembly for a switch statement below.
.globl switcher
.type switcher, @function
switcher:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %edx
movl 12(%ebp), %eax
movl 16(%ebp), %ecx
cmpl \$7, %edx
ja .L8
jmp *.L7(,%edx,4)
.section .rodata
.align 4
.align 4
.L7:
.long .L3
.long .L8
.long .L4
.long .L8
.long .L5
.long .L6
.long .L8
.long .L4
.text
.L5:
movl \$4, %eax
jmp .L8
.L6:
movl %eax, %ecx
xorl \$15, %ecx
.L3:
leal 112(%ecx), %eax
jmp .L8
.L4:
leal (%ecx,%eax), %eax
sall \$2, %eax
.L8:
popl %ebp
ret
Complete the following C function for the above assembly code.
int switcher(int a, int b, int c ){
switch(a){
8
/* Extra page for work */
9
3. (8 points) The following is the binary given for your bomblab assignment. However, we have simplified the binary so that you can solve this assignment without gdb. Your goal is to find all inputs that
defuse the bomb. Each input consists of 3 items: an integer, a character, and a character.
.LC0:
.string “%d %c %c”
.text
.globl phase1
.type phase1, @function
phase1:
pushl %ebp
movl %esp, %ebp
subl \$56, %esp
leal -14(%ebp), %eax
movl %eax, 16(%esp)
leal -13(%ebp), %eax
movl %eax, 12(%esp)
leal -12(%ebp), %eax
movl %eax, 8(%esp)
movl \$.LC0, 4(%esp)
movl 8(%ebp), %eax
movl %eax, (%esp)
call sscanf
movl -12(%ebp), %edx
leal 3(%edx), %eax
cmpl \$9, %eax
je .L9
.L2:
leal 0xf(,%edx,4), %eax
cmpl \$23, %eax
je .L9
.L5:
leal -0x2(%eax, %edx, 2), %eax
cmpl \$97, %eax
je .L9
.L8:
call explode_bomb
.L9:
leave
ret
• (1 point) How many inputs solve the bomb?
10
• (7 points) List all inputs that solve the bomb. It is only necessary to list inputs that need a distinct
integer input.
11
Problem 4: Caches (22 points)
1. You are given a cache with n sets, associativity of a and a block size of b. Given an unsigned 64-bit
convert the address to a string. You are allowed to use the log2 function if necessary. The prototype
of the log2 function is given below.
double log2 (double);
/* (4 points) Compute the set index */
unsigned long compute_set_index (unsigned long addr){
}
/* (2 points) Compute the tag bits */
unsigned long compute_tag (unsigned long addr){
}
12
2. Consider a machine with a direct mapped cache that has 8 sets and has a block size of 4 bytes. Memory
addresses are 13 bits and each memory access from a processor requests a byte from the cache. The
contents of the cache are as follows, with all numbers in hexadecimal.
Cache Line
Set Index Tag Valid Byte 0 Byte 1 Byte 2 Byte 3
0 09 1 30 F4 72 AB
1 38 1 78 3F 92 D4
2 6E 0 – – – –
3 06 0 1F DA 40 C5
4 C7 1 – – – –
5 71 1 D3 9A 0B 12
6 91 1 – – – –
7 46 0 5C 80 B3 59
(a) (1 point) Calculate the size of the cache in bytes.
(b) (1 point) Indicate the number of bits used to determine
• the block offset:
• set index:
• tag:
(c) (4 points) A program running on this machine makes memory references at the addresses specified in the first column of the following table. For each memory reference indicate the block
offset, set index and tag. Furthermore, indicate whether a cache hit occurs and the byte returned.
The byte returned is – for a miss.
Address Set index Block offset Tag Cache hit? (Y/N) Byte returned
0x0E35
0x0DD5
0x1FE4
0x0705
13
(d) (3 points) If we redesign the cache by increasing the associativity to 4 while keeping the total
cache size exactly the same as above, how many bits will you use for the following:
• Tag:
• Set index:
• Block offset:
(e) (2 points) What is spatial locality and temporal locality?
3. You are given a system where accessing memory takes 500 cycles per memory access. A hit in the
cache takes 10 cycles and the latency of a cache miss (including the time to search in the cache and
getting the data from memory) is 500 cycles.
• (2 points) You run the program by completely removing the caches. How many cycles does the
program take?
• (2 points) You run the program with caches and 90% of the accesses are hits in the cache and
the rest are misses. How many cycles will the program take with caches?
• (2 points) Assume that your program takes 10 hours to run on a machine without caches. How
long would it take on a machine with caches?
14
Problem 5: Logic Design (23 points)
1. (8 points) You are supposed to design a circuit which takes four bits as input (ABCD) and the bits are
interpreted as an unsigned integer. Here, A is the most significant bit and D is the least significant
bit. Design a combinational circuit that outputs a 1 if the number is divisible by 3. Clearly show truth
table. Simplification using K-maps.
15
2. (2 points) Implement the function F = A¯.B + A.B¯ using a 2:1 multiplexer.
3. (1 point) Implement the function F = A¯.B + A.B¯ using a 2:4 decoder.
16
4. (12 points) Design a Moore finite state machine that detects 1 0 1 in consecutive digits in the input
stream of 0’s and 1’s received every clock cycle. The circuit should output a 1 when it detects 1 0 1 as
consecutive digits. Implement the FSM using a combination of sequential and combinational logic.
Clearly show your work. Draw the truth table for inputs, outputs and your states. Draw the K-map for
everything. Clearly indicate how many flip flops you are going to use. Draw the final circuit with the
flip flops.
INPUT : 0 1 0 1 0 1 1 0 1 0 0….
OUTPUT: 0 0 0 1 0 1 0 0 1 0 0….
17
/* Extra page for work */
18
Extra Credit Problems (40 points)
1. (15 points) Identify the inputs that defuse the following bomb. There are 3 different inputs that solve
this bomb. Your goal is to identify the each of the inputs to solve the bomb.
.LC0:
.string “%d %c %c”
.text
.globl phase1
.type phase1, @function
phase1:
pushl %ebp
movl %esp, %ebp
subl \$56, %esp
leal -14(%ebp), %eax
movl %eax, 16(%esp)
leal -13(%ebp), %eax
movl %eax, 12(%esp)
leal -12(%ebp), %eax
movl %eax, 8(%esp)
movl \$.LC0, 4(%esp)
movl 8(%ebp), %eax
movl %eax, (%esp)
call sscanf
movl -12(%ebp), %eax
cmpl \$7, %eax
je .L6
cmpl \$9, %eax
jne .L3
movl string, %eax
movzbl 10(%eax), %eax
cmpb -13(%ebp), %al
je .L6
call explode_bomb
.L3:
cmpl \$41, -12(%ebp)
jne .L4
movl string, %eax
movzbl 9(%eax), %edx
cmpb -13(%ebp), %dl
jne .L5
movzbl 13(%eax), %eax
cmpb -14(%ebp), %al
je .L6
.L5:
call explode_bomb
.L4:
call explode_bomb
.L6:
leave
ret
19
.globl string
.section .rodata.str1.1
.LC1:
.string “CS 211 students are awesome!”
.data
.align 4
.type string, @object
.size string, 4
string:
.long .LC1
.ident “GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-16)”
.section .note.GNU-stack,””,@progbits
2. (7 points) You are asked to create a three dimensional matrix with each dimension having 10, 20, and
30 elements respectively. When given this questions, student P comes with the following solution
/* student P’s solution */
int ***A;
void init (){
int j, k;
A = (int ***)malloc(10* sizeof(int**));
for(j = 0; j< 20; j++){
int** temp = (int**) malloc(20 * sizeof(int*));
A[j] = temp;
for(k = 0; k < 30; k++){
int * temp2 = (int*) malloc(30 * sizeof(int));
A[j][k] = temp2;
}
}
}
Student Q comes up with the following solution:
int *A;
void init(){
A = (int*) malloc(10* 20*30 * sizeof(int));
}
• (2 points) Which solution has the best possible performance and why?
20
• (2 points) Let’s say you want to logically access the matrix element A. How do you do
it in Student P’s solution?
• (3 points) How do you access the matrix element A in Student Q’s solution?
3. (18 points) Consider the following example, where P, Q, R are constants declared with #define:
int A[P][Q][R];
int test_element(int i, int j, int k, int *dest){
*dest = A[i][j][k];
return sizeof(A);
}
GCC generates the following assembly code:
.globl test_element
.type test_element, @function
test_element:
pushl %ebp
movl %esp, %ebp
movl 12(%ebp), %eax
leal (%eax,%eax,4), %edx
leal (%eax,%edx,2), %edx
21
imull \$88, 8(%ebp), %eax
leal (%edx,%eax), %eax 