__MACOSX/._Files Files/Parser.java Files/Parser.java import java.util.*; import java.io.InputStream; public class Parser { String fileName = "input.txt"; InputStream file; public Parser() {...

In this project, you will solve the "Scheduling Problem". In this problem, your input will be a list of "Student Rosters". Each Roster is a (space- separated) list of student IDs. Please see attached file to read full programming instructions. The language needed is Java. Thank you.

__MACOSX/._Files Files/Parser.java Files/Parser.java import java.util.*; import java.io.InputStream; public class Parser {     String fileName = "input.txt";     InputStream file;     public Parser() {         file = Parser.class.getResourceAsStream(fileName);     }     /**      * Parses the input text file. This returns a list of "roster lists".      * courses.get(0) will be a list of the student IDs in course 0      * course.get(1) will be a list of student IDs in course 1      * etc.      *      * You then need to turn this "list of rosters" into a graph!      * @return      */     public List<>> listOfRosters() {         Scanner sc = new Scanner(file);         List<>> courseToStudentList = new ArrayList<>();         while (sc.hasNextLine()) {             String line = sc.nextLine();             ArrayList list = new ArrayList<>();             Scanner lineScanner = new Scanner(line);             while (lineScanner.hasNextInt()) {                 list.add(lineScanner.nextInt());             }             courseToStudentList.add(list);         }         sc.close();         return courseToStudentList;     }     public static void main(String[] args) {         Parser p = new Parser();         List<>> courses = p.listOfRosters();         System.out.println(courses);     } } __MACOSX/Files/._Parser.java Files/Assignment 3.pdf Assignment 3 In this project, you will solve the "Scheduling Problem". In this problem, your input will be a list of "Student Rosters". Each Roster is a (space- separated) list of student IDs. Part 1 For the first part, you must form the "Graph" that arises from the roster lists. We can associate a list of course rosters with a graph in a canonical way: • the nodes are the courses (use numbers 0, 1, 2, ... numCourses - 1) • two courses i and j share an (undirected) edge if and only if there is at least one student in both roster lists. Try to find the most efficient way to form this graph. I am attaching a sample input and a Parser file: you can use that parser file to generate the List of List of students, and then you must output the graph (output the set of pairs of nodes which have edges). Part 2 In this part, you must then output a schedule for the courses. A schedule is valid if no two courses which have a student in common are scheduled for the same time slot (a student cannot be in two places at once). You should output the list of courses that are scheduled for time slot 0, the list scheduled for time slot 1, etc. Ideally, your output should be minimal. In class, this problem was mentioned to be equivalent to the graph coloring problem, which is NP- complete, and so it is unlikely you can solve this problem in full generality. There are, however, some heuristic graph coloring algorithms which you can look for (not in your textbook). Note: I should be able to run Parts 1 and Parts 2 independently. So you will need two Main classes in your project! Part 3 In this part, I would like you to try to break your algorithm. That is, come up with a graph such that your algorithm does not output the minimum coloring for that graph. You should describe this in a separate file (Word doc, text file, PDF are all fine). Hint: start with a coloring (ie: nodes 0, 2, 5 will have color red, 1, 3, 6 will be green, 4 will be blue) and try to work backwards to a graph. In this part, I would also like you to describe the coloring algorithm you implemented. Did you come across any other algorithms that you chose not to use? Explain why you chose this algorithm or what the motivation behind this algorithm is. __MACOSX/Files/._Assignment 3.pdf Files/input.txt 1 3 5 8 10 7 6 11 2 3 4 6 7 7 8 9 __MACOSX/Files/._input.txt