Introduction to Analysis of Algorithms
代写homework | 代做Algorithm | oop代做 – 这是一个关于oop的题目, 主要考察了关于oop的内容,是一个比较经典的题目, 涵盖了Algorithm/oop等方面, 这是值得参考的homework代写的题目
Boston University CS 330
Professor Steve Homer, Dora Erdos Spring 2021
homework 2
Guidelines to presenting an algorithm.
Describing an algorithm: When we ask you to find an Algorithm we always ask you to
- give a clear and concise description of your algorithm. This usually would entail a pseudocode and some English text. A good rule of thumb is that your description is sufficient if a classmate is able to take your description and turn it in to working code. Its ok to add comments (the type you would add to your code) in the pseudocode.
- Prove that it is correct. I.e., show that the output of the algorithm is indeed what the problem is asking for.
(a) A first sanity check would be for you to trace your algorithm by hand on some small
graph (do not hand in!) and see that it indeed produces the result you want.
- Compute its asymptotic running time. For this you need to give some short explanation, e.g. we iterate over each edge once, hence this specific part takesO(m), or this for l oop takes O(n) iterations.
Reusing known facts, algorithms, etc: Often you find an algorithm that is either very similar to something that we discussed in class or it explicitly calls a known algorithm as a subroutine. In that case you dont need to explain the details again. Say, you design an algorithm that first sorts an array of n elements, then calls BFS as a subroutine and then does something else. Then this would be acceptable:
ExampleAlgo( array A, graph G):
sorted_A = A.sort( )
[dist, tree] = BFS(G)
Now do lots of other stuff
return
For your analysis you would write that we know that using an appropriate sorting algorithm (e.g. mergesort) the running time isO(nlogn). We also know that BFS on an input of n nodes and m edges runs in time (n+m). The lots of other stuff part takes timeO(xxx). In your proof you can also state that we know that BFS indeed outputs the correct distance for each node.
Problem 1.10 pts.
- Consider the followingSwapAlg( ) algorithm.
Algorithm 1:SwapAlg(A)
Input:Ais an array containing the firstnpositive integers. It is indexed 1 ton.
1 n=length(A) ;
2 swaps= 0;
3 fori= 1tondo
4 forj= 1tonido
5 ifA[j]> A[j+ 1]then
6 A[j] =A[j] +A[j+ 1];
7 A[j+ 1] =A[j]A[j+ 1];
8 A[j] =A[j]A[j+ 1];
9 swaps+ +;
Output:swaps
(a) Give the best asymptotic upper bound you can on the running time ofSwapAlg( ) as a
function ofnusing big-Oh notation. Explain your computation.
(b) Explain in one or two sentences what value the variableswapsis tracking. What is the
number that this algorithm returns?
- Consider thedecAlg( ) algorithm.
Algorithm 2:decAlg(A)
Input:Ais an array of integers. It is indexed 1 ton.
1 n=length(A) ;
2 dec= 0;
3 fori= 2ton+ 1do
4 j=i1;
5 whilej > 1 ANDA[j1]> A[j]do
6 temp=A[j1];
7 A[j1] =A[j];
8 A[j] =temp;
9 j;
10 dec+ +;
Output:dec
(a) Give the best asymptotic upper bound you can on the running time ofdecAlg( ) as a
function ofnusing big-Oh notation. Explain your computation.
(b) Observe, that both inSwapAlg( ) and indecAlg( ) pairs of values inAare swapped.
Both variables swapanddec keep track of the number of swaps performed in their
respective algorithms. State and give an exact proof of what the relationship between
the two variables are when the algorithms are run on the same inputA. (The answer
we are looking for is thatswapis always smaller/equal/larger thandecor that it varies
depending on the input array.)(Hint: One way of proving it is to show that for any
two values initially at indexA[x]andA[y] if they are swapped at any given time in
swapAlg( )then they eventually will be swapped indecAlg( )and vice verse.)
Problem 2.10 pts.
LetG(V, E, s, c) be an undirected graph withsas a source node. Each of its edgeseEis either blue or red, andcedenotes the color of edgee. Let all edges adjacent tosbe blue.
A path between nodesuandvin graphG, calledPuv, is ashortestpath if there is no other path betweenuandvwith fewer edges. A simple pathPinGis calledalternatingif the edge colors in the path alternate between red and blue. Analternating shortest pathis a path that is both shortest and alternates.
Find an algorithmAlternate( )that decides whether there is an alternating shortest path fromsto every other node.
Theinputto your algorithm isG(V, E, s, c) and a length-narraydist. The array entrydist[i] contains the distance (length of the shortest path) fromsto nodeiin the non-edge-colored sense. The algorithm needs to find whether there is an alternating shortest path betweensand every other nodevinV. Theoutputof your algorithm is yes if there exists an alternating shortest path fromsto everyv. (Note that it is possible that there are both alternating and non-alternating path of the same length.) The output is no if there is at least one nodevthat doesnt have an alternating shortest path tos.
Use the Guidelines to presenting an algorithm to do this problem. Make sure you follow all the parts of the guidelines.