algorithms hw2

Homework 2
The deadline for handing in this homework is on the deadline

specified on Canvas by 23:59. Homework must be neatly typeset
or handwritten, and submitted individually as a PDF. Please turn in
any source code if the assignment has programming components
(i.e., the *.py files). This assignment is graded out of 100 points, the
last question is a bonus problem worth 5 additional points. Starting
in the Fall 2024 semester, all assignments are required to
be submitted as group work. You must work in groups of
size 2-4 unless you have worked out other arrangements
with me. Only one student for each group needs to submit
the assignment, just make sure all names are on the
assignment at the top.
Problem 1 (50 points)

A client comes to you with a list of integers and wants to be able to
provide a target integer and determine if any two of the numbers in
the list sums to the target.
ˆ Example: ⟨1, 3, 5, 2⟩ and target 7 should return TRUE since 5 + 2 = 7.
ˆ Example: ⟨1, 3, 5, 2, 8⟩ and target 12 should return FALSE
because, while 8 + 3 + 1 = 12, there are no two numbers that
sum to 12.
Problem 1.a (10 points)

Provide a formal problem statement in terms of input and output.
Input:list of integers, target integer
Output:true target integer and list elements that sum to it/false,target integers
Problem 1.b (10 points)

Provide pseudocode that solves the problem (include line numbers).
Function add(list[], target int)
For(i=1 < list.length)
Y = target – list[i]
For(j=i+1 < list.length-1)
…if list[j] == Y
……Return true, print(list[i] + Y = target int)
Else
…return false
Problem 1.c (10 points)

Please prove the time complexity of your algorithm using your
1
provided pseudocode (please reference line numbers).
Problem 1.d (10 points)

Please provide a loop invariant for your algorithm.
2
Problem 1.e (10 points)
Please prove that your algorithm solves the problem (i.e., prove the
correctness) using your loop invariant and pseudocode.

Let f (n) = n3 + n2 log(n) + log(n) and g(n) = n4. Show that f (n) =
O(g(n) providing sufficient values for c and n0.

Let f (n) = n4 and g(n) = 6n4 + 5n3 − 2n + 7. Show that f (n) =
Ω(g(n) providing sufficient values for c and n0.
N^4 = 6n4 + 5n3 − 2n + 7.
>=1/6(6n4 + 5n3 − 2n + 7)

Let f (n) = n4 log(n) + n2 + n + 8 and g(n) = n4 log(n). Show that f
(n) = Θ(g(n)) providing appropriate values for c1, c2, and n0.
C1g(n) <= n4 log(n) + n2 + n + 8 <= c2g(n)
n4 log(n) + n2 + n + 8 <= n4 log(n)

Please provide the runtime for the following algorithm citing specific
line numbers to justify your solution.
Algorithm 1 MinList
Input: a two-dimensional array of integers M with n rows and m columns
Output: a list M ′ containing the minimum integer in each row
1: M ′ = []
2: for i = 1 to n do
3: min ← ∞
4: for j = 1 to m do
5: print(”Checking element j of row: ”)
6: for k = 1 to m do
7: print(M [i][k])
8: end for
9: print(“\n”)
10: if M [i][j] < min then
11: min ← M [i][j]
12: end if
13: end for
14: M′.append(min)
15: end for
16: return M′
3
2,4,6-time complexity = O(M^2) because line 6 takes O(m) for each iteration but is nested
in the j for loop which also takes O(M) time therefore the innermost loop runs in O(m^2).
The outermost loop runs only n times. The print statement inside the innermost loop runs in
O(1) but it runs O(m^2) times. Every other line either runs in O(n),O(m), or O(1) therefore
the time complexity for the entire algorithm is O(m^2)
Bonus Problem (5 points)

Write one paragraph explaining why you believe this course is
important for computer science majors to take. If you do not think
it is important or are unsure why please feel free to discuss that
instead.
I believe this course is important for computer science majors
because it is very important to be able to break down problems to
their base so that we can explain how/why our code actually works
in basic language so other people can understand what we are
doing. It is also important for us to be able to understand different
algorithms and why they actually work. All this is also good for
problem solving because it can give you a starting point with truth
tables,pseudocode, and big O so that you can solve problems more
efficiently and to a better quality

algorithms hw2

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

algorithms hw2

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

algorithms hw2

Uploaded by

Copyright:

Available Formats

Homework 2

The deadline for handing in this homework is on the deadline

Problem 1 (50 points)

Problem 1.a (10 points)

Problem 1.b (10 points)

Problem 1.c (10 points)

Problem 1.d (10 points)

Problem 2 (10 points)

Problem 3 (10 points)

Problem 4 (10 points)

Problem 5 (20 points)

Bonus Problem (5 points)

You might also like