IE 332 – Homework #1
Due: Feb 16th 2022, 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 230. 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.
Copyright By PowCoder代写 加微信 powcoder
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: Feb 16, 2022
1. As you’ve already learned from the online lectures, for the code you write to be actually run by the computer, it needs to be translated to a form the computer can understand. This is typically done either via compilation or interpretation. In this problem, we’re going to be examining different ways the same problem can be expressed in syntax, and how these different expressions can lead to more or less efficient code which is generated by the compiler.
(a) (10 points) Go to godbolt.org and change the language in the dropdown menu to the C language. Write a basic program to print the first 10 natural numbers, each on their own line. Include the source code you wrote, and the Assembly code generated by the compiler, and the output of your program.
(b) (10 points) Change the language from C to Python, and write the code in yet another imperative way (using loops, for example). Provide your source code and the assembly generated from it. Is there a noticable difference between this output and the assembly generated from C?
(c) (10 points) Write this same method using either some declarative syntax or a list comprehension (if you don’t know what that means, look it up). Provide your source and the assembly code.
(d) (20 points) Compare the assembly generated using this method with the previous two methods. Do you notice any general trends regarding the density of code, as compared to its efficiency? (Note, this may not hold for all languages, but for these two, please report any trends you noticed.)
2. Proving the correctness of your code via careful introspection will save you a lot of headache in the long run. In this problem, we’re going to ask you to prove the correctness of a loop by finding a loop invariant. Then we’re going have you refactor the code in R to eliminate the loops which may make reasoning and proving the correctness of the code much easier!
(a) (30 points) Analyze the following code, find a loop invariant, and prove the code will perform correctly for any range of inputs. Please note any errors in the code, and assume R style array indexing.
Algorithm 1: Basic List Sorting (descending order) Input: array of size n>0
for i=0; i
temp=array[j] array[j]=array[i] array[i]=temp
(b) (20 points) Refactor the code in R (perhaps with the help of the purrr library) to a declarative style read from left to right. Recursion is suggested, and your code should be able to fit on 1 line with 1 control flow statement. Can you guarantee the code will work correctly without the need of a loop invariant? How?
3. Consider the algorithm below, which takes as input a n × (n + 1) matrix A:
(a) (30 points) What is this algorithm’s time efficiency?
(b) (30 points) The algorithm is not as efficient as it could be. State the source of the inefficiency and rewrite the algorithm so as to eliminate it. (Hint: Consider using loop invariants.)
Algorithm 2: Graph Operation
Input: A n × (n + 1) matrix A of real numbers
(for the steps below, notice that the count of rows and columns begins at 0) fori←0ton-2 do
for j ← (i+1) to n-1 do for k ← (i) to n do
Aj,k ← Aj,k − Ai,k ∗ Aj,i Ai,i
4. (30 points) Consider the problem of giving an amount n of dollars as change by using the minimum number of coins of any denomination d1 < d2 < · · · < dm (in the United States case, for instance, 1 cent, 5 cents, a penny, a quarter, 50 cents, 1 dollar). For the general case (not the specific one for the United States’s coin denominations), assuming an unlimited availability of coins for each of the m denominations d1 < d2 < · · · < dm where d1 = 1, write pseudocode for a greedy algorithm to solve the problem, for an amount n of change and coin denominations d1 > d2 > . . . > dm as its input. What is the time efficiency of the algorithm?
5. (40 points) Consider the problem of covering a 2n-by-2n squared board which is missing one square by using pieces formed by 3 squares arranged in an L shape:
Considering that the L pieces must cover the whole board apart from the missing square without overlapping each other, provide a divide-and-conquer algorithm to solve this problem.
IE 332 Homework #1 Page 2 of 5
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com