Project-Management

Job Scheduler

Trie, Red-Black tree and Priority queue

Changes:

Download the new Makefile. Replace the current Makefile in the src folder with this one. This takes care of the file encoding issues while comparing. Constant files, the files that you are NOT suppose to change can be found here: Download constant files. Just replace these files in their respective directories. You can make changes to other files as per your requirements. Brief description:

In this assignment you need to work with Tries, Red-Black trees and Priority queues. There will be four components of the assignment. The first three will check tries, red-black trees and priority queues independently. The last part of the assignment will be a combination of all the previous components.

2 General instructions

The grading will be done automatically. To ensure a smooth process, an interface will be provided to you, which you are NOT suppose to change. Your solution classes will implement these interfaces.

For each of the component, you will be given and input file, which will contain the commands that your code must execute. As per the command, the program will produce the output, which will be compared against an expected output for grading. Please ensure that you follow the proper formatting criteria, failing to do so will results in a penalty or no marks for that particular component.

2.1 Code skeleton

You are provided with the skeleton of the code. This contains the interfaces and other relevant information. Your task is to implement these functions. The code also contains driver code for all the components of assignment. These will be used to check the correctness of the code. Please DO NOT modify the interface and the driver code. You are free to change and implement other parts in any way you like.

Code can be downloaded from here: Download code

2.1.1 Building and Running

In the code, within the src folder, you can use the following commands to check your code.

make This will check all the components. Components can also be checked independently:

make trie
make rbtree
make pq
make pm for Trie, Red-Black tree, Priority-Queue and Project-Management (4th component) respectively.

3 Trie [1 Mark]

Trie is an efficient information reTrieval data structure. Using Trie, search complexities can be brought to optimal limit (key length) [3].

In this part of the assignment, you need to implement a Trie data structure. To make things interesting, you will be implementing a telephone directory using Tries. Name of a person will be the key (assuming all names are unique). Associate with every name will be a Person object.

1package Trie; 2public class Person { 3 public Person(String name, String phone_number) { 4 } 5 public String getName() { 6 return ""; 7 } 8} Listing 1: Person class. 3.1 Interface

You version of Trie must implement the TrieInterface as shown in Listing 2 and is also present in the code provided.

1package Trie; 2/** 3 * DO NOT EDIT THIS FILE. 4 / 5public interface TrieInterface { 6 /* 7 * @param word Word to be input in the Trie 8 * @param value Associated value of the word 9 * @return Success or failure 10 / 11 boolean insert(String word, T value); 12 /* 13 * @param word Search for this word, Case-Sensitive 14 * @return Returns the Trienode associated if the word is found else NULL 15 / 16 TrieNode search(String word); 17 /* 18 * 19 * @param prefix Search a particular prefix 20 * @return Returns the last Trienode associated with the prefix. Eg: If PARIS and PARROT is in the Tries, searching for PAR, returns the trienode of first R 21 / 22 TrieNode startsWith(String prefix); 23 /* 24 * 25 * @param trieNode Prints all the possible word possible from this Trienode 26 * Eg: PAR and PARIS, printTrie(startWith("PAR")) should print PARIS and PARROT i.e all the words with suffix PAR 27 / 28 void printTrie(TrieNode trieNode); 29 /* 30 * 31 * @param word Delete a word from the Trie 32 * @return Success or Failure 33 / 34 boolean delete(String word); 35 /* 36 * Print the complete Trie 37 / 38 void print(); 39 /* 40 * Print a specific level of the Trie. 41 * 42 * @param level 43 */ 44 void printLevel(int level); 45} Listing 2: Interface specifications for Trie. 3.2 Input specifications

Commands:

INSERT: It takes a Person name and phone number (in next line) as input and inserts that into the trie. 2. DELETE: It takes a String as an input and deletes that from the trie. 3. SEARCH: It takes a String as input and returns true or false, based on whether that word is present in trie or now. 4. MATCH: It takes a String as an input, and return all words where the prefix is the entered String. Printing is done in a lexicographical order. 5. PRINTLEVEL: Print the specified level in lexicographical order separated by comma and DO NOT print spaces. 6. PRINT: Print all the LEVELS of the trie. The print format same as that of PRINTLEVEL. Sample input file:

