Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
IE 332 - Homework #1 Due: Sept 29th, 11:59pm EST Read Carefully. Important! As outlined in the course syllabus this homework is worth 9% of your final grade. The maximum attainable mark on this homework is 165. As was also outlined in the syllabus, there is a zero tolerance policy for any form of academic misconduct. The assignment can be done individually or in pairs. You must upload your homework on time for it to be graded. No late assignments will be accepted. Only the last uploaded version of your assignment will be graded. NOTE: You should aim to submit no later than 30 minutes before the deadline, as there could be last minute network traffic that would cause your assignment to be late, resulting in a grade of zero. You must use the provided LATEX template on Brightspace to submit your assignment. No exceptions. Page i of i IE 332 Homework #1 Due: Sept 29 2021 1. This question is meant to reinforce your understanding of how a CPU executes program code by focusing on the low-level instructions it executes, versus higher-level instructions you would use in a programming language such as R. You will use the hypothetical assembly language outlined below in Table 1, in addition to 10 registers referred to by $r0, . . . ,$r15, and system RAM as needed. instruction meaning example add reg1, reg2, reg3 reg1 = reg2 + reg3 add $r0, $r1, $r2 sub reg1, reg2, reg3 reg1 = reg2− reg3 sub $r0, $r1, $r2 div reg1, reg2, reg3 reg1 = reg2/reg3 div $r0, $r1, $r2 divi reg1, reg2, reg3 reg1 = reg2/reg3, truncates fractional values divi $r0, $r1, $r2 mul reg1, reg2, reg3 reg1 = reg2 ∗ reg3 mul $r0, $r1, $r2 muli reg1, reg2, x reg1 = reg2 ∗ x, where x is some integer mul $r0, $r1, 4 addi reg1, reg2, x reg1 = reg2 + x, where x is some integer addi $r0, $r1, 5 subi reg1, reg2, x reg1 = reg2− x, where x is some integer subi $r0, $r1, 5 divr reg1, reg2, x reg1 = reg2/x, where x is real, truncates result divr $r0, $r1, 2 mod reg1, reg2, reg3 reg1 = reg2 mod reg3 mod $r0, $r1, $r2 mov reg1, reg2 reg1 = reg2 mov $r0, $r1 label: create a reference label in the code main: name: .type, value create .type variable in RAM where name = value var1: .word 5 lw reg, RAM_source move word from RAM to a register lw $r4, var1 sw reg, RAM_source move word from register to RAM sw $r4, var1 la reg, RAM_source move address of RAM to a register la $r4, var1 sa reg, RAM_source move address in register to RAM sa $r4,var1 b label jump to a label in the program b main beq reg1,reg2,label jump to label if reg1 = reg2 beq $r0,$r1,main blt reg1,reg2,label jump to label if reg1 < reg2 blt $r0,$r1,main bgt reg1,reg2,label jump to label if reg1 > reg2 bgt $r0,$r1,main bqe reg1,reg2,label jump to label if reg1 ≥ reg2 bqe $r0,$r1,main ble reg1,reg2,label jump to label if reg1 ≤ reg2 ble $r0,$r1,main bne reg1,reg2,label jump to label if reg1 ̸= reg2 bne $r0,$r1,main print reg print contents of register to screen print $r0 prints reg print string pointed to in register to screen prints $r0 read reg get keyboard input (after ENTER pressed); store in reg read $r0 .wordspace size allocates mory of size integers, all initialized to zero arr: .wordspace 10 done end of program Table 1: Hypothetical assembly language *NOTE: for lw if RAM_source is an integer instead of a memory address, or reg1 and/or reg2 in beq, blt, bgt, bge,ble, bne, then it will be automatically interpreted as such. For instance, lw $r1, 4, will be an equivalent instruction to setting $r1=4. Also, potential variable types include .word (for integers or floats), .bit (for bits), .asciiz (for strings/character arrays - noting that each character has an associated bit pattern and can be interpreted as an integer as well). Furthermore, a sequence of comma separated integers is accepted as valid input, allowing you to create integer arrays, e.g., arr: .asciiz 10,13,12. Arrays are indexed from 1, and accessing a value from an array is done by referring to the RAM_source as array_name[index] (e.g., if loading an array value, use lw $r1, A[1] where A is the array name). The size of the array is stored at position 0, (e.g. A[0]). Ex. computing the first n Fibonacci numbers (Fn = Fn−1 + Fn−2 for n > 0, F1 = 1 and F2 = 1): string1: .asciiz “The result is: ” value: .word 0 main: read $r9 ble $r9, 0, end lw $r0, value addi $r0, $r0, 1 beq $r9, 1, end mov $r2, $r0 mov $r1, $r2 lw $r8, 1 loop: add $r0, $r1, $r2 mov $r2, $r1 mov $r1, $r0 addi $r8, $r8, 1 beq $r9, $r8, end b loop end: sw $r0, value la $r7, string1 prints $r7 print $r0 done (a) (20 points) Translate the following C program into assembly instructions without adding personal insight or design modifications - translate it in a way that a compiler would. When submitting your results show a table with two columns: (1) the original C program, (2) your assembly code. You can increase the page margins or reduce font size to 10pt to improve readability, if needed. You do not have to create assembly code for printf (replace directly with assembly instruction). Do NOT debug the C code. HINTS: (1) start your translation from main(), not line 1. (2) consider negation of conditional statements. 1 double findOddEven ( in t arr [ ] , s i z e_t arr_len ){ 2 i n t odds [ arr_len / 2 ] ; i n t evens [ arr_len / 2 ] ; // Odd and Even numbers 3 i n t counterOdd = 0 , counterEven = 0 ; 4 f o r ( in t i = 0 ; i < arr_len ; i++ ){ 5 i f ( arr [ i ] % 2 == 0){ 6 evens [ counterEven ] = arr [ i ] ; counterEven += 1; 7 } e l s e { 8 odds [ counterOdd ] = arr [ i ] ; counterOdd += 1; 9 } 10 } 11 p r i n t f ( ”The odd array = ” ) ; 12 f o r ( in t i = 0 ; i < counterOdd ; i++ ){ p r i n t f ( ”%d\t ” , odds [ i ] ) ; } 13 p r i n t f ( ”The even array = ” ) ; 14 f o r ( in t i = 0 ; i < counterEven ; i++ ){ p r i n t f ( ”%d\t ” , evens [ i ] ) ; } 15 16 return counterOdd/CounterEven ; 17 } 18 i n t main ( ) { 19 i n t arr [ ] = {1 , 2 , 3 , 4 , 5 , 6} ; 20 i n t arr_len = s i z e o f ( arr ) / s i z e o f ( arr [ 0 ] ) ; 21 double d = findOddEven ( arr , arr_len ) ; 22 d = d + 2 ∗ d 23 p r i n t f ( ”%d” ,d) ; 24 return 0 ; 25 } IE 332 Homework #1 Page 2 of 10 (b) (4 points) Provide pseudocode for the given C program. Be mindful of the balance between too little and too much detail. That is focus on conveying the idea of what is being done, not necessarily how it is done in C! (c) (4 points) Convert the given C code to equivalent but fewest lines of R code to print the same result. Use existing R function(s) or you will lose points. Do not line-by-line convert the C code! You should need no more than 7 lines of R code. (d) Suppose that the C algorithm is re-executed for an arr[] of odd length. i. (5 points) Alter the C code, if needed, to accommodate this change and yield accurate output. If not needed, argue why. ii. (5 points) Re-translate the C code from (i), if any changes to it were made. If no changes are required argue why. iii. (5 points) Provide a tight bound for the worst-case runtime and space complexity of the original C code. Briefly, but sufficiently, justify your answers. IE 332 Homework #1 Page 3 of 10 2. Divide and conquer. After every snow at Purdue, n Purdue staff members apply salt to k campus sidewalks. Suppose we have a sorted (in increasing order) array T = [t1, t2, . . . , tk] where ti is the amount of time needed to apply salt to sidewalk i, i = 1, . . . , k, and that each staff member can only salt sidewalks that are of consecutive numbers (e.g., sidewalks 1, 2 and 3, but not 1 and 3). Also, each sidewalk can be salted by only one staff member. Purdue is seeking a solution to salt all the sidewalks such that the maximum time any staff member is outside salting is minimized, and have assigned you to solve the problem for them. After much thought you have decided to apply the below-sketched modification to the iterative binary search algorithm (it may help to draw a picture to visualize the process using an example T): 1. if the number of sidewalks is less than the number of staff members then the problem is trivially solved as the largest value in T ; otherwise, it is not trivial and you need find the minimum value in [0,∑i ti]. 2. The remainder of the algorithm is very similar to that in lecture 9 slide 25, noting instead of testing if x < A[m] or not, you will be testing whether there is an allocation of k sidewalks among n members of staff using the isFeasible(T, n, x) function provided in part (b).