IE 332 – Homework #1

Read Carefully. Important!

As outlined in the course syllabus this homework is worth 7% of your final grade. The maximum attainable mark on this homework is 115. 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 Blackboard 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.

When submitting your assignment it is assumed that every student considers the below checklist, as there are grading consequences otherwise (e.g., not submitting a cover sheet is an automatic grade of ZERO).

Q Attach a cover sheet (see Blackboard) as the first page of your submission. Q Submit page i of this assignment as the second page of your submission. Q Your solutions have style (see Q1 in the assignment).

Q All of your solutions (program code, etc.) are included in the submission.

Q All of your source code is cut-and-pasted into the assignment, not included as a separate file, picture or screen shot.

Q You have not included any screen shots, photos, etc. (plots from R are permitted/expected but should be intermediately saved as .png files).

Q All math notation and expressions are created using an equation editor (no pictures, handwritten solutions, etc.).

Q If using Word or other text processor, convert the output to .pdf and ensure that it does not contain any aesthetic or other errors. Submit only the pdf version.

Q If using LATEX, the source code is separately submitted in a .zip file. If using LATEX correctly, there is a 7 point bonus.

Q Watch videos on creating pseudocode if you need a refresher or quick reference to the idea. These are good starter videos:

www.youtube.com/watch?v=4jLO0vXPktU www.youtube.com/watch?v=yGvfltxHKUU

Page i of i