1INSERT 2Diljeet Singh, +91987654321 3INSERT 4Bhavesh Kumar, +91987654321 5INSERT 6Chayan Malhotra, +91987654321 7INSERT 8Ekta Mittal, +91987654321 9INSERT 10Farhan Khan, +91987654321 11INSERT 12Dishant Goyal, +91987654321 13INSERT 14Dishant Kumar, +91987654321 15INSERT 16Dishant Gupta, +91987654321 17SEARCH 18Dishant Goyal 19MATCH Di 20MATCH di 21DELETE 22Dishant Goyal 23SEARCH 24Dishant Goyal 25MATCH SK 26PRINTLEVEL 2 27PRINT 28DELETE 29Dishant Goyal Listing 3: Input for Trie. Expected Output file:

1Inserting: Diljeet Singh 2Inserting: Bhavesh Kumar 3Inserting: Chayan Malhotra 4Inserting: Ekta Mittal 5Inserting: Farhan Khan 6Inserting: Dishant Goyal 7Inserting: Dishant Kumar 8Inserting: Dishant Gupta 9Searching: Dishant Goyal 10FOUND 11[Name: Dishant Goyal, Phone=+91987654321] 12Matching: Di 13MATCHED: 14[Name: Diljeet Singh, Phone=+91987654321] 15[Name: Dishant Goyal, Phone=+91987654321] 16[Name: Dishant Gupta, Phone=+91987654321] 17[Name: Dishant Kumar, Phone=+91987654321] 18Matching: di 19NOT FOUND 20Deleting: Dishant Goyal 21DELETED 22Searching: Dishant Goyal 23NOT FOUND 24Matching: SK 25NOT FOUND 26Level 2: a,h,h,i,k 27------------- 28Printing Trie 29Level 1: B,C,D,E,F 30Level 2: a,h,h,i,k 31Level 3: a,a,l,r,s,t 32Level 4: a,h,h,j,v,y 33Level 5: a,a,a,e,e 34Level 6: M,e,n,n,n,s 35Level 7: h,i,t,t 36Level 8: K,M,t 37Level 9: G,K,K,S,a,h,t 38Level 10: a,a,i,l,u,u,u 39Level 11: h,l,m,m,n,n,p 40Level 12: a,a,g,o,t 41Level 13: a,h,r,r,t 42Level 14: r 43Level 15: a 44Level 16: 45------------- 46Deleting: Dishant Goyal 47ERROR DELETING Listing 4: Ouput for Trie. 4 Red-Black Tree [1 Mark]

In this part you need to implement a Red-Black tree. A tutorial on Red-Black tree can be found here [2]. In this part, the basic operations on a Red-Black tree, insert and search will be tested. Note: you are not required to implement the delete feature. You will be given an input file, whose format is listed in Section 4.2. A sample output for the input command given in Section 4.2 is shown in 7

In this case also you will implement a telephone directory, with an extra feature that a person can have multiple numbers.

4.1 Specifications

You Red-Black tree, must implement the interface as shown in listing 5.

1package RedBlack; 2public interface RBTreeInterface<T extends Comparable, E> { 3 /** 4 * Insert and element using the "key" as the key and the corresponding value. 5 * Please note that value is a generic type and it can be anything. 6 * 7 * @param key 8 * @param value 9 / 10 void insert(T key, E value); 11 /* 12 * Search using the key. 13 * 14 * @param key 15 * @return 16 */ 17 RedBlackNode<T, E> search(T key); 18} Listing 5: Interface for Red-Black tree. Things to keep in mind:

All the items insert into the RB-Tree has a key and the corresponding value with it. In this version of Red-Black tree, a key can have multiple items. If we are trying to insert an element with a key which is already present in the tree, the value will get attached /appended to that key. This can be seen in the Listing 6. 4.2 Input specifications

Commands:

INSERT: Insert a Person into the tree. 2. SEARCH: Searches for a person in the tree. Sample input (ignore the line numbers):

