Assignment 2 Greedy Algorithms

CS 310 ‘Algorithms’
[Total Marks = 105]

Read the instructions at the end of this document and follow the naming conventions. Marks for writing well-structured and efficient code.
Consider the following problem discussed in class. You are given two boxes, one of the boxes has ‘n’ red-colored sticks of lengths Lr1, Lr2, Lr3 … Lrn and the other box has ‘n’ blue-colored sticks of lengths Lb1, Lb2, Lb3 … Lbn. You have to make ‘n’ pairs of the red and blue sticks. Suppose a pair contains a red stick of length Lrx and a blue stick of length Lby. The difference between the lengths of the two paired sticks is | Lrx - Lby |. Your goal is to minimize the average of length-differences of all the pairs (i.e., minimize ( | Lrx - Lby | ), n 1∑ where x and y range from 1 to n. Does the following greedy solution work? If yes, then it using Stays-Ahead or Exchange argument, otherwise provide a counter-example. Sort the red and blue sticks in increasing order of their lengths. Suppose ra, rb, rc … are the red sticks in sorted order and ba, bb, bc … are the blue sticks in sorted order. Match rawith ba, rb with bb, rc with bc, and so-on until ‘n’ pairs are created. Your friend runs a company that delivers organs for transplantation to hospitals. Since lives are at stake, these organs have to be delivered as quickly as possible. Your friend transports these organs in special medical vehicles (MV) through fast highways. There are a number of petrol stations along the highway and your friend has tospent in stopping for petrol. A full tank on the MV can holdT litres of petrol. The vehicle consumes petrol at the rate of R litres per km. If your friend decides to stop at a station then filling the tank takesF litres per minute (assume that filling the tank is the only delay incurred at the station). The starting point of the trip is your friend’s office ‘O’ and ending point is the hospital ‘H’. You are given the locations (L1, L2, L3, … Ln) of petrol stations along the O-H route (assume that the O-H route is a straight line and L1, L2 are distances in kilometers from the starting point O along that line. The distance between any two stations will not be greater than T/R km). Assume that MV’s fuel tank is full at starting point O. You have to design a algorithm that decides when and where to stop for petrol and how much to fill, while minimizing the overall time required in stopping for petrol. 1. Code an algorithm in C/C++ that solves the above problem. Your code will take as input the values of T R F and the locations of the petrol stations. See the input format below. [7]

2. Your algorithm should output the locations where MV stopped for petrol and the time (in minutes) spent at each station. Also output the total time at all the stopping locations. [2] 3. that your algorithm is correct using an Exchange argument. [5] 4. Give a clear description of your algorithm and the data structures used to implement it in the comments at the beginning of your code. Your should include clear comments that explain your algorithm’s time and space complexity. [2+1] 5. You should create at least three different input files to test your algorithm for different scenarios (see format below). [3]
Your code will read input from a text file. The format of the file is as follows. The first three lines contain the values of , respectively. The fourth line contains ‘n’, the number of petrol stations along the O-H route. This will be followed by n lines (one for each of the n locations) indicating the distance of that location from the starting point O. The last line in the input file indicates the distance of H (hospital) from O. An example is given below. T 50 R 3 F 2 n 4 L1 6 L2 12 L3 25 L4 30 H 35
L1 6, L4 30 Total time: 36 The output values do not indicate the correct answer for this example. They are being used to illustrate the output format.
You are given an nxn square game board and positive integers row1, row2, … rown and col1, col2, .. coln. You have to place game pieces in the squares in such a way that the number of game pieces in ith row is equal to rowi and the number of game pieces in the ith column is equal to coli. For example, let n=4. You are given as input a blank 4x4 board and the following integers: row1=2, row2=2, row3=2, row4=3 col1=3, col2=2, col3=1, col4=3

One possible arrangement of game pieces on the board, satisfying the above row and column values, is as follows:
1. Code an algorithm in C/C++ that solves the above problem. Your code will take as input the value of ‘n’ and the row and column values. See the input format below. [8] 2. Your algorithm should output the (row, column) indices where game pieces are placed. See format below. If it is not possible to satisfy the row and column values given in the input, then your algorithm should output “Not possible”. [2] 3. Give a clear description of your algorithm and the data structures used to implement it in the comments at the beginning of your code. Your should include clear comments that explain your algorithm’s time and space complexity. [2+1] 4. You should create at least three different input files to test your algorithm for different scenarios (see format below). [3] n 4 Row 2 2 2 3 Col 3 2 1 3
(1,1) (1,4) (2,1) (2,2) (3,3) (3,4) (4,1) (4,2) (4,4)
Consider a large warehouse where the inventory items for storage are stacked in ‘n’ racks. Assume all the racks are placed in a straight line as shown in the figure below. The racks are of different lengths L1, L2, .. Ln.

One type/category of items are placed together on one rack. Depending on the sales, different items require replenishment more often than others. Each of the racks have replenishment probabilities associated with them, which are denoted by p1, p2, … pn. A robot stands on the left of the first rack and when it receives a replenishment request, it goes to the appropriate rack and fills it up. We want to come up with an ordering of the racks, along a straight line, such that the replenishment time is . That is, for all the ‘n’ racks, you have to decide which rack should be placed where, starting from the first position on the left to last on the right. For example, suppose n=3 and rack3 is placed first, followed by rack1 and lastly rack2. The expected replenishment time is given by: p3 x L3 + p1 (L3+L1) + p2 (L3+L1+L2). If we change the ordering in the above example to rack2, rack3, rack1, then the expected replenishment time will be p2 x L2 + p3 (L2+L3) + p1 (L2+L3+L1). If the ordering is denoted by O1, O2, … On, then the general formula for expected time is given as follows:
pOx ( LOy)∑ x=n x=1 ∑ x y=1 You have to come up with a strategy for rack ordering that minimizes the expected replenishment time. 1. Code an algorithm in C/C++ that solves the above problem. Your code will take as input the value of ‘n’ and the lengths of the racks and their replenishment probabilities. See the input format below. [8] 2. Your algorithm should output the ordering of the racks as well as the expected time. See format below. [2] 3. Give a clear description of your algorithm and the data structures used to implement it in the comments at the beginning of your code. Your should include clear comments that explain your algorithm’s time and space complexity. [2+1] 4. You should create at least three different input files to test your algorithm for different scenarios (see format below). [3] n 4 L 12, 2, 8, 3

p 0.3, 0.2, 0.4, 0.1
rack1, rack4, rack2, rack3 Expected time: 18.5 The output values do not indicate the correct answer for this example. They are being used to illustrate the output format.
Consider a railway network that connects a large number of cities across the country. A big oil company is laying pipelines along a rail network. The rail network has ‘n’ junctions and the oil company has set up booster stations at each junction. They want to the total length of the pipes they have to lay such that there is a path for oil between every pair of junctions. The engineers at the oil company have constructed an undirected, weighted graph G(V,E) with ‘n’ vertices (i.e., junctions) and ‘m’ railway tracks. To minimize the total pipe lengths along the rail tracks they have constructed a minimum spanning tree ‘T’ of G and installed pipes along the edges of T.
One day, due to an earthquake, one of the railway tracks and also the pipe alongside it is permanently damaged. The engineers have to quickly construct a new minimum spanning tree T2 after removing the damaged rail track from the graph G. You have to help the engineers. if you say rerun a minimum spanning tree (MST) algorithm on the rail network, you will not get any marks. A. Code an algorithm in C/C++ to solve the above problem. The input to your program is a weighted undirected graph G (format is similar to one described in Q3, except that the graph is undirected. See example below.). You will find T of G using any of the MST algorithms studied in class. Now delete an arbitrary edge ‘e’ from T and find the new MST (T2) without re-running the MST algorithm. Your program should output the MST ‘T’, the edge ‘e’ you have removed from T, and the new MST T2. For outputting the MST, it is sufficient if you list all its edges. Note: it is possible that a new spanning tree T2, including all the vertices of G, cannot be constructed after deletion of ‘e’ (think about why). In that case, simply print that T2 cannot be constructed. [8] B. Give a clear description of your algorithm and the data structures used to implement it in the comments at the beginning of your code. Your should include clear comments that explain your algorithm’s time and space complexity. [2+1] C. You should create at least three different input files to test your algorithm for different scenarios (see format below). [3]
An example of graph G is below. n 5 C0: C1;3, C2;4 C1: C0;3, C3;5, C4;2 C2: C0;4, C3;4

C3: C1;5, C2;4, C4;2 C4: C1;2, C3;2
Output: MST1: (C1,C2),(C3,C2) Edge Removed: (C3,C1) MST2: (C1,C2),(C3,C2) The output values do not indicate the correct answer for this example. They are being used to illustrate the output format. This is a continuation of Q5a. You have the same initial rail network G(V,E) described in Q5a. This time there is no earthquake but the railway company has added a new railway track between two of the junctions (there was no direct track between these junctions previously). The railway engineers want to know what the new MST T2 looks like after the addition of this new link. As in Q5a, you are not allowed to rerun the MST algorithm to find T2. A. Code an algorithm in C/C++ to to find T2. The input to your program is same as in Q5a. Add a new link to G between two vertices that did not have an edge previously. Your program should output the original MST ‘T’ (reuse code from Q5a), the edge ‘e’ you have added to G and the new MST T2. For outputting the MST, it is sufficient if you list all its edges. [9] B. Give a clear description of your algorithm and the data structures used to implement it in the comments at the beginning of your code. Your should include clear comments that explain your algorithm’s time and space complexity. [2+1] C. Reuse the input files you created in Q5a to test your algorithm for different scenarios.
Output format for the above question is the same as Q5a.
Read Section-5.3 of the book ‘Algorithms’ . . . . . . You have to implement the greedy algorithm in Section 5.3 for Horn formula satisfiability in time that is in the length of the formula (i.e. the number of occurrences of literals in the formula). 1. Implement the algorithm of Section 5.3 in C/C++ that runs in time that is linear in the length of the formula. The input file will contain each clause on a separate line. The variables will always be named x1, x2, … xn. Negation of a variable is indicated by a single apostrophe (’). The symbol ^ stands for logical AND and v stands for OR in the input. The first line of the input file will mention the number of variables ‘n’. See the input format below. [8] 2. Your algorithm should output the satisfying assignment for each variable, if such an assignment exists. Otherwise, output “Not satisfiable”. See format below. [2]

3. Give a clear description of your algorithm and the data structures used to implement it in the comments at the beginning of your code. Your should include clear comments that explain. Also, mention how much space your algorithm uses. [2+1] 4. You should create at least three different input files to test your algorithm for different scenarios (see format below). [3]
n 4 (x1 ^ x2 ^ x3) = x4 (x4 ^ x3) = x1 x4 = x2 = x4 (x4 ^ x2) = x1 (x1’ v x4’ v x2’) (x3’)
x1=1 x2=1 x3=0 x4=1 Not satisfiable
1. You must submit your own work. You may discuss the problems with other classmates but must not reveal the solution to others or copy someone’s work. Remember to acknowledge other classmates if discussions with them has helped you. 2. You should name your code files using the following convention: Qx-rollno.c 3. Type your answer to the theoretical questions (Q1 & Q2 part-3) and submit a separate pdf file for each using the naming convention above. 4. Upload all your files in Assignment-1 folder on LMS. 5. There will be vivas during grading of the assignment. The TAs will announce a schedule and ask you to sign up for viva time slots. Failure to show up for vivas will result in a in the assignment. 6. In most of the questions, you are asked to create test cases. Think carefully about good test cases that check different conditions and corner cases. The examples given in the assignment are for clarity and illustration purposes. You should not assume that those are the only test cases your code should work for. Your code should be able to scale up to larger input sizes and more complex scenarios.

7. Do not make arbitrary assumptions about the input or the structure of the problem without clarifying them first with the Instructor or the TAs. 8. Make sure that your code compiles and runs on Ubuntu. You may choose to develop your code in your favourite OS environment, however, the code must be properly tested on Linux before submission. During vivas, your code should not have any compatibility issues. It's a good idea to use gcc -Wall option flag to generate the compiler's warnings. Pay attention to those warnings as fixing them will lead to a much better and robust code. 9. For full credit, comment your code clearly and state any assumptions that you have made. As mentioned in the beginning of the assignment, there are marks for writing well-structured and efficient code.