Other代写：CSCI2110 Algorithm Complexity

发表于   |   分类于

代写算法作业，计算代码的时间复杂度。

Purpose

The purpose of this assignment is to practice your analysis of algorithm complexity. It is recommended that this assignment be printed, and that the work be done right on it. This assignment is to be submitted in paper form to the assignment boxes, just to the left of the elevators, on the second floor of the Goldberg CS Building. For each of the algorithms below:

  1. Derive the cost function for the algorithm. Be sure to show your work like we do in lectures.
  2. State the complexity of the algorithm in Big-Oh.
  3. Prove that the derived cost function is in the stated order (big-Oh).

Problem 0: Reverse

1
2
3
4
5
6
7
8
9
input: vals[n]
output: vals reversed

for i = 0 ... n/2
  t = vals[i]
  vals[i] = vals[n-i-1]
  vals[n-i-1] = t

return vals

Problem 1: Multiplication

1
2
3
4
5
6
7
8
9
10
11
input: A[n][n] and B[n][n] // 2D arrays of size n x n
output: C[n][n]

C = array[n][n] // Assume O(1) cost to create 2D array

for i = 0 ... n
  for j = 0 ... n
    C[i][j] = 0
    for k = 0 ... n
      C[i][j] = C[i][j] + A[i][k] x B[k][j]
return C

Problem 2: Edge Detection

1
2
3
4
5
6
7
8
9
10
11
12
input: A[n][n], F[3][3] // 2D arrays
output: E[n][n]

E = array[n][n] // Assume O(1) basic operation to create 2D array

for x = 1 ... n - 1
  for y = 1 ... n - 1
    E[x][y] = 0
    for k = -1 ... 2
      for l = -1 ... 2
        E[x][y] = E[x][y] + A[x+k][y+l] x F[k+1][l+1]
return E

Problem 3: Sorting

1
2
3
4
5
6
7
8
9
10
input: vals[n]
output: sorted vals[n]

for i = n - 1 ... 0
  for j = 0 ... i
    if vals[j] ] vals[j+1]
      v = vals[j]
      vals[j] = vals[j+1]
      vals[j+1] = v
return vals

Problem 4: Longest Common Subsequence

Based on code from https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
input: X[n], Y[n]
output: length of longest common sequence between X and Y

C = Array[n][n]
for i = 0 ... n
  C[i,0] = 0
  C[0,i] = 0

for i = 1 ... n
  for j = 1 ... n
    if X[i] == Y[j]
      C[i,j] = C[i-1,j-1] + 1
    else if C[i,j-1] < C[i-1,j]
      C[i,j] = C[i-1,j]
    else
      C[i,j] = C[i,j-1]
return C[n,n]

Problem 5: Sorting, again

1
2
3
4
5
6
7
8
9
10
11
input: vals[n]
output: sorted vals[n]

for i = 1 ... n
  for j = i ... 1
    if vals[i] >= vals[i-1]
      break
    v = vals[i]
    vals[i] = vals[i-1]
    vals[i-1] = v
return vals

Problem 6: Factorization

1
2
3
4
5
6
7
8
9
10
11
12
input: n-bit integer X // see not below the algorithm
output: list of prime factors and their multiplicity

acc = X
for i = 2 ... sqrt( X )
  count = 0
  while acc % i == 0
    acc = acc / i
    count = count + 1

  if count > 0
    print i (count)

Note: Recall that the range of values of an n-bit integer is 0 … 2^n.

Problem 7: Pivot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
input: vals[n]
output: vals divided by a pivot at val[0]

low = 1
high = n - 1

while low <= high
  if vals[0] <= vals[high]
    t = vals[high]
    vals[high] = vals[low]
    vals[low] = t
    low = low + 1
  else
    high = high - 1

t = vals[high]
vals[high] = vals[0]
vals[0] = t

Bonus Problem: Sorting, Once more with feeling!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
input: vals[n]
output: sorted vals[n]

sort( vals[n] )

function sort( V[n] ):
  if n > 2
    m=n/2
    sort( V[0:m] )
    sort( V[m,n] )

    A = array[n] // assume 1 operation to create array
    i=0
    j=m
    k=0
    while i < m and j < n
      if V[i] [<= V[j]
        A[k] = V[i]
        i=i+1
      else
        A[k] = V[j]
        j=j+1
      k=k+1

    if j < n
      i=j

    for l = k ... n
      A[l] = V[i]
      i=i+1

    for l = 0 ... n
      V[l] = A[l]
return V

Hints and Suggestions

  • Print this assignment and show your work right on it.
  • Feel free to use O(1) instead of specific constants when analyzing the algorithms.
  • Be sure to show your work!

Grading

Each problem will be graded out of 10 points:

  • 4 marks for deriving the correct cost function. The cost function should be of the correct order, and it should be clear how it was derived from the algorithm. One mark for the correct answer, three marks for showing your work.

  • 2 marks for identifying the correct order of the function (big Oh). One mark for the correct order, and one mark for correct notation. I.e., no multiplicative constants, or multiple terms.

  • 4 marks for justifying your answer. Follow the steps discussed in lecture. Approximately, 1 mark per step.

What to Hand In

Submit you assignment in hardcopy (paper form) to the submission box, which is located to the left of the elevators, on the second floor of the CS Goldberg Building.