Recurrence, Sorting, Visibility, Probability, And Algorithms

Recurrence in Running Time

Finding the solution for n ≤ 3 takes only a constant amount of time. The divisionof the problem into 3 parts and the combination of S1, S2, S3 into the solution S each take O(n) time. In your answers, you may ignore the problem of rounding to integer. (For example, as in the pseudocode you can ignore the difference between n/3 and bn/3c or dn/3e.)

(i) Write a recurrence for the running time.

(ii) Demonstrate how to guess a solution of the recurrence by applying the recurrence repeatedly to itself.

(iii) Use induction to prove your guess is correct.

Question 2.

The following is a procedure that sorts an array A[0 · · · n−1]. procedure mysort(A, n)

for j from n−2 downto 0 do

x := A[j]

k := j + 1

while k < n and A[k] < x do

A[k−1] := A[k]

k := k + 1 endwhile

A[k−1] := x endfor end procedure

The meaning of the for statement is that j takes the values n − 2, n − 3, . . . , 1, 0 in that order.

(a) In 80 words or less describe how the procedure works. (A formal proof is not needed.)

(b) Using the Θ( ) notation, determine the worst-case running time of the procedure for sorting an array of length n.

(c) Now suppose we use the algorithm to sort arrays of distinct elements in random order, where each of the n! possible orders is equally likely. Find a lower bound for the average running time, using the ?( ) notation.

Question 3.

A row of n students are sitting directly behind each other, trying to see the screen at the front of the room. Each student can see the screen only if she is at least as tall as all the students in front of her. Let h[1], . . . , h[n] be the heights of the students, starting furthest from the screen. For example, if h[1] = 4, h[2] = 5, h[3] = 2, h[4] = 4, then students 2 and 4 can see the screen, but student 1 is blocked by student 2, and student 3 is blocked by student 4.

(a) Prove that when the following algorithm finishes, the stack contains exactly those students who can see the screen. Initialize a stack S for i from 1 to n do while S is not empty and h[i] > h[Top(s)] do Pop S endwhile Push i onto S endfor

(b) The algorithm has n “steps” corresponding to the values of i. What is the worst case time for one step? Use the Θ( ) notation and assume that Push and Pop take constant time.

(c) Give elementary reasoning why the total running time is O(n).

(d) Using the stack size as a potential function, write a careful proof of O(n) total running time using the potential method.

Question 4.

Let X be a random variable whose values are non-negative integers. Using the definition of expectation, prove that Prob(X ≥ 1) ≤ E(X).

Question 5. [0 or 10 marks] This question is compulsory for COMP8460 students. Other students can optionally answer the question and obtain up to 10 bonus marks.

One way to define a random graph is like this: Take some function p(n) which is always between 0 and 1. Take n vertices. For each pair v, w of distinct vertices, put an edge between v and w with probability p(n); otherwise no edge. Each of the decisions about whether to insert an edge are made independently of each other.

(a) What is the expected number of edges? Write both an exact answer and an approximate answer using the Θ( ) notation.

(b) What is the expected number of triangles? (A triangle is a cycle of length 3.) Write both an exact answer and an approximate answer using the Θ( ) notation.

(c) An isolated vertex is a vertex which has no edges incident to it. What is the exact expected number of isolated vertices?

(d) Given two distinct vertices v, w, a 2-path between v and w is a path of two edges v—u—w where u is a vertex different from v and w. Note that the 2-paths between v and w have no edges in common, so they are independent. Write an exact expression for the probability that a particular pair of vertices v and w have no 2-path between them. Infer an exact expression for the expectation of the number of pairs of distinct vertices with no 2-paths between them. (e) Let p(n) = n

−1/2 log n. Using your answer from part (d), and the inequality in

1 (a) Simplify the expressions

• ? (n ⁸(log n) ⁹ + 4e ⁿ (log n) ³ − 7(log n) ³ )

n ⁸ (log n) ⁹ + 4e ⁿ (log n) ³ − 7(log n) ³= n ⁸. log n ⁹ + 4e ⁿ .log n ³ – 7.log n. ³

let n⁸ =K, 4e ⁿ=m

7. log K ⁿ+ m.log n ³ – 7.log n ³

? (( n+k)(log K) + 3m (log n)– 10(log n))

?(log (K ^n+k +n^3m)/(n¹⁰) )

0(n) =1

0(log n) =log n

Taking n² as k

Then :

(log n^k +1 )/(log nk)

• Θ(g(n)) + o(g(n)), where g(n) is a function that is positive for large enough n

Definition:

