Get Instant Help From 5000+ Experts For

Writing Get your essay and assignment written from scratch by PhD expert

Rewriting: Paraphrase or rewrite your friend's essay with similar meaning at reduced cost

# Recurrence, Sorting, Visibility, Probability, And Algorithms

8 Pages / 1,762 Words Published On: 08-02-2021

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

Cite This Work

"Recurrence, Sorting, Visibility, Probability, And Algorithms." My Assignment Help, 2021, https://myassignmenthelp.com/free-samples/comp4600-advanced-algorithms/genetic-algorithms-for-pattern-recognition.html.

My Assignment Help (2021) Recurrence, Sorting, Visibility, Probability, And Algorithms [Online]. Available from: https://myassignmenthelp.com/free-samples/comp4600-advanced-algorithms/genetic-algorithms-for-pattern-recognition.html
[Accessed 02 October 2023].

My Assignment Help. 'Recurrence, Sorting, Visibility, Probability, And Algorithms' (My Assignment Help, 2021) <https://myassignmenthelp.com/free-samples/comp4600-advanced-algorithms/genetic-algorithms-for-pattern-recognition.html> accessed 02 October 2023.

My Assignment Help. Recurrence, Sorting, Visibility, Probability, And Algorithms [Internet]. My Assignment Help. 2021 [cited 02 October 2023]. Available from: https://myassignmenthelp.com/free-samples/comp4600-advanced-algorithms/genetic-algorithms-for-pattern-recognition.html.

Stuck on Any Question

Writing: Get your essay and assignment written from scratch by PhD expert

Rewriting: Paraphrase or rewrite your friend's essay with similar meaning at reduced cost

250 words
5% Cashback

On APP - grab it while it lasts!