1INSERT 2Diljeet Singh, +91987654321 3INSERT 4Bhavesh Kumar, +91987654321 5INSERT 6Chayan Malhotra, +91987654321 7INSERT 8Ekta Mittal, +91987654321 9INSERT 10Farhan Khan, +91987654321 11INSERT 12Dishant Goyal, +91987654321 13INSERT 14Dishant Goyal, +91999999999 15INSERT 16Dishant Kumar, +91987654321 17INSERT 18Dishant Gupta, +91987654321 19SEARCH 20Dishant Goyal 21SEARCH 22Sandeep Listing 6: Input for RedBlack Tree. Expected Output (ignore the line numbers):

1Inserting: Diljeet Singh 2Inserting: Bhavesh Kumar 3Inserting: Chayan Malhotra 4Inserting: Ekta Mittal 5Inserting: Farhan Khan 6Inserting: Dishant Goyal 7Inserting: Dishant Goyal 8Inserting: Dishant Kumar 9Inserting: Dishant Gupta 10Searching for: Dishant Goyal 11[Name: Dishant Goyal, Phone=+91987654321] 12[Name: Dishant Goyal, Phone=+91999999999] 13Searching for: Sandeep 14Not Found Listing 7: Output for RedBlack Tree. 5 Priority queues [1 Mark]

In this part you will be working with a priority queue. Specifically, you will be implementing a max-heap which is an implementation of priority queue.

You will need to implement a marks scoring system using Max Heap. This will contains, students name and their corresponding marks. The max-heap will use the marks to arrange the students, i.e. the student with the highest marks will be on the top.

5.1 Specifications

1package PriorityQueue; 2/** 3 * DO NOT EDIT 4 * 5 * @param 6 / 7public interface PriorityQueueInterface { 8 /* 9 * @param element Insert and element to the Priority Queue 10 / 11 void insert(T element); 12 /* 13 * Extract the current maximum element from the Queue (assuming a max heap). 14 * @return 15 */ 16 T extractMax(); 17} Listing 8: Interface for PriorityQueue. Commands

INSERT name marks: Insert the student in the tree. Student name and marks are give in the next line. Students name will be unique. 2. EXTRACTMAX: Extract the student with highest marks and print it. Extract operations also removes this from the max-heap. Sample input (ignore the line numbers):

1INSERT 2Diljeet Singh, 10 3INSERT 4Bhavesh Kumar, 100 5INSERT 6Dishant Kumar, 67 7EXTRACTMAX 8EXTRACTMAX 9EXTRACTMAX 10EXTRACTMAX Listing 9: Input for PriorityQueue. Expected Output (ignore the line numbers):

1Inserting: Diljeet Singh 2Inserting: Bhavesh Kumar 3Inserting: Dishant Kumar 4Student{name=’Bhavesh Kumar’, marks=100} 5Student{name=’Dishant Kumar’, marks=67} 6Student{name=’Diljeet Singh’, marks=10} 7Heap is empty. Listing 10: Output for PriorityQueue. 6 Project Management (Scheduler) [2 Marks]

In this part of the assignment you need to combine all the previous components of the assignment, Trie, Red-Black Tree and Priority Queue to implement a Job scheduler (Project management). The main part of this part are:

Project: The project class will be have a name, budget and priority (as shown in Listing 11).

1package ProjectManagement; 2public class Project { 3} Listing 11: Project class 2. User:

1package ProjectManagement; 2public class User implements Comparable { 3 @Override 4 public int compareTo(User user) { 5 return 0; 6 } 7} Listing 12: User class 3. Job:

1package ProjectManagement; 2public class Job implements Comparable { 3 @Override 4 public int compareTo(Job job) { 5 return 0; 6 } 7} Listing 13: Job class A job can have two status: REQUESTED, COMPLETED.

6.1 Specifications

The main component in this part of the assignment is a Job. As shown in Listing 13, each Job will belong to a Project and created by an User. The name of the Jobs will be unique (this is guaranteed in the test cases). All the jobs have a running time, i.e. the time required to run this job. The priority of a job is same as of that its project and a job can only be executed if its running time is less than the current budget of the Project. Successfully running a Job, will reduce the budget of that project by running time of the project.