Let f and g be two functions f, g : N → R ⁺ . We say that

 f(n) ∈ Θ(g(n))

 if there exist constants c₁, c₂ ∈ R ⁺ and n0 ∈ N such that for every integer n ≥ n0,

c₁g(n) ≤ f(n) ≤ c₂g(n)

Θ(g(n)) = O(g(n)) ∩ Ω(g(n))

Replacing Θ(g(n))

Then:

O(g(n)) ∩ Ω(g(n)) + O(g(n))

(b) Find expressions for the following summations (as a function of n) using the Θ( ) notation

The time complexity is Θ()

(c) Using the Θ( ) notation, what is the running time of this code fragment as a function of n?

i := 1

  sum := 0

      while i ≤ n do

         for j from 1 to i do

         prod := 1

 for k from 1 to i do

      prod := prod ∗ k

endfor

sum := sum + prod

 endfor

 i := i ∗ 3

 endwhile

Solution

At the while loop, the increment of i is not linear as it in goes from 1,3,9,…i*3.

Analysis of the increment of  i :

i = 1, i<=n, i=i*3

1^st execution  i=1=3⁰

2^nd execution i=3 = 3¹

3^rd execution i=9 = 3²

N^th  exection i=  3^n-1

The algorithm stops when  3^n-1   =n

Taking n-1=k

Then while loop stops when 3^k=n

Time taken

 K= log₃n

Note that when n is 1, the estimation runs one times. This shows the lower bound of the computation as Ω(n). The for-circles are dependent of the expansion of I, which implies every increase result to i3 number of times. In this way the time unconventionality of the estimation if 0(log3n) - the upper bound. Relating the lower bound and upper bound, we can for the most part reason that the two cases fuse the 3k=n. Giving it a tight bound of ?(log3n).

(d) (i) Write a recurrence for the running time.

COMP4600 Is a recursive function that calls itself referencing to the value of n. S₁, S₂, S₃ call the function are run equal times since the values of P₁, P₂, P₃ is the same. Values of S₁, S ₂, S₃ are gotten when n is less than 3. The function ends when n is less than 3.

Sorting Array A

Recurrence

funtion COMP4600(problem P of size n)

 if n ≤ 3 then

 return the solution --------- base case=T(o)

  else

  Divide P into 3 subproblems P₁, P₂, P₃ of size n/3

 S₁ := COMP4600(P₁) ----- 0(n)

  S₂ := COMP4600(P₂)------ 0(n)

 S₃ := COMP4600(P₃) ----- 0(n)

Combine S₁, S₂, S₃ into the solution S

 return S -----------------------T(n)

 endif

endfunction

recursive relation = n+n+n = 3n

T(n)= ?(3n).

 (ii) Demonstrate how to guess a solution of the recurrence by applying the recurrence repeatedly to it.

Since S₁, S ₂, S₃ take the same time, while n reduces by the factors of 3. Then estimation of the solution would base on the factors of 3 in n while assuming the decimals in the result. Given the factors of 3 in n to be k, then:

 Recursive relation = kn + kn + kn = 3kn

T(n)= ?(3kn).

(iii) Use induction to prove your guess is correct.

Induction: assume for some arbitrary value of n than T(n)= ?(3kn), decimals are assumed (Bubeck, 2015, Pg. 234).

T(n)=0---base case

Let n=1, 2

K= 1/3, 2/3,

K of 2, 3 =0.33, 0.66 assuming the decimals, k=o,o

Induction case

T(1)= ?(3*0*1)

T(1)=0

T(2)= ?(3*0*2)

T(2)=0

Conclusion:

Thus we conclude that T(n)= ?(3kn).

2(a) The procedure is a sorting function – Mysort, that takes two arguments A and n. In this algorithm, a nested loop is used. The different invariant holds – in the j-th times of the outer loop, there is a relative ordering of in the items of A[0] through A[j-1]. In order to insert an item in a relative position of the sort, there is a necessity of moving values to the right to make room. The first two items are put in the correct relative order, and then the third item correct to the first two in that order until the whole array of data is sorted.

(b)

(n-1)+(n-2)+….+1=

The time complexity is Θ(n² )---Worst case scenario.

(c) Basing on distinct elements of a random order that would give equally likely n! possible orders under this sort, then the lower bound would not be any different from the time complexity (Deb, 2014, Pg. 415). Hence ?(n² ).

3. (a) Prove that when the following algorithm finishes, the stack contains exactly those students who can see the screen. Initialize a stack S

for i from 1 to n do

  while S is not empty and h[i] > h[Top(s)] do

  Pop S

Endwhile

 Push i onto S

 Endfor

First, the algorithm runs

