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
8
Views
0
Answers
Inter-Process Communication (IPC) with Pipes in C
This is a C programming assignment to implement the parallel processing of input files using the fork(), waitpid(), and pipe() system calls. You will also use stat() and write() in each child process, and you will use read() in the parent process. Overa...
16
Views
0
Answers
The third programming project involves writing a program that allows the user to enter a binary tree.
Use original java code as well as original work for test plans and documentation. The third programming project involves writing a program that allows the user to enter a binary tree in a parenthesized prefix format and then allows it to be categorized a...
25
Views
0
Answers
Jupyter notebook tasks. Create a Python file dmv_record.py that contains the definition of a class named DmvCarRecord.
Create a Python file dmv_record.py that contains the definition of a class named DmvCarRecord. The class should include an __init__ method that initializes the following fields using optional parameters: license_num maker model year owner_id reg_ex...
24
Views
0
Answers
software design & development using flask
The objective of this exercise is to create a database-driven Flask application to keep track of guest attendance to an event. The application should enable users to perform the following 3 actions, which should be implemented as links in a navbar: 1. V...