All the projects will be stored in a Trie, using the project name as the key. Project names will be unique. All the Jobs will be stored in a Priority Queue, specifically a Max-Heap, using their priorities as the key.

6.2 Commands

A sample input file is shown in Listing 15.

USER: Create the user with given user name. 2. PROJECT: Create a project. NAME PRIORITY BUDGET 3. JOB: Create a job. NAME PROJECT USER RUNTIME 4. QUERY: Return the status of the Job queried. 5. ADD: Increase the budget of the project. PROJECT BUDGET 6. EMPTY_LINE: Let the scheduler execute a single JOB. 6.3 Scheduler specifications

The scheduler will execute a single job whenever it will encounter an empty line in the input specifications. After the end of the INP (input file) file, scheduler will continue to execute jobs till there are jobs left that can be executed.

Each time the scheduler wants to execute a job, it will do the following:

It selects the job with the highest priority from the MAX HEAP. 2. It first check the running time of the Job, say t. 3. It will then fetch the project from the RB-Tree and check its budget, say B. 4. If B ≥ t then it executes the job. Executing a job means: Set the status of the job to complete. Increase the global time by job time. Set the completed time of the job as the current global time. Decrease the budget of the project by run-time of the job. i.e. ˆB = B - t, where ˆB is the new budget of the project. 5. If: B < t, then select the next job from the max-heap (where jobs are stored) and try to execute this. 6. A scheduler will return in following cases: It successfully executed a single job. There are no jobs to be executed. None of the jobs can be executed because of the budget issue. 7. After the execution returns, process the next batch of commands (all the commands till next EMPTY_LINE or EOF). 8. If there are no more commands in the INP (input file) file, then let the scheduler execute jobs till there are no jobs left, or no jobs can be executed because of budget issues. This marks the END of the execution. 9. Print the stats of the current system. See Listing 16.

1package ProjectManagement; 2/** 3 * DO NOT MODIFY 4 / 5public interface SchedulerInterface { 6 /* 7 * @param cmd Handles Project creation. Input is the command from INP1 file in array format (use space to split it) 8 / 9 void handle_project(String[] cmd); 10 /* 11 * @param cmd Handles Job creation. Input is the command from INP1 file in array format (use space to split it) 12 / 13 void handle_job(String[] cmd); 14 /* 15 * @param name Handles user creation 16 / 17 void handle_user(String name); 18 /* 19 * Returns status of a job 20 * 21 * @param key 22 / 23 void handle_query(String key); 24 /* 25 * Next cycle, is executed whenever an empty line is found. 26 / 27 void handle_empty_line(); 28 /* 29 * Executed as a thread to server a job. 30 / 31 void schedule(); 32 /* 33 * Add budget to a project Input is the command from INP1 file in array format (use space to split it) 34 * 35 * @param cmd 36 / 37 void handle_add(String[] cmd); 38 /* 39 * If there are no lines in the input commands, but there are jobs which can be executed, let the system run till there are no jobs left (which can be run). 40 / 41 void run_to_completion(); 42 /* 43 * After execution is done, print the stats of teh system 44 */ 45 void print_stats(); 46} Listing 14: Interface specification