The for-loop runs n times, and for each i-th time, the while –loop runs to pop S if S is not empty and the height of the student in the h[i] position is greater than that of h[Top(s)], or the position I is pushed onto S. By the time the algorithm runs n times, only those heights that meet the while condition shall be popped. Hence, when the algorithm finishes, the stack will contain students who can see the screen only.

Visibility Algorithm

b)

for i from 1 to n do -------------n

  while S is not empty and h[i] > h[Top(s)] do----------1

  Pop S

Endwhile

 Push i onto S

 Endfor

T(n)=n+1

Time complexity = ?(n)

(c)  Given that the while loop runs one in every i-th time the for-loop runs, it is evident that the algorithm depends on the nth times to finish. Hence, the time complexity of 0(n) as provided by Pal & Wang (2017).

(d) Prove that time complexity

Definition:

f(n)= 0(g(n))

if f(n) ≤ C.g(n) for all n≥ k ….where C and k are positive

(f(n))/(g(n)) ≤ C for all  n≥ k

Taking C=4 then:………number of students in the raw

n+1 ≤ 4* g(n) for all n ≥ 1

n+1 ≤ 4* n……………….n=1

2 ≤ 4

Then f(n) = 0(g(n))

Conclusion: we have proved that time complexity of the algorithm is indeed 0(n)

4.  Proof that Prob(X ≥ 1) ≤ E(X).

Using Markov’s inequality (Schacht, 2016, pg)

P(X ≥ a)  ≤ E(X)/a

Indicator function 1 _{X ≥ a}

Multiplying the indicator function by a constant a:

a(1 _{X ≥ a})

If x<a then:

a(1 _{X ≥ a}) =0<x

if X ≥ a then:

a (1 _{X ≥ a}) =a≤ x

a (1 _{X ≥ a})/a= P(X ≥ a)  = a/a ≤ x/a ----an equivalent to the  probability equation

hence: P(X ≥ a) ≤ E(x/a)

replacing a with 1

P(X ≥ 1) ≤ E(x/1) == P(X ≥ 1) ≤ E(x)

Conclusion: We have proven that Prob (X ≥ 1) ≤ E(x)

5. (a)Let Ikbe the indicator function for the edge k, i.e.,

Quantity of interest:

 --------By linearity of expectation (Le, Levina, & Vershynin, 2017, Pg. 545)

Assuming that the likelihood of an edge to be present or absent is equal, then:

The approximate tight bound would be Θ()

(b) An arbitrary diagram with n vertices and edge likelihood d/n, has a normal number of triangles that is autonomous of n, to be specific d³/6.

(c) For each vertex v, there is a random variable Xv that is 1 if v has degree 0 and 0 otherwise as explained by Dellamonica et al., (2015, Pg. 288).

Then, E(Xv)=P(Xv=1)E(Xv)=P(Xv=1), where the probability is the fraction of random selections of k edges that leave v isolated, over all possible selections of k edges

Then, by linearity of expectation, the number of isolated vertices is nE(Xv).

(d) To begin, n vectors (of n vertices) v₁,...,v_n are picked i.i.d. as per some likelihood appropriation on R k . In the wake of taking this decision, particular vertices I and j are made nearby with likelihood v_i · v_j . All sets are viewed as free. Care ought to be taken to guarantee the conveyance on R k fulfills P( v_i · v_j ∈/ [0,1])  = 0.

(e) if p(n) = n ^−1/2 log n

With:

Prob(X ≥ 1) ≤ E(X) and P( v_i · v_j ∈/ [0,1])  = 0

Then:   p(n)= (log n)/n²

Assuming that n ≥ 1:

Then the equation fits in to Markov’s inequality. So Prob(n ≥ 1) ≤ E(n)

Reference List

Bubeck, S., 2015. Convex optimization: Algorithms and complexity. Foundations and Trends® in Machine Learning, 8(3-4), 231-357.

Deb, K., 2014. Multi-objective optimization. In Search methodologies (pp. 403-449). Springer, Boston, MA.

Dellamonica Jr, D., Kohayakawa, Y., Rödl, V., and Ruci?ski, A., 2015. An improved upper bound on the density of universal random graphs. Random Structures & Algorithms, 46(2), 274-299.

Le, C. M., Levina, E., and Vershynin, R., 2017. Concentration and regularization of random graphs. Random Structures & Algorithms, 51(3), 538-561.

Pal, S. K., and Wang, P. P., 2017. Genetic algorithms for pattern recognition. CRC press.

Coja?Oghlan, A. and Efthymiou, C., 2015. On independent sets in random graphs. Random Structures & Algorithms, 47(3), pp.436-486.