Programming Assignment #2 Solution

Preamble



Description of a programming assignment is not a linear narrative and may require multiple readings before things start to click. You are encouraged to consult instructor/Teaching Assistants for any questions/clari cations regarding the assignment. You can work in group of size at most 2. It is your responsibility to nd a classmate (taking this course with you) with whom you can work e ectively. Your programs must be in Java, preferably Java 8.1.




Q1: Shortest Path Problems



We have covered single source shortest path problem and used Dijkstra's algorithm to address the problem in O((jV j + jEj)lg(V )) time for a graph G = (V; E; wt) (V is the set of vertices, E is a set of edges and wt : E ! N). In this assignment, you will write algorithms to solve di erent variants of shortest path problems. We will denote any path as as a sequence of vertices in the path. We will denote source and destination of as src( ) and dest( ). The cost of a path, cost( ), is the sum of the weights of the edges in the path.




V 2V problem: Given vertices u and v, nd the shortest path to from u to v. We will refer to such a path as V 2V (u; v).



V 2V (u; v) = argmin cost( j src( ) = u and dest( ) = v)




V 2S problem: Given a vertex u and a set of vertices S, nd the shortest path from u to some vertex in S. We will refer to such a path as V 2S(u; S).



V 2S(u; S) = argmin cost( j src( ) = u and dest( ) 2 S)




S2S problem: Given a set of vertices S1 and a set of vertices S2, nd the shortest path from some vertex in S1 to some vertex in S2. We will refer to such as path as S2S(S1; S2).



S2S(S1; S2) = argmin cost( j src( ) 2 S1 and dest( ) 2 S2)










1



1.1 Your Task for Q1




You are required to design a class with the following properties:




Classname and constructor: WGraph. The constructor of this class will take as input (a String type) a le-name F N ame. It should read the le with the name F N ame from the same directory and create a graph representation from the le data (how you represent the graph will depend on you: adjacency matrix, adjacency list, list of edges, etc. The representation will also indicate what type of member variables and methods you need for the class). The le data is formatted as follows:



First line contains a number indicating the number of vertices in the graph



Second line contains a number indicating the number of edges in the graph



All subsequent lines have ve numbers: source vertex coordinates ( rst two numbers), destination vertex coordinates (third and fourth numbers) and weight of the edge con-necting the source vertex to the destination (assume direction of edge from source to destination)



For example:




4




4




1 2 3 4 10




5 6 1 2 9




3 4 5 6 8




1 2 7 8 2




Numbers in the same line are separated by a single space.




Your class should contain three methods with the following signatures:



The pre/post-conditions describes the structure of the



input/ouput. The semantics of these structures depend on



defintion of the corresponding method.



pre: ux, uy, vx, vy are valid coordinates of vertices u and v



in the graph



post: return arraylist contains even number of integers,



for any even i,



i-th and i+1-th integers in the array represent



the x-coordinate and y-coordinate of the i-th vertex



in the returned path (path is an ordered sequence of vertices) ArrayList<Integer V2V(int ux, int uy, int vx, int vy)



pre: ux, uy are valid coordinates of vertex u from the graph



S represents a set of vertices.



The S arraylist contains even number of intergers



2



for any even i,



i-th and i+1-th integers in the array represent



the x-coordinate and y-coordinate of the i-th vertex



in the set S.



post: same structure as the last method's post. ArrayList<Integer V2S(int ux, int uy, ArrayList<Integer S)



pre: S1 and S2 represent sets of vertices (see above for



the representation of a set of vertices as arrayList)



post: same structure as the last method's post. ArrayList<Integer S2S(ArrayList<Integer S1, ArrayList<Integer S2)



The de nitions of these methods follow the problem de nitions for V 2V , V 2S and S2S above.













Q2: Image Processing



We will consider the problem of resizing images. We will proceed with the notion of a min-cost vertical cut in a 2-D matrix. We will use this notion to address the resizing problem.




2.1 Cuts




Let I be a n m integer matrix (with n rows and m columns). Assume that rows are numbered 0; 1; 2; ; n 1 and columns are numbered 0; 1; 2; m 1. A vertical cut V of I is a sequence of 2n integers [x0; y0; x1; y1; ; xn 1; yn 1] such that the following holds




x0 = 0, y0 2 f0; ; m 1g



For 1 i < n, xi = xi 1 + 1



For 1 i < m yi 2 fyi 1; yi 1 1; yi 1 + 1g



The cost of a vertical cut V = [x0; y0; x1; y1; ; xn; yn] of I is de ned as




CostI (V ) = I[x0; y0] + I[x1; y1] + + I[xn 1; yn 1]




Given a matrix, the min-cost vertical cut, denoted M inV C(I), is a vertical cut whose cost is the smallest:

M inV C(I) = argmin CostI (V )




2.2 Vertical Cut and Image Resizing




Note that an image is 2-dimensional array of pixels. Each pixel has represented as 3-tuple in the RGB format. Given an image of height H and width W , it is represented by a H W matrix (2-D array). In this problem, we will assume that H and W are both greater than 1. For example, an image with H = 3 and W = 4 is represented as the following 2-D array of pixels M:










3



[98,
251, 246]
[34, 0, 246]
[255,
246,
127]
[21,
0,
231]
[25,
186,
221]
[43, 9,
127]
[128,
174,
100]
[88,
1,
143]
[46,
201,
132]
[23, 5,
217]
[186,
165,
147]
[31,
8,
251]



