Homework answers / question archive / There is the specific timed assignment about Introduction to Analysis of Algorithms

There is the specific timed assignment about Introduction to Analysis of Algorithms

Computer Science

Share With

There is the specific timed assignment about Introduction to Analysis of Algorithms. Attached is the practice problems, which you can reference if you can handle this assignment. Then I will provide some materials to help you solve the specific timed assignment, which helps you to know what format you need to use. If you think you can read all materials I provides before doing the assignment and then provide quality work in specific time, please places you bids. If you do not have time to do the review, please don't waste our time. Thank you.
I will post the assignment on 3:00 PM, Wednesday, May 5, 2021 (EDT), and you got only 1.5hrs to finish FIVE questions which seems like the sample questions.Boston University CS 330 Spring 2021 Practice Problems for Final Exam Divide and Conquer 1. Suppose you are given a stack of n pancakes of different sizes. You want to sort the pancakes so that smaller pancakes are on top of larger pancakes. The only operation you can perform is a flip—insert a spatula under the top k pancakes, for some integer k between 1 and n, and flip them all over. Describe an algorithm to sort an arbitrary stack of n pancakes using O(n) flips. [Hint: This problem sounds a bit like the “Tower of Hanoi” probem that you may have encountered in other classes. But don’t be fooled! The solution looks very different.] 2. Suppose you are given a sorted array of n > 1 distinct numbers that has been “rotated” k steps, for some unknown integer k between 1 and n. That is, you are given an array A[1..n] such that some pref ixA[1..k] is sorted in increasing order, the corresponding suffix A[k +1..n] is sorted in increasing order, but A[n] < A[1]. As an example of an array of integers 1, . . . 10, a rotated array with k = 3 would be [8, 9, 10, 1, 2, 3, 4, 5, 6, 7]. (a) design a fast algorithm to find k by which the array is rotated. (b) design a fast algorithm to determine whether a number x is in the rotated array. 3. A subtree of a binary tree means any connected subgraph. A binary tree is complete if every internal node has two children, and every leaf has exactly the same depth. Describe and analyze a recursive algorithm to compute the largest complete subtree of a given binary tree. Your algorithm should return both the root and the depth of this subtree. Below you can see an example. 1 to find the k strings that are missing from A using only O(n log k) calls to F B . Trees . For this problem, a subtree of a binary tree means any connected subgraph. A binary tree is complete if every internal node has two children, and every leaf has exactly the same depth. Describe and analyze a recursive algorithm to compute the largest complete subtree of a given binary tree. Your algorithm should return both the root and the depth of this subtree. See Figure . for an example. Figure ?.?6. The largest complete subtree of this binary tree has depth ?. . Let T be a binary tree with n vertices. Deleting any vertex v splits T into at most three subtrees, containing the left child of v (if any), the right child of v (if any), and the parent of v (if any). We call v a central vertex if each of these smaller trees has at most n/2 vertices. See Figure . for an example. Describe and analyze an algorithm to find a central vertex in an arbitrary Dynamic Programming given binary tree. [Hint: First prove that every tree has a central vertex.] 1. You are participating in a dance contest. You know all the songs, all the judges, 34 14 and your own dancing ability extremely well. For each integer k, you know that if you dance to the kth song on the schedule, you will be awarded exactly Score[k] points, but then you will be physically unable to dance for the next W ait[k] songs (that is, you cannot dance to songs 12 night k + 1 through k + W ait[k]). The dancer with the highest total score at7 the end of the wins the contest, so you want your total score to be as high as possible. Describe and analyze an efficient algorithm to compute the maximum total score you can achieve. The input to your sweet algorithm is the pair of arrays Score[1..n] and W ait[1..n]. 2. In a previous life, you worked as a cashier in the lost Antarctican colony of Nadiria, spending the better part of your day giving change to your customers. Because paper is a very rare and Figure ?.??. Deleting a central vertex in a ??-node binary tree, with ??,bills ?, and ?? nodes. valuable resource in Antarctica, cashiers were required by leaving law to subtrees use the fewest possible whenever they gave change. Thanks to the numerological predilections of one of its founders, 6? 2 the currency of Nadiria, called Dream-Dollars, was available in the following denominations: $1, $4, $7, $13, $28, $52, $91, and $365 (a) The greedy change algorithm repeatedly takes the largest bill that does not exceed the target amount. For example, to make $122 using the greedy algorithm, we first take a $91 bill, then a $28 bill, and finally three $1 bills. Give an example where this greedy algorithm uses more Dream-Dollar bills than the minimum possible. [Hint: It may be easier to write a small program than to work this out by hand.] (b) Describe and analyze a recursive algorithm that computes, given an integer k, the minimum number of bills needed to make k Dream- Dollars. (Don’t worry about making your algorithm fast; just make sure it is correct.) (c) Describe a dynamic programming algorithm that computes, given an integer k, the minimum number of bills needed to make k Dream-Dollars. (This one needs to be fast.) 3. Suppose we are given a set L of n line segments in the plane, where each segment has one endpoint on the line y = 0 and one endpoint on the line y = 1, and all 2n endpoints are distinct. (a) Describe and analyze an algorithm to compute the largest subset of L in which no pair of segments intersects. (b) Describe and analyze an algorithm to compute the largest subset of L in which every pair of segments intersects. 4. You are organizing a holiday party for the employees at your company. The employees are organized into a strict hierarchy tree with the company president at the root. (a) The all-knowing oracles in Human Resources have assigned a real number to each employee measuring how “fun” the employee is. To keep things social, there is one restriction on the guest list: an employee cannot attend the party if their immediate supervisor is also present. On the other hand, the president of the company must attend the party, even though she has a negative fun rating; it’s her company, after all. Give an algorithm that makes a guest list for the party that maximizes the sum of the “fun” ratings of the guests. (b) Next year you are organizing the party again. This time the all-knowing oracles in Human Resources have assigned a real number to each employee indicating the awkwardness of inviting both that employee and their immediate supervisor; a negative value indicates that the employee and their supervisor actually like each other. Your goal is to choose a subset of exactly k employees to invite, so that the total awkwardness of the resulting party is as small as possible. For example, if the guest list does not include both an employee and their immediate supervisor, the total awkwardness is zero. The input to your algorithm is the tree T , the integer k, and the awkwardness of each node in T . 5. Give an algorithm that, given a weighted, directed graph G and two vertices s and t as input, counts the number of shortest paths between s and t. (Note: This is sometimes used as a measure of “well connected” s and t are in the graph.) The running time of the algorithms we can designn using the techniques we have seen depends on what you assume about the graph. Give algorithms that run in time 3 • O(mn) in graphs with positive and negative edge weights (assuming no negative-cost cycles) • O((m + n) log n) in graphs with nonnegative edge weights • O(m + n) if all the edge weights are 1 (that is, the graph is unweighted). Network Flow 1. We proved in class that at the end of the Ford-Fulkerson algorithm, the flow found by the algorithm has maximum possible value. Given that flow, how can we find a minimum-capacity cut in G in time O(m + n)? 2. Give a polynomial-time algorithm that, given a graph G with nonnegative integer edge capacities, determines if there is more than one minimum cut for G. 3. What is the tightest bound you can give on the running time of the Ford-Fulkerson algorithm when the input graph satisfies the following: all vertices have degree at most Dmax , and all edges have capacity at most Cmax (where Cmax is an integer)? Your bound should depend on n, Cmax and Dmax but nothing else. 4. Kleinberg-Tardos, Chapter 7, exercises 1–10 (page 415+). 5. Kleinberg-Tardos, Chapter 7, exercise 12 (page 420). 6. Kleinberg-Tardos, Chapter 7, exercise 15 (page 421). 7. Kleinberg-Tardos, Chapter 7, exercise 16 (page 422). 8. Kleinberg-Tardos, Chapter 7, exercise 19 (page 425). Polynomial Time Reductions, P, NP, and NP-completeness For each of the following statements, indicate whether it is true, false, or “unknown”, where “unknown” indicates that scientists have not conclusively determined whether the statement is true or false. For example, the correct answer for the statement “P = N P ” is “unknown”. But the correct answer for “the best algorithm for the maximum flow problem in n-vertex graphs takes time at least 2n ” is “false”. Give a short justification for your answer (i.e. explain why the statement is true, or false, or not known to be either true or false). 1. If X is in NP, then there does not exist a polynomial-time algorithm for X. 2. If X is NP-complete, then there is no polynomial-time algorithm for X. 3. If X is NP-complete, Y is in NP, and X reduces to Y, then Y is NP-complete. 4. Minimum-cut is NP-complete. 5. Minimum-cut is in NP. 4 6. Minimum-cut is in P. 7. Every problem in P is in N P . 8. Every N P -complete problem is in N P . 9. Some N P -complete problems have polynomial time algorithms, but some others do not. 5 Boston University, CS 330 Spring 2021 Final Exam 1, May 5, 2021 This exam consists of 5 problems. You have 120 minutes to complete it and submit on Gradescope. Problem 1 Asymptotic running time What is the asymptotic running time for computing fun( )? Give the lowest bound you can and justify your answer. You are free to refer results from class. fun(n): if(n