1USER Rob 2USER Harry 3USER Carry 4PROJECT IITD.CS.ML.ICML 10 15 5PROJECT IITD.CS.OS.ASPLOS 9 100 6PROJECT IITD.CS.TH.SODA 8 100 7JOB DeepLearning IITD.CS.ML.ICML Rob 10 8JOB ImageProcessing IITD.CS.ML.ICML Carry 10 9JOB Pipeline IITD.CS.OS.ASPLOS Harry 10 10JOB Kmeans IITD.CS.TH.SODA Carry 10 11 12QUERY Kmeans 13QUERY Doesnotexists 14 15JOB DeepLearningNoProject IITD.CS.ML.ICM Rob 10 16JOB DeepLearningNoUser IITD.CS.ML.ICML Rob2 10 17 18JOB DeepLearning1 IITD.CS.ML.ICML Rob 10 19JOB ImageProcessing1 IITD.CS.ML.ICML Carry 10 20JOB Pipeline1 IITD.CS.OS.ASPLOS Harry 10 21JOB Kmeans1 IITD.CS.TH.SODA Carry 10 22 23JOB DeepLearning2 IITD.CS.ML.ICML Rob 10 24JOB ImageProcessing2 IITD.CS.ML.ICML Carry 10 25JOB Pipeline2 IITD.CS.OS.ASPLOS Harry 10 26JOB Kmeans3 IITD.CS.TH.SODA Carry 10 27 28ADD IITD.CS.ML.ICML 60 29JOB DeepLearning3 IITD.CS.ML.ICML Rob 10 30JOB ImageProcessing3 IITD.CS.ML.ICML Carry 10 31JOB Pipeline3 IITD.CS.OS.ASPLOS Harry 10 32JOB Kmeans3 IITD.CS.TH.SODA Carry 10 33 34QUERY Kmeans 35 36JOB DeepLearning4 IITD.CS.ML.ICML Rob 10 37JOB ImageProcessing4 IITD.CS.ML.ICML Carry 10 38JOB Pipeline4 IITD.CS.OS.ASPLOS Harry 10 39JOB Kmeans4 IITD.CS.TH.SODA Carry 10 40 41JOB DeepLearning5 IITD.CS.ML.ICML Rob 10 42JOB ImageProcessing5 IITD.CS.ML.ICML Carry 10 43JOB Pipeline5 IITD.CS.OS.ASPLOS Harry 10 44JOB Kmeans5 IITD.CS.TH.SODA Carry 10 45 46QUERY Kmeans Listing 15: Input specification

