# 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

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

Tutlance Experts offer help in a wide range of topics. Here are some of our top services:

- Math homework help
- Nursing homework help
- Statistics homework help
- Nursing coursework help
- Capstone project writing services
- Essay writers for hire
- Case study writing help
- Buy college papers online
- Buy college research papers
- College homework help
- Professional resume writing services
- Programming homework help
- Coursework writing help
- Term paper writing help
- Biology homework help
- Do my physics homework
- Dissertation data analysis help
- PhD Dissertation writing services
- Chemistry homework help

Post your project now for free and watch professional experts outbid each other in just a few minutes.