In the above M[i; j] (i 2 [0; 2]; j 2 [0; 3]) refers to the pixel in the ith row and jth column. For example M[2; 3] is [31; 8; 251] and M[0; 0] is [98; 251; 246].




Suppose you would like to reduce the width of an image. Standard techniques such as cropping may remove some prominent features of the image. Ideally, we would like to preserve most important features of an image even after reducing the width. Consider that for an image of width W , we would like to re-size it to width W 1. Thus we would like to remove one pixel from each row of the image, so that the width becomes W 1. Which pixels should be removed from each row? One possible solution would be remove the pixels that are not important. How do we decide on importance of a pixel? There are several alternatives, in this assignment we consider the following simple method to decide the importance of a pixel.

Given two pixels p = [r1; g1; b1] and q = [r2; g2; b2], we de ne




P Dist(p; q) = (r1 r2)2 + (g1 g2)2 + (b1 b2)2




Given a picture with width W and height H for any pixel M[i; j], 0 i < H, its YImportance is




Y Importance(M[i; j]) =
8
P Dist(M[i 1; j]; M[0; j])
if i = H 1


<
P Dist(M[H
1; j]; M[i + 1; j])
if i = 0


P Dist(M[i


1; j]; M[i + 1; j])
otherwise


:






Similarly, given a pixel M[i; j], 0 j < W , its XImportance is






8
P Dist(M[i; W 1]; M[i; j + 1])
if j = 0
XImportance(M[i; j]) =
P Dist(M[i; j
1]; M[i; 0])
if j = W 1


:


1]; M[i; j + 1])
otherwise


<
P Dist(M[i; j
Finally,




Importance(M[i; j]) = XImportance(M[i; j]) + Y Importance(M[i; j])




Now, coming back to our problem of reducing the image width, we will apply the following procedure to reduce width from W to W 1.




Compute a Matrix named I, where I[i; j] = Importance(M[i; j]).




Compute M inV C(I). Let it be V = [x0; y0; x1; y1; ; xH 1; yH 1]. You must compute the Min-Cost vertical cut using some variant of shortest path problems (from Q1).




For every xi; yi in the vertical cut V , remove the pixel M[xi; yi] from the image. Now the width of the image is W 1.




To reduce the width from W to W k 1, repeat the above procedure k times.



















4



2.3 Your Task for Q2




You are required to design a class with the following properties:




Classname and Constructor: ImageProcessor. The constructor of this class takes as input (a String type) a lename FName. The le with this name will be read from the same directory to obtain the data related to pixels of some image. The le data is formatted as follows:



First line contains the height H of the image as a number



Second line contains the width W of the image as a number



All subsequent lines contains pixel values at M[i; j] (0 i < H, 0 j < W ). For instance,



3




4




98 251 246 34 0 246 255 246 127 21 0 231




25 186 221 43 9 127 128 174 100 88 1 143




46 201 132 23 5 217 186 165 147 31 8 251




The numbers in the same line are separated by a single space. You can decide the way you want to represent the matrix M.




Methods



Compute Importance matrix: The matrix I capturing the importance values for each element in M



pre:



post: returns the 2-D matrix I as per its definition ArrayList<ArrayList<Integer getImportance()



Compute the reduced image (reduction in width by k) and write the result in a le



pre: W-k 1



post: Compute the new image matrix after reducing the width by k



Follow the method for reduction described above



Write the result in a file named FName



in the same format as the input image matrix



void writeReduced(int k, String FName)




Postscript



You shall use default package. Though it is not recommended in practice, you can write all your classes for each problem in one le. For the Q1, you will submit WGraph.java and for Q2, you will submit ImageProcessor.java.



Submit the README.txt including the names and netids of all group members (alphabetical order by last name):




Lastname1 FirstName1 netid1 Lastname2 FirstName2 netid2




5



You must follow the given speci cations. Method names, classnames, return types, input types. Any discrepancy may result in lower than expected grade even if \everything works".



In the above problems, there are several data structure/organization that are left for you to decide. Do not ask questions related to such data structure/organization. Part of the exercise to understand and assess a good way to organize data that will allow e ective application of methods/algorithms.



In Q2, you will have to think about how to model the problem into a graph-based problem and apply your knowledge of graph algorithms to address the original problem. Do not ask questions about how to model the problem as a graph-based problem and/or what graph algorithms to use (though in this assignment, it is clear that we are looking to apply shortest path related algorithm). Part of the exercise is to understand and assess a good way to represent/reduce a problem to a known problem for which we know an e cient algorithm.



Start reading and sketching the strategy for implementation as early as possible. That does not mean starting to \code" without putting much thought on what to code and how to code it. This will also help in resolving all doubts about the assignment before it is too late. Early detection of possible pitfalls and di culties in the implementation will help in reducing the nishTime-startTime for this assignment.



Both correctness and e ciency are important for any algorithm assignment. Writing a highly e cient incorrect solution will result in low grade. Writing a highly ine cient correct solution may result in low grade. In most cases, the brute force algorithm is unlikely to be the most e cient. Use your knowledge from lectures, notes, book-chapters to design and implement algorithms that are correct and e cient. In addition to typical correctness validation, your implementation will be tested on at least one large graph (and/or image).



If you would like to generate pixels from real images, you can use the following code available at https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Picture.java.html with documentation at https://algs4.cs.princeton.edu/code/javadoc/edu/princeton/cs/algs4/Picture.html


































































6