这是一个加拿大的算法作业代写

Question 2: You are given a sequence S of n numbers. An element x in S is called a

majority element if it occurs more than n=2 times in S.

This question asks you to describe two algorithms that decide if the sequence S contains

a majority element; if it does, the algorithm returns it; otherwise, the algorithm returns the

message \there is no majority element”.

You are highly encouraged to use any algorithm and any result that was discussed in

class. In other words, try to make your algorithms as short as possible by using algorithms

discussed in class as \black boxes”.

(2.1) How many majority elements can there be? Justify your answer.

(2.2) Show how the majority problem can be solved in O(n log n) time. Argue why your

algorithm is correct and why the running time is O(n log n).

(2.3) Show how the majority problem can be solved in O(n) time. Argue why your algorithm

is correct and why the running time is O(n).

Question 3: Some textbooks contain statements of the form \The running time of algorithm

A is at least O(n2)”. Explain why such a statement does not make sense.

Question 4: You are given k lists, each one containing a sorted sequence of numbers. Let

n denote the total number of elements in all these lists. Give an O(n log k){time algorithm

that merges these k lists into one sorted list. Explain why the running time of your algorithm

is O(n log k).

Hint: Use a min-heap. If k = 2, this problem should look familiar to you.

Question 5: You are given a min-heap A[1 : : : n] on n elements and an integer k with

1 ≤ k ≤ n. Give an algorithm that computes the k smallest elements in A in sorted order.

The running time of your algorithm must be O(k log k). Explain why your algorithm is

correct and why its running time is O(k log k).

Hint: It is easy to get an O(k log n){time algorithm. In a min-heap, the root of any

subtree contains the minimum of all elements in that subtree. You may think of forming a

min-heap consisting of O(k) elements using the elements of the given heap A of n elements.

As always, you may use any algorithm that was discussed in class.

Question 6: Let G = (V; E) be an undirected graph, which is given to you in the adjacency

list format. Recall that degree(u) denotes the degree of vertex u. Let twodegree(u) be the

sum of the degrees of u’s neighbors, i.e.,

twodegree(u) = X

v:fu;vg2E

degree(v):

Describe an algorithm that computes twodegree(u) for all vertices u, in O(jV j + jEj) total

time. Justify your answer.

Question 7: Let G = (V; E) be a directed acyclic graph. In class, we have seen the following

algorithm for topologically sorting the vertices of G:

• Set k = 1.

• While the graph is non-empty:

{ Find a vertex v of indegree zero.

{ Assign the number k to v.

{ Remove v from the graph.

{ Increase k by one.

Show how this algorithm can be implemented such that its running time is O(jV j + jEj).

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

**E-mail:** itcsdx@outlook.com **微信:**itcsdx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。