1Creating user 2Creating user 3Creating user 4Creating project 5Creating project 6Creating project 7Creating job 8Creating job 9Creating job 10Creating job 11Running code 12Remaining jobs: 4 13Executing: DeepLearning from: IITD.CS.ML.ICML 14Project: IITD.CS.ML.ICML budget remaining: 5 15Execution cycle completed 16Querying 17Kmeans: NOT FINISHED 18Querying 19Doesnotexists: NO SUCH JOB 20Running code 21Remaining jobs: 3 22Executing: ImageProcessing from: IITD.CS.ML.ICML 23Un-sufficient budget. 24Executing: Pipeline from: IITD.CS.OS.ASPLOS 25Project: IITD.CS.OS.ASPLOS budget remaining: 90 26Execution cycle completed 27Creating job 28No such project exists. IITD.CS.ML.ICM 29Creating job 30No such user exists: Rob2 31Running code 32Remaining jobs: 1 33Executing: Kmeans from: IITD.CS.TH.SODA 34Project: IITD.CS.TH.SODA budget remaining: 90 35Execution cycle completed 36Creating job 37Creating job 38Creating job 39Creating job 40Running code 41Remaining jobs: 4 42Executing: DeepLearning1 from: IITD.CS.ML.ICML 43Un-sufficient budget. 44Executing: ImageProcessing1 from: IITD.CS.ML.ICML 45Un-sufficient budget. 46Executing: Pipeline1 from: IITD.CS.OS.ASPLOS 47Project: IITD.CS.OS.ASPLOS budget remaining: 80 48Execution cycle completed 49Creating job 50Creating job 51Creating job 52Creating job 53Running code 54Remaining jobs: 5 55Executing: DeepLearning2 from: IITD.CS.ML.ICML 56Un-sufficient budget. 57Executing: ImageProcessing2 from: IITD.CS.ML.ICML 58Un-sufficient budget. 59Executing: Pipeline2 from: IITD.CS.OS.ASPLOS 60Project: IITD.CS.OS.ASPLOS budget remaining: 70 61Execution cycle completed 62ADDING Budget 63Creating job 64Creating job 65Creating job 66Creating job 67Running code 68Remaining jobs: 11 69Executing: ImageProcessing from: IITD.CS.ML.ICML 70Project: IITD.CS.ML.ICML budget remaining: 55 71Execution cycle completed 72Querying 73Kmeans: COMPLETED 74Running code 75Remaining jobs: 10 76Executing: DeepLearning1 from: IITD.CS.ML.ICML 77Project: IITD.CS.ML.ICML budget remaining: 45 78Execution cycle completed 79Creating job 80Creating job 81Creating job 82Creating job 83Running code 84Remaining jobs: 13 85Executing: ImageProcessing1 from: IITD.CS.ML.ICML 86Project: IITD.CS.ML.ICML budget remaining: 35 87Execution cycle completed 88Creating job 89Creating job 90Creating job 91Creating job 92Running code 93Remaining jobs: 16 94Executing: DeepLearning2 from: IITD.CS.ML.ICML 95Project: IITD.CS.ML.ICML budget remaining: 25 96Execution cycle completed 97Querying 98Kmeans: COMPLETED 99Running code 100Remaining jobs: 15 101Executing: ImageProcessing2 from: IITD.CS.ML.ICML 102Project: IITD.CS.ML.ICML budget remaining: 15 103System execution completed 104Running code 105Remaining jobs: 14 106Executing: DeepLearning3 from: IITD.CS.ML.ICML 107Project: IITD.CS.ML.ICML budget remaining: 5 108System execution completed 109Running code 110Remaining jobs: 13 111Executing: ImageProcessing3 from: IITD.CS.ML.ICML 112Un-sufficient budget. 113Executing: DeepLearning4 from: IITD.CS.ML.ICML 114Un-sufficient budget. 115Executing: ImageProcessing4 from: IITD.CS.ML.ICML 116Un-sufficient budget. 117Executing: DeepLearning5 from: IITD.CS.ML.ICML 118Un-sufficient budget. 119Executing: ImageProcessing5 from: IITD.CS.ML.ICML 120Un-sufficient budget. 121Executing: Pipeline3 from: IITD.CS.OS.ASPLOS 122Project: IITD.CS.OS.ASPLOS budget remaining: 60 123System execution completed 124Running code 125Remaining jobs: 7 126Executing: Pipeline4 from: IITD.CS.OS.ASPLOS 127Project: IITD.CS.OS.ASPLOS budget remaining: 50 128System execution completed 129Running code 130Remaining jobs: 6 131Executing: Pipeline5 from: IITD.CS.OS.ASPLOS 132Project: IITD.CS.OS.ASPLOS budget remaining: 40 133System execution completed 134Running code 135Remaining jobs: 5 136Executing: Kmeans1 from: IITD.CS.TH.SODA 137Project: IITD.CS.TH.SODA budget remaining: 80 138System execution completed 139Running code 140Remaining jobs: 4 141Executing: Kmeans3 from: IITD.CS.TH.SODA 142Project: IITD.CS.TH.SODA budget remaining: 70 143System execution completed 144Running code 145Remaining jobs: 3 146Executing: Kmeans3 from: IITD.CS.TH.SODA 147Project: IITD.CS.TH.SODA budget remaining: 60 148System execution completed 149Running code 150Remaining jobs: 2 151Executing: Kmeans4 from: IITD.CS.TH.SODA 152Project: IITD.CS.TH.SODA budget remaining: 50 153System execution completed 154Running code 155Remaining jobs: 1 156Executing: Kmeans5 from: IITD.CS.TH.SODA 157Project: IITD.CS.TH.SODA budget remaining: 40 158System execution completed 159--------------STATS--------------- 160Total jobs done: 19 161Job{user=’Rob’, project=’IITD.CS.ML.ICML’, jobstatus=COMPLETED, execution_time=10, end_time=10, name=’DeepLearning’} 162Job{user=’Harry’, project=’IITD.CS.OS.ASPLOS’, jobstatus=COMPLETED, execution_time=10, end_time=20, name=’Pipeline’} 163Job{user=’Carry’, project=’IITD.CS.TH.SODA’, jobstatus=COMPLETED, execution_time=10, end_time=30, name=’Kmeans’} 164Job{user=’Harry’, project=’IITD.CS.OS.ASPLOS’, jobstatus=COMPLETED, execution_time=10, end_time=40, name=’Pipeline1’} 165Job{user=’Harry’, project=’IITD.CS.OS.ASPLOS’, jobstatus=COMPLETED, execution_time=10, end_time=50, name=’Pipeline2’} 166Job{user=’Carry’, project=’IITD.CS.ML.ICML’, jobstatus=COMPLETED, execution_time=10, end_time=60, name=’ImageProcessing’} 167Job{user=’Rob’, project=’IITD.CS.ML.ICML’, jobstatus=COMPLETED, execution_time=10, end_time=70, name=’DeepLearning1’} 168Job{user=’Carry’, project=’IITD.CS.ML.ICML’, jobstatus=COMPLETED, execution_time=10, end_time=80, name=’ImageProcessing1’} 169Job{user=’Rob’, project=’IITD.CS.ML.ICML’, jobstatus=COMPLETED, execution_time=10, end_time=90, name=’DeepLearning2’} 170Job{user=’Carry’, project=’IITD.CS.ML.ICML’, jobstatus=COMPLETED, execution_time=10, end_time=100, name=’ImageProcessing2’} 171Job{user=’Rob’, project=’IITD.CS.ML.ICML’, jobstatus=COMPLETED, execution_time=10, end_time=110, name=’DeepLearning3’} 172Job{user=’Harry’, project=’IITD.CS.OS.ASPLOS’, jobstatus=COMPLETED, execution_time=10, end_time=120, name=’Pipeline3’} 173Job{user=’Harry’, project=’IITD.CS.OS.ASPLOS’, jobstatus=COMPLETED, execution_time=10, end_time=130, name=’Pipeline4’} 174Job{user=’Harry’, project=’IITD.CS.OS.ASPLOS’, jobstatus=COMPLETED, execution_time=10, end_time=140, name=’Pipeline5’} 175Job{user=’Carry’, project=’IITD.CS.TH.SODA’, jobstatus=COMPLETED, execution_time=10, end_time=150, name=’Kmeans1’} 176Job{user=’Carry’, project=’IITD.CS.TH.SODA’, jobstatus=COMPLETED, execution_time=10, end_time=160, name=’Kmeans3’} 177Job{user=’Carry’, project=’IITD.CS.TH.SODA’, jobstatus=COMPLETED, execution_time=10, end_time=170, name=’Kmeans3’} 178Job{user=’Carry’, project=’IITD.CS.TH.SODA’, jobstatus=COMPLETED, execution_time=10, end_time=180, name=’Kmeans4’} 179Job{user=’Carry’, project=’IITD.CS.TH.SODA’, jobstatus=COMPLETED, execution_time=10, end_time=190, name=’Kmeans5’} 180------------------------ 181Unfinished jobs: 182Job{user=’Carry’, project=’IITD.CS.ML.ICML’, jobstatus=REQUESTED, execution_time=10, end_time=null, name=’ImageProcessing3’} 183Job{user=’Rob’, project=’IITD.CS.ML.ICML’, jobstatus=REQUESTED, execution_time=10, end_time=null, name=’DeepLearning4’} 184Job{user=’Carry’, project=’IITD.CS.ML.ICML’, jobstatus=REQUESTED, execution_time=10, end_time=null, name=’ImageProcessing4’} 185Job{user=’Rob’, project=’IITD.CS.ML.ICML’, jobstatus=REQUESTED, execution_time=10, end_time=null, name=’DeepLearning5’} 186Job{user=’Carry’, project=’IITD.CS.ML.ICML’, jobstatus=REQUESTED, execution_time=10, end_time=null, name=’ImageProcessing5’} 187Total unfinished jobs: 5 188--------------STATS DONE--------------- Listing 16: Output for INP in Listing 15 7 Submission instructions