IE 332 Homework #1 Due: Sept 19 2018

  1. (0 points) These are style points meant to enforce the skill of communicating technical information in a precise, concise and easily interpretable way. You are penalized for (a) using poor grammar/spelling, (b) disorganized presentation of solutions (including organizing your code into functions, as appropriate),

    (c) not commenting well your source code, (d) not using meaningful variable names in your code. At the discretion of the TA (who should be grading this “hard”). The presumption is that you do not do any of these things, and so doing them will cost addition points (up to -10). Your goal is to get 0/0 on this question.

    The assignment should have margins between 0.5 and 0.75 inches wide, with font size no larger than 12pt (11pt for code) and no smaller than 10pt – sub/superscripts, figure and plot captions excluded, but should be clearly legible. Clearly label each question.

    If a question requires more than 40% of the page to answer, then that is the only answer on that page. If multiple pages are required, this rule applies to the last of those pages.

  2. 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, . . . ,$r10, and system RAM as needed.




    add reg1, reg2, reg3

    sub reg1, reg2, reg3 div reg1, reg2, reg3 mul reg1, reg2, reg3 muli reg1, reg2, x addi reg1, reg2, x subi reg1, reg2, x divr reg1, reg2, x mov reg1, reg2 label:

    name: .type, value lw reg, RAM source sw reg, RAM source la reg, RAM source sa reg, RAM source b label

    beq reg1,reg2,label blt reg1,reg2,label bgt reg1,reg2,label bqe reg1,reg2,label ble reg1,reg2,label bne reg1,reg2,label print reg

    prints reg read reg done

    reg1 = reg2 + reg3

    reg1 = reg2 reg3 reg1 = reg2/reg3 reg1 = reg2 reg3

    reg1 = reg2 x, where x is some integer reg1 = reg2 + x, where x is some integer reg1 = reg2 x, where x is some integer

    reg1 = reg2/x, where x is real, truncates result

    reg1 = reg2

    create a reference label in the code

    create .type variable in RAM where name = value

    move word from RAM to a register move word from register to RAM move address of RAM to a register move address in register to RAM jump to a label in the program jump to label if reg1 = reg2

    jump to label if reg1 < reg2

    jump to label if reg1 > reg2 jump to label if reg1 reg2 jump to label if reg1 reg2 jump to label if reg1 ƒ= reg2 print contents of register to screen

    print string pointed to in register to screen

    get keyboard input (after ENTER pressed); store in reg end of program

    add $r0, $r1, $r2

    sub $r0, $r1, $r2 div $r0, $r1, $r2 mul $r0, $r1, $r2 mul $r0, $r1, 4 addi $r0, $r1, 5 addi $r0, $r1, 5 divr $r0, $r1, 2 mov $r0, $r1 main:

    var1: .word 5 lw $r4 var1 sw $r4,var1 la $r4 var1 sa $r4,var1

    b main

    beq $r0,$r1,main blt $r0,$r1,main bgt $r0,$r1,main bqe $r0,$r1,main ble $r0,$r1,main bne $r0,$r1,main print $r0

    prints $r0 read $r0

    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 = Fn1 + Fn2 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, strin1 prints $r7 print $r0 done

    Create an assembly program using the above language for the following algorithm, that should perform a mathematical operation using all elements of arrays A and B. You can assume that function basicFunc works correctly. Make your solution as concise (fewest number of lines) as possible. When submitting your results show a table with two columns: (1) the original program, (2) your assembly code.

    1. (15 points) Create an assembly program using the above language for the following algorithm. In this algorithm, it searches 2 arrays and do basic mathematical operations. It is expected to return a number that is equal to ’SUM’.

      1: A = {1, 10, 13, 15, 21, 55, 67}

      2: B = {1, 2, 3, 4, 5, 6, 7}

      3: i = 0, L = length(A)-1, SUM = 0

      4: while i < L do

      5: SUM = SUM + basicFunc(A[i],B[i])

      6: i = i+1

      7: end while

      8: return SUM

      9: function basicFunc(x, y)

      10: z = 0

      11: if x == SUM then

      12: z = y

      13: else

      14: z = x*y

      15: end if

      16: return z

    2. (3 points) What is the loop invariant for your algorithm? (just state the invariant)
    3. (8 points) Prove whether the algorithm is correct or not using a loop invariant.
  3. Provide a tight bound on the the worst case runtime for the following algorithms. The grading criteria is as follows (note, “answer” refers to the tight bound equation):



    Provide correct answer as well as explanation


    Provide correct answer but incomplete correct explanation


    Provide wrong answer but mostly correct explanation


    Provide correct answer but mostly wrong explanation


    Provide wrong answer and mostly wrong explanation


    No answer, or only answer without sufficient explanation


    1. (5 points) Require: n > 1 1: x=0, y=1

      2: while y < n do

      3: x = x + 50

      4: y = 3y 5: end while 6: print x, y

    2. (10 points)

      Require: Array A containing n > 1 elements

      1: for (i=1; i<n; i=i+1) do

      2: A[i] = (1)i2i

      3: end for

      4: k = max(max(A),n)

      5: x = 1, y = 0

      6: while x < n do

      7: y = y + 1

      8: if y = x then

      9: x = x + 1

      10: y = 0

      11: end if

      12: end while

      13: print x,y

    3. (8 points)

      Require: n > 0

      1: for (i=1 ; i < n ; i=2i) do

      2: for (j=i ; j<2i ; j=j+1) do

      3: print i,j

      4: end for

      5: end for

  4. You are taking an IE332 exam worth a maximum of 55 points, but you are not expected to answer all the questions within the 50 minute time limit. Instead, you are supposed to select a subset of questions that your grade is based on. You decide to devise a greedy algorithm using points per minute to find questions that maximize your overall score (assume that you get those you answer 100% correct and once you start answering a question you must completely answer it). NOTE: Question 8 and 9 are bonus questions and you can only answer one of them to get the 5 bonus points. If you answer both, you will not get any points. You estimate the time you need to finish each question is as follows:


    Total Points

    Time needed (in mins)




























    1. (2 points) What is the value (in points) you will get per minute for answering each question? Sort the table above by this value in decreasing order.
    2. (3 points) Using the greedy framework, which questions will you choose to solve within the time limit in order to maximize your score? What is that score, and how many total minutes would you spend writing the test?
    3. (6 points) Code your greedy algorithm in R. (HINT: you may need rank() or order() functions).

      DO NOT hard code the table from part (a), you will get a grade of zero if so.

    4. (3 points) Do you think this greedy algorithm will always yield the highest possible score on the test? Justify your answer with a proof or counter example.
  5. Suppose that you are given an unsorted list containing n characters, and that the distance between characters c1 and c2 is measured as |n(c1)n(c2)| where |·| is the absolute value function and n(·) returns the index of the character in the alphabet (i.e., so that n(a) = 1). For examples, the distance between ‘a’ and ‘c’, would be |n(a) n(c)| = |1 3| = 2, and between ‘a’ and itself would be |n(a) n(a)| = 0.
    1. (15 points) Construct a Θ(n log n) divide-and-conquer algorithm that can find a pair of characters whose distance in the alphabet is smallest compared to all others in the list. For example, if your list has letters < c, t, f, a, m, i >, the result will be ‘c’ and ‘a’. Your solution should be in pseudocode!
    2. (10 points) Code your above algorithm in R.
  6. Consider the following algorithm, where P is an array containing random numbers. The function swap(v1,v2) will swap the values stored in the variables v1 and v2. Note that % is the modulus operation, and will return the integer remainder r of a/b, i.e., r= a%b.

    Require: Array P with n > 0 values

    1: i=1, j=n-1

    2: while i<=j do

    3: x=j, y=i

    4: for a=i to j by 1 do

    5: if P [a]>P [a+1] and P [a]%2==0 then

    6: swap(P [a], P [a+1])

    7: y=a

    8: end if

    9: end for

    10: j=y-1

    11: for a=j-1 to i by 1 do

    12: if P [a]>P [a-1] and P [a]%2!=0 then

    13: swap(P [a], P [a+1])

    14: x=a

    15: end if

    16: end for

    17: i=x+1

    18: end while

    1. (1 point) What are the input(s) to the algorithm?
    2. (2 points) In one short sentence explain what the purpose of the algorithm is. Be as specific as possible by referring to program variables.
    3. (10 points) Provide a proof of correctness using a loop invariant. Be sure to clearly state the invariant. HINT: after each iteration of the outer loop, largest even element of the array is always placed at rightmost position.
    4. (3 points) What is a best-case runtime scenario for this algorithm? Explain.
    5. (3 points) What is a worst-case runtime scenario for this algorithm? Explain.
  7. (8 points) Watch this video www.youtube.com/watch?v=OY41QYPI8cw and answer the questions be- low.
    1. What does the P vs NP problem boil down to?
    2. What defines the set of problems in P?
    3. What defines the set of problems in NP?
    4. What is the Cook-Levin Theorem?
    5. What do we mean by “hardest problem”? (f) What is EXPTIME?
  1. What is an example undecidable problem?
  2. If a problem is NP-complete, does it mean that it is impossible to solve optimally?