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. By electronically uploading this assignment to Gradescope you acknowledge these statements and accept any repercussions if in any violation of ANY Purdue Academic Misconduct policies. 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). • If feasible, save the splitting point and perform another iteration of the loop over the interval up to the previous splitting point (-1) • If infeasible, perform another iteration of the loop over the interval after the splitting point (+1) to the total time in T 3. Continue looping while the entire time span of T has not been analyzed; otherwise return the best splitting point/solution found. (a) (12 points) Provide the iterative pseudocode for your findHours(T,n) divide-and-conquer algorithm. (b) (15 points) A member of Purdue administration is not convinced of the correctness of the isFeasible algorithm, and after she brings it up, neither are you. In order to determine this you will devise a loop invariant to either identify incorrectness (and fix it), or prove that no errors exist. Require: array T of length k, n ≥ 0 integer, min ≥ 0 1: FUNCTION isFeasible(T, n, min) 2: staffNeeded = 1 3: currentHours = 0 4: for i = 1 to length(T) do 5: if T [i] > min then 6: return FALSE 7: end if 8: if currentHours+T [i] > min then 9: staffNeeded += 1 10: currentHours = T[i] 11: if staffNeeded > n then 12: return FALSE 13: end if 14: else 15: currentHours += T[i] 16: end if 17: end for 18: return TRUE IE 332 Homework #1 Page 4 of 10 (c) (6 points) Use a loop invariant to determine whether isFeasible would output the correct result if T was not sorted. (d) (5 points) Use the Master Theorem to determine the runtime complexity for the worst-case scenario of findHours(T,n). IE 332 Homework #1 Page 5 of 10 3. Provide a tight bound on the the worst case runtime for the following algorithms (recall that n =∞ is not the worst case scenario!). Be sure to clearly indicate: (i) what the worst case scenario is (ii) T (n) in the worst case (iii) tight bound on the worst case runtime complexity. Use as reference for what is expected of a solution the example in the file examples.pdf attached with Lecture 9 slides. Correct answers without proper justification will get zero points. (a) (8 points) Require: array A of length n 1: i = 0 2: if A[i] ≥ 0 then 3: i = 3 4: while i ≤ n do 5: do something Θ(i) 6: for j=1 to i do 7: do something Θ(j) 8: end for 9: i+ = 1 10: end while 11: else 12: x = max(A) # assume that max takes Θ(n) time 13: do something Θ(n4) 14: end if (b) (10 points) Require: array A of length n containing only integers (can be negative) 1: sum=0 2: for i = 0 to length(A) do 3: if A[i] % 2 ! = 0 then 4: for j = 0 to i by j = j3 + 1 do 5: A[j] = A[j]*3+1 6: sum = sum + A[i] - A[j] 7: end for 8: else 9: sum = sum + √ A[i] 10: do something Θ(√n) 11: A[i] = 2 12: end if 13: end for 14: return sum IE 332 Homework #1 Page 6 of 10 (c) (12 points) Require: n, r ∈ N and n > r > 0. A is an array with n elements and each element ∈ R+. 1: FUNCTION magicFun(n, r,A) 2: if r > n− r then 3: r = n− r 4: end if 5: for k=1 to r by k = k + 1 do 6: j = 1, i = k 7: while j < k + 1 do 8: i = i/A[j] 9: perform a O(2k) operation 10: if i < 1 then 11: break 12: end if 13: j = j + 1 14: end while 15: end for IE 332 Homework #1 Page 7 of 10 4. You are tasked with organizing a flight path for a cargo plane that must visit a number of cities; the plane starting city is given but it does not need to return to its starting airport. There are many places to fly to, each located somewhere on the Earth (i.e., points on a sphere), and your company desires the minimum total flight distance and constrained you to only visiting each city once. Consider a greedy algorithm that decides which city to fly to next based on how close it is to the current city the plane is at. That is, you are given a list of n cities L = {c0, c1, . . . , cn} and you can assume that you start at c0. Within the greedy algorithm you will maintain a list of visited cities V that is initially V = {c0}, and another list of cities U = L\V that you haven’t visited. Assuming you are at an arbitrary city c∗ the next city to visit will then correspond to argmini∈U d(c∗, ci) where the distance between points p1 and p2 on a sphere is given by d(p1, p2) = arccos (p1 · p2) – · represents a dot product operation. The algorithm continues until all cities are visited. (a) (8 points) Use a loop invariant to show whether or not the greedy algorithm will correctly guarantee that it will find the shortest flight path. (b) (25 points) Whether or not your algorithm is guaranteed to find an optimal solution, it may nonetheless be capable of usually finding a good solution. To experiment with the algorithm in a practical setting you will use R to program it, and will need to install the rgl, purrr, and pracma packages. First, generate a problem instance with 50 random points as shown below: library(rgl) library(purrr) library(pracma) # This generates 50 points on the sphere set.seed(42168) n=50 theta=runif(n,0,2*pi) z=runif(n,-1,1) x=sqrt(1-z^2)*cos(theta) y=sqrt(1-z^2)*sin(theta) df=data.frame(x,y,z) m=as.matrix(df) # To plot points on the sphere, and draw a path between the first two points. spheres3d(0,0,0,radius=1,lit=F,color="white") spheres3d(0,0,0,radius=1.01,lit=FALSE,color="black",front="lines") spheres3d(x,y,z,col="yellow",radius=0.02) #arc3d(c(x[1],y[1],z[1]),2*c(x[1],y[1],z[1]),c(0,0,0),1,n=100,col="blue") #arc3d(c(-1,-1,-1),2*c(1,1,1),c(0,0,0),1,n=100,col="blue") spheres3d(0,-1,0,col="red",radius=0.02) spheres3d(-1,0,0,col="red",radius=0.02) spheres3d(0,1,0,col="blue",radius=0.02) arc3d(c(0,-1,0),2*c(-1,0,0),c(0,0,0),1,n=100,col="red") arc3d(c(0,1,0),2*c(-1,0,0),c(0,0,0),1,n=100,col="red") IE 332 Homework #1 Page 8 of 10 Figure 1: Example plotted solution. The International Date Line is defined as the line through points {(0,−1, 0), (−1, 0, 0), (0, 1, 0), } where (0,1,0) is the equivalent of the North Pole. To show your solution, gen- erate a plot that shows the links (in blue) that were traveled in the order they were traveled. Also output the total distance traveled and the sequence of cities traveled.HINT: to plot arcs on the sphere, use a loop with the quote() function to combine the function calls of arc3d into a list (every element in the list should be a unique expression), then use the purrr package’s map function ( map(list,eval)) to plot all the paths. IE 332 Homework #1 Page 9 of 10 5. Watch the video at https://www.youtube.com/watch?v=eqvBaj8UYz4 and answer the following questions: (a) (1 point) What does it mean for an algorithm to halt? (b) (1 point) Is the Halting Problem possible to solve? (c) (1 point) Is the entscheidungsproblem equivalent to asking “is there any question that a computer cannot solve”? (d) (4 points) Summarize the strategy Turing used to show the Entscheidungsproblem was false. 6. Watch the video at https://www.youtube.com/watch?v=PZRI1IfStY0 and answer the following questions. (a) (1 point) Floating point number are essentially what? (b) (1 point) What are two main benefits of using floating point numbers? (c) (1 point) What is decimal value 0.1 in binary? (d) (1 point) How many significant digits can a 32-bit computer store? (e) (1 point) Do computers understand the concept of mathematical recursion? (f) (1 point) When does a floating point rounding error occur? (g) (1 point) What is eventual consistency? 7. Watch the video at https://www.youtube.com/watch?v=ci1PJexnfNE and answer the following questions. (a) (1 point) What was one of the biggest challenges in programming during the 1970s? (b) (1 point) What was getting to be an important task? (c) (1 point) What was needed of a programming language? (d) (1 point) What was a great advantage of C compared to its contemporary programming languages? (e) (1 point) What was one of the design requirements of Java? (f) (1 point) What is probably the biggest liberation Prof Brailsford can think of in terms of his professional career? (g) (1 point) What problem may be eternal? IE 332 Homework #1 Page 10 of 10