As always compress src directory to zip format and rename the zip file in the format entrynumber_assignment4.zip. For example, if your entry number is 2012CSZ8019, the zip file should be named 2012CSZ8019_assignment4.zip. Then you need to convert this zip file to base64 format as follows and submit the .b64 file on Moodle.

base64 entrynumber_assignment4.zip > entrynumber_assignment4.zip.b64 Folder structure: Inside the src directory, you need to have a README.pdf (case sensitive) and your solution (exactly following the folder structure that of the code provided.). Please do not rename the existing directories. You need to report the time complexities of various operations for both the implementations. You should also report any interesting findings based on your experiments with the two implementations.

Grading: While grading we will replace the driver code and the interface code with the original files before the compilation. So please ensure that your code compiles and run correctly with the original driver and interface files.

MOSS: Please note that we will run MOSS on the submitted code. Anyone found with a copied code, either from Internet or from another student, will be dealt as per the class policy.

8 FAQ

See some fixes here: 1 Project Management: In what data-structure projects are stored? Ans: Trie Trie: Match: match the search term with pre-fix of entries. Lists and its subclasses (ArrayList, LinkedList) etc. are allowed. Maps (e.g. HashMap) are also allowed. You need to override the toString() method in classes to print in a particular format. Printing order in Trie: Lexicographical order. DO NOT print spaces (which is present in the name). You need to store spaces in the Trie, otherwise MATCH command will print first-name and second-name together(without a space) and it will not match the output. Trie: Names can contain any character whose ASCII code is between 32-126, see an ASCII table here: [1]. Trie: If a particular entry is not found, print NOT FOUND. Build issues: Please use the Makefile provided. Only List, Stack, Queue and Maps arze allowed to be imported. There are some encoding issue in file compare. We are working on it. Extract-Max in Priority Queue should follow FIFO (if the priority of two objects is same). Casting from and to Object is allowed. Please adhere to return types of the function. It will be used in the driver code. You can use Iterator. Print: Trie. Last level is empty, which represents the end of the Trie. Question: Adding budget to a project, what to do with its unfinished (but already tried) jobs? Answer: https://piazza.com/class/jyic9aa2xyb34g?cid=649 Project insertion and retrieval doubt: We are inserting project in a trie and retrieving from a RB tree, how? Answer:When a new Project is created, it is stored in a Trie. RB-Tree is used as a NOT_READY queue. To store the jobs which cannot be executed because there is not enough budget left. As mentioned in the RB-Tree implementation, using a single key we can store multiple objects. Files NOT to be edited: Please make no changes to the Driver code for the Trie, RedBlack and PriorityQueue. And please do not change any of the interface files. Size of Max-heap: Upper bound on the size of the heap: 10000. You can use lists. Project management, empty_line, run_to_completion: "1. How is schedule() different from handle_empty_line()?"

