# 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

- (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.

- 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.

instruction

meaning

example

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 = 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, 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.

- (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

- (3 points) What is the loop invariant for your algorithm? (just state the invariant)
- (8 points) Prove whether the algorithm is correct or not using a loop invariant.

- (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’.
- 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):

Criteria

Score

Provide correct answer as well as explanation

100%

Provide correct answer but incomplete correct explanation

75%

Provide wrong answer but mostly correct explanation

50%

Provide correct answer but mostly wrong explanation

25%

Provide wrong answer and mostly wrong explanation

0%

No answer, or only answer without sufficient explanation

0%

- (5 points)
**Require:**n > 1 1: x=0, y=12:

**while**y < n**do**3: x = x + 50

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

- (10 points)
**Require:**Array A containing n > 1 elements1:

**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

- (8 points)
**Require:**n > 01:

**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

- (5 points)
- 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:

Question

Total Points

Time needed (in mins)

Q1

21

24

Q2

5

7

Q3

10

15

Q4

14

12

Q5

5

4

Q6

5

3

Q7

10

10

Q8

5

5

Q9

5

6

- (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.
- (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?
- (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.

- (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.

- 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.
- (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**! - (10 points) Code your above algorithm in R.

- (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
- 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 values1: 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 point) What are the input(s) to the algorithm?
- (2 points) In
__one short sentence__explain what the purpose of the algorithm is. Be as specific as possible by referring to program variables. - (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. - (3 points) What is a best-case runtime scenario for this algorithm? Explain.
- (3 points) What is a worst-case runtime scenario for this algorithm? Explain.

- (8 points) Watch this video www.youtube.com/watch?v=OY41QYPI8cw and answer the questions be- low.
- What does the P vs NP problem boil down to?
- What defines the set of problems in P?
- What defines the set of problems in NP?
- What is the Cook-Levin Theorem?
- What do we mean by “hardest problem”? (f) What is EXPTIME?

- What is an example undecidable problem?
- If a problem is NP-complete, does it mean that it is impossible to solve optimally?