I need help with 3 Algorithm Design problems

Hi, please help me solve the 3 questions in the attached document.


Thank you

Get Help With a similar task to - I need help with 3 Algorithm Design problems

Login to view and/or buy answers.. or post an answer
Additional Instructions:

EECS 3101 Winter 2018-19 – Test 4 Instructor: Jeff Edmonds 1) Array algorithm 9 + 13 = 22 2) Greedy algorithm 5× 13 = 65 3) Network Flows 13 4) Art therapy question 2 Total 102 Keep your answers short and clear. Do not repeat the question. 20% is given to any subquestion left blank (eg 3b). USE A PEN OR DARK PENCIL SO THE SCAN IS CLEAR DON’T WRITE OUTSIDE SPECIFIED AREAS. 1. Design an algorithm for crossing an array in the minimum number of steps. At each point in time you are standing on one of the elements. Each step you can move to any element with the same value, move forward one or move back one. For example, for {1, 2, 3, 4, 1, 5} move from the first 1 to the second 1 to the 5. (a) (9 marks) The obvious greedy algorithm moves each step the furthest to the right it can. Prove whether or not this works? (b) (13 marks) Give another algorithm for solving this problem. 2. The input is a set of cards I = {〈di, ci〉 |i ∈ [1..n]} and an integer C. Here di is a “digit” and ci is a cost. A solution 〈i1, i2, i3, . . . , im〉 is a subset of the cards in an order. The solution is valid if the sum of the costs ci of the cards in it sum to at most C, i.e. ∑ j∈[1..m] cij ≤ C. Consider the string formed by concatenating the digits of the solution together with zeros added on the end so that each solution has n characters, namely D = 〈di1di2di3 . . . dim00 . . .〉. The value of the solution which we are to maximize is the integer value and/or the lexicographical order of D. For example 122 is lexicographically before 21 but the integer 122 is bigger than 21. We added zeros to make it clearer. Solution 12200 is worse than 21000. For example, I = {〈2, 5〉 , 〈3, 4〉 , 〈3, 3〉 , . . . , 〈3, 3〉 , 〈8, 8〉 , 〈9, 9〉 , 〈9, 10〉} and C = 14. The following are the D and total cost C ′ for various valid solutions sorted from worst to best: D = 000000000 C ′ = 0 S = 〈〉 D = 233300000 C ′ = 5 + 3 + 3 + 3 = 14 S = 〈〈2, 5〉 , 〈3, 3〉 , 〈3, 3〉 , 〈3, 3〉〉 D = 333300000 C ′ = 3 + 3 + 3 + 3 = 12 S = 〈〈3, 3〉 , 〈3, 3〉 , 〈3, 3〉 , 〈3, 3〉〉 D = 390000000 C ′ = 3 + 9 = 12 S = 〈〈3, 3〉 , 〈9, 9〉〉 D = 833000000 C ′ = 8 + 3 + 3 = 14 S = 〈〈8, 8〉 , 〈3, 3〉 , 〈3, 3〉〉 D = 930000000 C ′ = 9 + 3 = 12 S = 〈〈9, 9〉 , 〈3, 3〉〉 D = 930000000 C ′ = 9 + 4 = 13 S = 〈〈9, 9〉 , 〈3, 4〉〉 D = 930000000 C ′ = 10 + 3 = 13 S = 〈〈9, 10〉 , 〈3, 3〉〉 D = 930000000 C ′ = 10 + 4 = 14 S = 〈〈9, 10〉 , 〈3, 4〉〉 (a) (13 marks) Give a non-adaptive greedy algorithm for this problem. Specifically what is the greedy criteria and the decision making process? (b) (13 marks) Define At. For your algorithm on the above input, give A0, A1, A3, A3, . . .. Explain where each of these comes from and why. (c) (13 marks) Define St. For your algorithm on the above input, give S0, S1, S3, S3, . . .. Maximize the changes. Explain where each of these comes from and why. 1 (d) (13 marks) Now consider a generic input. Discuss At−1, St−1, and At. Explain how St is obtained. (e) (13 marks) Prove that your St has the required properties. 3. (13 marks) Network Flow: Suppose you are given a network flow instance and optimal flow for it. Given an algorithm that determines whether or not this optimal solution is unique and if it is not finds a different one. Explain your algorithm both using the following instance as an example and for a general input. A formal proof is not needed. What algorithms learned in class do you use to find the required structures? Hint: Start by constructing the augmentation graph. s 5/5 7/7 2/10 t 5/11 Optimal Flow 2/6 u v w 4. (2 marks) Art therapy question: When half done the exam, draw a picture of how you are feeling. 2

Related Questions

Similar orders to I need help with 3 Algorithm Design problems
25
Views
0
Answers
The file included into this message shows the requirements.
Homework for computer science using JavaFX. The image included Into this shows the project. The requirements are listed in the picture of the tasks needed in the code....
12
Views
0
Answers
CPT202 SQL Programming 1 SQL Assignment 3
Microsoft SQL Server Management Studio 18 must be used for this assignment....
11
Views
0
Answers
CPT202 SQL Programming 1 SQL Assignment 3
Microsoft SQL Server Management Studio 18 is the program needed for this assignment....
9
Views
0
Answers
Java Coding Assignment - interact with SRPN Calc
Your task is to write a program which matches the functionality of SRPN as closely as possible. Note that this includes not adding or enhancing existing features....