Word Document has the 3 exercisesGraph Coloring Problem Statement Graph coloring is a special,...

Question

Word Document has the 3 exercisesGraph Coloring Problem Statement Graph coloring is a special, common, yet simply described problem- How can we assign a color to every node of a graph such that no two nodes which share an edge also share the same color? Here's an example using an undirected graph: Notice how no node has any neighbors with the same color as itself.  This problem is a good introduction to Greedy algorithms, which are algorithms that makes the best sounding decision at each step of solving the problem in hopes that the overall solution will be optimal in the end. Greedy algorithms are sometimes successful in finding the optimal solutions, but not always. For example, in this specific problem the greedy approach doesn't guarantee to use the minimum number of colors but it does provide an upper bound of no more colors than the maximum degree of a vertex in any graph- which is still pretty good for a relatively simple algorithm. The greedy algorithm for graph coloring is as follows: 1. Color the starting vertex with the first color 2. For the remaining vertices, color it with the a color that has been used before but is not the color of any adjacent vertex. If there are none, make a new color and assign it to that vertex. For this assignment, you will be asked to fill in the color method, which has a signature of std::vector color(Graph& graph) which takes in a reference to a graph object, which is defined by the following snippet: class Graph { public: 	// An array of vectors to represent an adjacency list 	vector> adjList; 	// The number of vertices in the graph 	int V; 	// The Constructor 	Graph(...) {...} }; The method will return a vector of strings, in upper case, denoting the color of the ith node in the order that was given in the Graph class's adjList member. The colors are ranked as such: 0 - RED 1 - BLUE 2 - GREEN 3 - YELLOW 4 - ORANGE 5 - PURPLE This means the first node should be assigned red, and you should be assigning the next node blue and so on.  Example Graphs will be inputted as a vector of edges, so for example take the following graph: It will be inputted as [[0,1], [0,4], [0,5], [4,5], [1,4], [1,3], [2,3], [2,4]] and the expected output is: Vertex 0: RED Vertex 1: BLUE Vertex 2: RED Vertex 3: GREEN Vertex 4: GREEN Vertex 5: BLUE This is visually as follows: And we are confident in our result as no two adjacent nodes share the same color. Constraints · The graph is undirected and will always be connected · 1  color(Graph& graph) {        // CODE HERE } Backpack Problem / 0-1 Knapsack Problem Problem Statement There are N items and a backpack with capacity W. Given an array weights representing the weight of each item in the backpack and an array values representing the value of each item. Write a method to find the maximum value you could put into the backpack given the capacity of W. The prototype of the method is as followed:  int backpack(int W, vector weights, vector values) Constraints · You cannot split an item · The total weights of the items that you need to put into the backpack cannot exceed backpack capacity W.  · Each item can only be chosen once.  Input: W = 4, weights = [1,1,2,2], values = [1,2,4,5] Output: 9 Explanation: If we put weights[2] and weights[3] into the backpack, we can get the maximum value of 4 + 5 = 9. And the capacity of the backpack is not exceeded. Test cases · The first line of input specifies the capacity of the backpack · The second line of input lists the weight of each item.  · The third line of input lists the value of each item. · The output indicates the maximum value you could put into the backpack of capacity W. Sample Input: 4 [1,1,2,2] [1,2,4,5] Sample Output: 9 MUST USE THIS FUNCTION AS SOLUTION IN C++ int backpack(int W, vector weights, vector values) { 	// CODE HERE } Topological Sorting in Course Scheduling System Problem Statement Given the total number of courses as numCourses and a list of prerequisites pairs as req, implement finishCourses method to determine whether the students could finish all the courses based on the current course scheduling system. As for the pair in the prerequisites list, e.g. [2, 1] means that students have to take course 2 before taking course 1.  Example: Input: numCourses = 3, req = [[1, 0], [0, 2]] Output: true Explanation · There are a total of 3 courses to take. This information is denoted by numCourses · [1,0] means before taking course 0, students have to take course 1. [0, 2] means before taking course 2, students have to take course 0 · In this example, students could first take course 1, then course 0 followed by course 2. Thus, it is possible for students to finish all the courses and we output true. Test Cases · The input req is a graph represented by a list of edges. · There are no duplicate or parallel edges in the input req. Note · You are required to return true of false based on the current course prerequisites list. You don't need to print out anything in your finishCourses method implementation.  MUST USE THIS FUNCTION AS SOLUTION IN C++ bool finishCourses(int numCourses, vector> req) { 	// your code }

Graph Coloring Problem Statement Graph coloring is a special, common, yet simply described problem- How can we assign a color to every node of a graph such that no two nodes which share an edge also...

Get Answer To This Question

Related Questions & Answers

Submit New Assignment