handle_empty_line is there so do dome pre-processing before calling schedule.
If you feel like this is not required, use this:

public void handle_empty_line() {
schedule();
}

"2. What is the use of run()? What is schedule() doing inside that?
If it is for completing the pending jobs at the end, then why
run_to_completion()?"

The driver uses a thread to execute the jobs. schedule() contains
the logic to check the budget, then either execute the code or move
it to a NON_READY queue.
As can be seen from the driver code, run_to_completion() is used
when we are done processing the INPUT FILE (i.e. no more
commands are left to process). What to return in RBTree when key is not found? A RedBlackNode with NULL key and NULL values. If a key has multiple values associates with it, then the output of search query for that key should have values printed in lexicographic order or FIFO. Priority order: FIFO order comes after priority. If there are two jobs with a different priority, then you take the job which has the higher priority, irrespective of who came first. FIFO has to be maintained only if their priorities are same. References :

[1] Ascii table - ascii character codes and html, octal, hex and decimal chart conversion. http://www.asciitable.com/. (Accessed on 09/15/2019).

[2] Painting nodes black with red-black trees - basecs - medium. https://medium.com/basecs/painting-nodes-black-with-red-black-trees-60eacb2be9a5. (Accessed on 09/10/2019).

[3] Trie — (insert and search) - geeksforgeeks. https://www.geeksforgeeks.org/trie-insert-and-search/. (Accessed on 09/12/2019).