Description
CmpE 250 Project 1 – Factory
1 Introduction
In Rumeli Hisarüstü, a factory called 1-A Factory produces essential products. Every product has their respective value. In the factory, individual units called holders are responsible for handling the products in the factory line. Each holder is coupled with the previous and the next holder to create a product line. You are tasked with the organization of this product line.
2 Details
You will be given two classes Holder, and Product; and an interface, Factory. You need to write two new classes FactoryImpl, and Project1.
2.1 FactoryImpl • This class should implement the Factory interface. The overridden methods should work the way they are described in the Javadoc. • This class has three mandatory fields. These fields should be correctly modified inside the overriden methods. private Holder f i r s t private Holder l a s t private I n t e g e r s i z e • You are free to add helper methods.
2.2 Project1 • The main method should be implemented here. This class is the entry point of your program. • You are required to read from the input file and write to the output file. These file paths will be given in the program arguments. • Each input command will be given in a single line. You have to read the input file and write to the output file line by line. 1
3 Input & Output
3.1 Input • Add First – Adds a new product at the beginning of the factory line. AF productid productvalue • Add Last – Adds a new product to the end of the factory line. AL productid productvalue • Add – Adds a new product to the given index of the factory line. Prints “Index out of bounds.” if the index is out of bounds. A index productid productvalue • Remove First – Removes the first product from the factory line and prints it. Prints “Factory is empty.” if the there is no product in the factory. RF • Remove Last – Removes the last product from the factory line and prints it. Prints “Factory is empty.” if the there is no product in the factory. RL
• Remove Index – Removes the product in the given index and prints it. Prints “Index out of bounds.” if the index is out of bounds. RI index • Remove Product – Removes the first occurrence of the product with the given value and prints it. Prints “Product not found.” if the product is not in the factory line. RI productvalue • Find – Prints the product with the given productid. Prints “Product not found.” if the product is not in the factory line. F productid • Get – Prints the product in the given index. Prints “Index out of bounds.” if the index is out of bounds. G index
• Update – Updates the value of the product with the given productid to productvalue. Prints “Product not found.” if the product is not in the factory line. U productid productvalue 2 • Filter Duplicates – Removes products such that after the filtering process there is only a single occurrence of each product in the factory line. In the context of this method, duplicate products are products with equal value fields, the id fields are of course unique. FD • Reverse – Reverses the factory line. R • Print – Prints the factory line. P Input file path will be given as the first program argument.
3.2 Output • Product – Products will be printed in the format below. ( productid, productvalue ) • Factory Line – Factory line will be printed in the format below. { product1, product2, . . . , productn } Output file path will be given as the second program argument.
4 Submission Your project will be graded automatically. So it’s important that you carefully follow the submission instructions. First, all 5 of your source files, and nothing more, should be collected under Project1/src. Then, you should zip the Project1 folder and rename it to p1_.zip (e.g., p1_2020400999.zip). This zip file will be submitted through moodle.
Your program must be runnable through the terminal. We will compile your code with the javac command. The target version is 17. Hence, it is imperative that your project structure is correct, otherwise you will not be able to get any points from the automatic grading system. The compiled program will be run using java command. Your program should be able to run with full-path arguments. 5 Grading Grading of this project is based on the automatic compilation and run and the success of your code in test cases. If your code compiles and runs with no error, then you will get 10% of the project grade. 40% of the grade will come from unit tests. We will test each method implementation for the methods in the Factory interface. Each method implementation will have equal weight. The rest of your grade will be the sum of collected points from each test case.
Each test case will have equal weight. Maximum project grade is 100%. 3 Input Corresponding Output Line Explanation P {} Initially the factory line is empty. RF Factory is empty. Cannot remove from the front since the factory is empty. RL Factory is empty. Same as above, but now it’s the end. AF 3 9 (3,9) is added to the front. A 0 2 4 (2,4) is inserted to index 0. AL 5 25 (5,25) is added to the end. A 0 1 1 (1,1) is inserted to index 0. A 3 4 16 (4,16) is inserted to index 3. AL 6 36 (6,36) is added to the end. AF 7 30 (7,30) is added to the front. P {(7, 30),(1, 1),(2, 4),(3, 9), (4, 16),(5, 25),(6, 36)} Factory line is printed. F 3 (3, 9) Product with id 3 is found and printed. F 20 Product not found. Product with id 20 does not exist. U 4 9 (4, 16) value of the product with id 4 is updated to 9. The previous product is printed. U 13 21 Product not found. Product with id 13 does not exist. G 0 (7, 30) Product with index 0 is printed. G 17 Index out of bounds. The factory line has 7 products so index 17 is out of bounds. U 1 36 (1, 1) value of the product with id 1 is updated to 36.
The previous product is printed. A 21 21 21 Index out of bounds. There is no product at index 21. FD 2 All duplicates are removed from the factory line. In this case it was (4,9) and (6,36). Prints the number of duplicates removed. P {(7, 30),(1, 36),(2, 4), (3, 9),(5, 25)} Prints the factory line. R {(5, 25),(3, 9),(2, 4), (1, 36),(7, 30)} Reverses the factory line. Prints the new version. RP 9 (3, 9) Removes the first product with value 9. RP 13 Product not found. No product has value 13. RL (7, 30) Removes and prints the last product. RI 2 (1, 36) Removes and prints the product at index 2. RF (5, 25) Removes and prints the first product. RI 4 Index out of bounds.
The factory line has a single product so index 4 is out of bounds. Table 1: Line by line analysis of example input 6 Warnings • All source codes are checked automatically for similarity with other submissions and exercises from previous years. Make sure you write and submit your own code. Any sign of cheating will be penalized by at least -50 points at first attempt and F grade in case of recurrence.
• Make sure you document your code with necessary inline comments and use meaningful variable names. Do not over-comment, or make your variable names unnecessarily long. This is very important for 4 partial grading. • Do not make changes in Holder.java, Product.java, and Factory.java. • Do not add any files to the source code except Holder.java, Product.java, Factory.java, FactoryImpl.java, and Project1.java.
• Make sure that each method in the Factory interface does the operations it is supposed to do. These methods will be individually unit tested. For example, if there is only one product in the factory and either RF or RL is called, then both first and last fields should be set to null. So basically the three mandatory fields should always be correctly set. • Make sure that the white-spaces in your output is correct. You can disregard the ones at the end of the line. 5
CmpE 250 Project 2 – Internet
1 Introduction
Have you ever wondered how the Internet works? The implementation of the internet is quite similar to a postal service. When you try to send a package from BOUN to METU, firstly you go to the post office in Hisarüstü, then, they send their package to gathering center in Levent and then to the gathering center of Istanbul. From there, the package is sent to the gathering center in Ankara, Çankaya, METU, and then to the receiver.
The Internet works with the exact same principals, where specialized computers named routers act like the postal service. When you send a Whatsapp message, the message first goes to your modem, which is a router, then to the router responsible for your neighbourhood, district, city, country in order. There is a different structure in international space but notice that, up to the country node, with different cities, districts, and neighbourhoods the topology is a tree topology! One question comes to mind is that, how does the addressing work in the internet. You probably heard about the IP addressing. IP address uniquely identifies each device(Node) connected to a network. Overall, network looks like this with addresses:
2 Objective
Your objective in this project is modelling this networking structure using different data structures: BST and AVL tree. We will be giving you details about the nodes, then your model should: • Add and delete nodes. 1 • Send a message between nodes, tracing the path the message took. • Re-balance the tree as the number of nodes increase. • Keep the logs of the operation. You can safely assume that input files will be set up so that each IP will be unique. In the end, you will be given a huge input file to observe the speed difference between BST and AVL.
2.1 Model details Each node is uniquely identified by an IP address. For illustration valid IP addresses are used but assume any string can be used as an address(you can name your nodes like: Özlem, Ece, Barış, etc). These addresses shall be compared using compareTo(String s) function of a string object. As the operations happen and messages pass between nodes, each node prints a log message containing details about the operation to a output file. You can find the log string definitions bellow.
3 Functionality and Input File
Each input file has a single IP address in the starting line, this IP is the IP of the initial root. The lines bellow that contain instructions your model should handle.
3.1 Add a new Node Instruction: ADDNODE During addition of a new node, its place is found using binary search. All the nodes on the path from root node to parent node of the newly added node shall add the event to their log messages, and others should not change their log files. Log message structure for adding a new node is: : New Node being added:
3.2 Delete a node Instruction: DELETE When a node is deleted, there are 2 cases: The node is a leaf node and deleted immediately or the node is not a leaf node and upon deletion, a leaf node takes its place. For this project, you are expected to use the smallest node from right subtree to replace the deleted node. In terms of logging, logging of the delete operation is performed by the parent node of the deleted node. For the 2 cases, there are 2 possible log lines: • When a leaf node is deleted, its parent logs: : Leaf Node Deleted: • When a non-leaf node is deleted: : Non-Leaf Node deleted; removed: replaced: Notice that only the parent of actually deleted node’s parent performs a logging operation, so when you swap the intermediate node with a leaf node to remove the leaf node, the parent of the leaf node should not log anything. 2
3.3 Send Message Instruction: SEND Tree is a connected graph, meaning there is a path between each node in the topology, so it is possible to send a message between each node. However, a node can transmit a message only to its child nodes or the parent node. Thus, to arrive to the receiver, the message must jump between nodes. These message hops are logged in the nodes as: : Transmission from: receiver: sender: For example, consider the tree structure from the introduction. A message sent from 172.46.7.10 to 172.200.56.78 follows the following path: 172.46.7.10 −→ 172.50.4.70 −→ 172.100.0.1 −→ 172.200.56.78 This transmission is logged in 3 different ways in different type of nodes: • Sender(172.46.7.10): : Sending message to: 172.200.56.78 • Receiver(172.200.56.78): : Received message from: 172.46.7.10 • Intermediate node(172.100.0.1): : Transmission from:172.50.4.70 receiver: 172.200.56.78 sender: 172.46.7.10 One another thing to keep in mind is that, we want you to commute the message in the shortest path, so a message should not go over the same node 2 times. (Pro tip: throw an exception when this happens for easy debugging)
3.4 Re-Balancing Balance functionality will not be provided as instructions in the input file. Instead, your AVL tree needs to rebalance itself as the new nodes are added and some nodes are deleted. Your AVL tree should never be in a unbalanced situation. As you know, there are 2 types of rebalancing in AVL trees, single rotation and double rotation. These are just reorganization of pointers in short. When the rotations happen, all nodes involved in the rotation, 2 nodes in single rotation case and 3 nodes in double rotation case, will log the rotation type as: Rebalancing Note: Check for balance deficiencies in a bottom-up manner. On the case of BST tree, this functionality won’t be used so nothing will be logged since there is no rebalancing.
4 Input File
Your program shall take the input file as the first system argument. The input file structure and an example input file is in the following: Instruction 1 Instruction 2 … For more, refer to the input files provided with the description. 3 5 Output File Your second system argument will specify an output file, assume it is output.txt for illustration. Your file shall create 2 files, output_AVL.txt and output_BST.txt and each tree shall log to their respective output file. You will be provided with example input files and their expected output files.
6 Submission
You will be submitting a zip file containing your code via Moodle. We will be running your code via followind commands: javac Main.java java Main You will be delivered a huge file containing millions of instructions. In the last part of submission, you will switch on and off AVL property, then observe the time difference between AVL tree and BST tree.
You can measure the time your code took via running: time java Main
CmpE 250 Project 3 – Encore Airlines
1 Introduction
Aviation makes the dream and desire of being able to fly a reality. A strong and affordable global air transport network transcends continents, greatly expands local access to foreign supplies and markets, provides invaluable opportunities for cultural and social exchange, and enhances emergency and humanitarian response capabilities during crises and public health emergencies.
All these opportunities and many more depend on the flawless execution of our flight operations. Air traffic management is a cooperative, international effort and does not stop at borders, on land or in the air. International cooperation of air traffic control providers has helped make commercial aircraft one of the most rapid and dependable mode of travel. Flight operations staff work around the clock to ensure the smooth running of these services. In this project, you will explore these flight operations services’ event-driven flight scheduling and processing routines.
2 Details
In this project you will simulate an air traffic management system. This system has area control centers, air traffic controllers, airports and flights. Area control centers are where flights enter and exit the simulation. Each area control center has a set of airports its’ responsible for and each airport has one air traffic controller. These air traffic controllers are what the area control center will communicate with when processing flight events. Your job is to make sure that each flight is handled correctly.
2.1 ACC • Area control center, or ACC, is the entry and exit point for flights. • Area control centers are identified by a unique code consisting of 4 capital letters. • Each area control center is responsible for a set of airports. Every airport has one and only one air traffic controller. This air traffic controller communicates with the area control center. The area control center will delegate the departure and landing phases of the flight to the air traffic controller. Control will be given back to the area control center when these phases are done.
• There might be more than one area control center. These area control centers are completely independent. They have their own flights, their own airports, and their own air traffic 1 controllers for those airports. In other words, a flight or an airport or an air traffic controller can only be a part of one area control center. • Every airport in an area control center is connected to every other airport in that area control center. • Flights can only fly between airports in the same area control center. Passages between area control centers do not happen.
• Flights need to have some operations done by the area control center to progress forward. At any given time there might be more than one flight that needs their operation done. These flights will form a queue while the area control center is busy. This queue is called the ready queue, because it holds flights that are ready to be processed by the area control center. Area control centers are almost always really busy, but each flight should also have a good response time to ensure the smooth running of flight operations.
To this end, the area control center will process the first flight in the ready queue, however, this flight will only be processed for some predetermined time-slice. If the operations do not finish in the given time-slice, the flight is sent all the way to the back of the queue for further processing; else, if the operations finish the flight continues on with its’ next step. There might be cases where two flights want to enter the ready queue at the same time.
In such a case, if one of the flights is new to the queue and the other one just finished processing and got sent to the back of the queue, the new one has priority. If the both flights are new, then the flight with the lower flight code, by string comparison, has higher priority. Area control centers in this air traffic management system use a time-slice of 30 units of time. The chart below visualizes this time-slice processing regime. Flight entries are flight codes followed by the amount of time needed to finish that flight. 0 F1: 40t F2: 20t F3: 30t F1 F2 F1 F3 . . . 30t 50t 60t 90t time t Flight entry
2.2 ATC • Air traffic control, or ATC, is an auxiliary flight manager. • Each air traffic control is responsible for a single airport. • Flights taking off from or landing at an airport need their operations done by the air traffic controller for that airport. So, when time comes, the area control center will delegate flights to the required air traffic controller. When the take off or land operations end, the air traffic controller will control of the pass the flight back to the area control center.
• At any given time air traffic control might have more than one flight that needs their operation done, just like the area control center. These flights will again form a queue called the ready queue. Air traffic controllers are also very busy, however, unlike the area control center, air traffic control must commit to one flight when it starts processing it. So the first flight in the queue will be processed first, and it will be processed until the completion of its’ operations.
• Air traffic controllers are identified by a unique code consisting of 7 characters, the first 4 characters of which is the area control center code it belongs to, the following 3 characters 2 are numbers from 0 to 999, filled with zeros from the front. These numbers are obtained by placing the airport code of this air traffic control into an available slot in a table of size 1000. Every area control center will have its’ own table, filled with airports it is responsible for. For every ith character of the airport code string, i starting from zero of course, the ASCII value for that character will be multiplied by 31i . These i multiplications will be summed together to generate the initial slot value.
Search for an available slot will start from the position denoted by the last three digits of the initial slot value. If a slot is not available, the next slot will be considered. If the end of the table is reached jump back to the beginning slot of the table and continue. There will not be more than 1000 airports in one area control center, and consequently in one table, so every airport will eventually find a slot. Air traffic control codes are generated in the order their respective airport code appears in the input.
2.3 Flight • Flights are the entities that needs processing. • Each flight has a departure and landing airport, both airports belong to the same area control center. Which area control center these airports belong to will be given in the input. • A flight has 21 operation steps to complete before termination. These steps and their order are explained in detail in the next section. Durations of these steps will be given in the input. • Flights enter and exit the simulation through the area control center. In the area control center flights process their operation steps until termination.
These processing steps repeat a certain form. This form can be visualized as a collection of states the flight can be in. A state diagram is given below to help you visualize the situation. • During processing the flight event will cycle through the states. Twice during these cycles, the flight will exit states that belong to the area control center and enter states that belong to an air traffic control, where it will process either the departure or the landing operation steps of the flight.
After the air traffic control has cycled through its’ states, the flight will be back in the area control center states, and it will continue processing from there. ACC ATC New Terminated Running 1 Waiting 1 Ready 1 Ready 2 Waiting 2 Running 2 admitted exit time-slice expired process operations wait completion wait event landing/departure event landing/departure completion wait event process operations wait completion 3
2.4 Operation Times Every flight will follow a certain chain of states. Each state needs some amount of time to complete its’ operation. These state chains are given below, in order. Operation times will be given for each running and waiting state in the input. The completion of running states depend on the availability of either the area control center or the air traffic control responsible for the execution. So, time spent in the ready states depends on the scheduling situation.
Waiting states just require the flight to wait for a certain amount of time before continuing with the next operation. ACC – Running: ACC initial processing. ACC – Waiting: Relaying flight information to ACC. ACC – Running: Control transfer from ACC to departure ATC. ATC Departure – Running: Departure ATC initial processing. ATC Departure – Waiting: Boarding wait. ATC Departure – Running: Taxi information processing. ATC Departure – Waiting: Taxi wait. ATC Departure – Running: Takeoff clearance processing. ATC Departure – Waiting: Takeoff wait. ATC Departure – Running: Control transfer from departure ATC to ACC. ACC – Running: Flight path processing. ACC – Waiting: Flight wait. ACC – Running: Control transfer from ACC to arrival ATC. ATC Arrival – Running: ATC initial processing and landing clearance processing. ATC Arrival – Waiting: Landing wait. ATC Arrival – Running: Taxi information processing. ATC Arrival – Waiting: Taxi wait. ATC Arrival – Running: Gate and ground crew information processing. ATC Arrival – Waiting: Disembarkation wait. ATC Arrival – Running: Control transfer from arrival ATC to ACC. ACC – Running: ACC wrap-up.
3 Input & Output
3.1 Input Input file path will be given as the first program argument. Format Input begins with a single line containing two space-separated integers A and F. Then, A lines follow, the ith of which contains space-separated codes starting with Ai the ACC code, followed by airport codes connected to that ACC, jth of which is Hij .
Then, F lines follow, the kth of which contains 26 space-separated values, Tk admission time, Fk the flight code, Ak ACC code, Ok departure airport code, Dk arrival airport code, respectively. Followed by 21 space-separated integers, denoting the operation times for the flight Fk, mth of these operation times is Pkm. 4 Constraints 1 ≤ A, i ≤ 104 1 ≤ F, k ≤ 6 · 106 0 ≤ Tk ≤ 109 2 ≤ j ≤ 1000 1 ≤ m ≤ 21 1 ≤ Pkm ≤ 500 Ai , Ak ∈ [“AAAA”-“ZZZZ”] Ok, Dk, Hij ∈ [“AAA”-“ZZZ”] Fk ∈ [“AA1111”-“ZZ9999”] 3.2 Output Output file path will be given as the second program argument.
Format The output will consist of A lines, one for each ACC. Ordering between ACC lines does not matter. Each ACC line has an ACC code followed by a space-separated integer denoting the time of termination of the last flight. The next j space-separated strings are airport codes and their slot concatenated together. These values are for each ACC.
4 Submission
Your project will be graded automatically. So it’s important that you carefully follow the submission instructions. First, all of your source files, and nothing more, should be collected under Project3/src. Then, you should zip the Project3 folder and rename it to p3_.zip (e.g., p3_2020400999.zip). This zip file will be submitted through moodle. These steps should be followed in order. Your program must be runnable through the terminal. We will compile your code with the javac command. The target version is 17.
Hence, it is imperative that your project structure is correct, otherwise you will not be able to get any points from the automatic grading system. The compiled program will be run using java command. Your program should be able to run with full-path arguments.
5 Grading Grading of this project is based on the automatic compilation and run and the success of your code in test cases. If your code compiles and runs with no error, then you will get 10% of the project grade. 90% of your grade will be the sum of points collected from each input/output test case. Each test case will have equal weight. Outputs will have partial grading, each correct ACC line will contribute towards your final grade. Wrong values do not reduce your grade. Maximum project grade is 100%.
6 Warnings • This is an individual project. • All source codes are checked automatically for similarity with other submissions and exercises from previous years. Make sure you write and submit your own code. Any sign of cheating will be penalized by at least -50 points at first attempt and F grade in case of recurrence. 5 • Make sure you document your code with necessary inline comments and use meaningful variable names. Do not over-comment, or make your variable names unnecessarily long. This is very important for partial grading.
• Do not start coding right away. Think about the structure of your program and the possible complications resulting from it before coding. • Make sure that the white-spaces in your output is correct. You can disregard the ones at the end of the line.
• Questions about the project should be sent through the contact address in the first page. • There will be a time limit of 60 seconds for your program execution. This is not a strict time limit, execution times may vary for each run, thus objections regarding to time limits will considered if necessary. 6
CmpE 250 Project 4 – Marathon
1 Introduction
A philosopher once said, “Some flowers… Some flowers don’t grow in some soils. Such is life.” A few days ago, I received such an e-mail from rambo.ocon@boun.edu.tr. He wrote in that e-mail, “As a traveling race man, I could not do anything when it came to coding. I’m not good enough to code and need help from cmpe250 students.”
So he asked me to create this project for you to help him. And now it’s time to help him! Esteban Ocon, a famous Formula 1 pilot, also known as Rambo Ocon, decides to participate in the 43rd Istanbul marathon, even though he has no previous running experience. Since he has a competitive personality, he wants to finish the race in first place.
So he decides to cheat and complete the course in the shortest way possible. In the meantime, he sees that at some points on the path, the opposing team’s flags fly around. He wants to take down all these flags before the race starts. Because he doesn’t want to get tired before the race, he wants to do it in the shortest possible way.
Also, this will mean that the chances of him getting caught by the police will decrease; hence he will make it to the race. Before the race, Rambo Ocon takes the map of Istanbul in front of him, marks the points where the flags are, and starts calculating the shortest route. Since there are many streets in Istanbul, and he is bad at math, he cannot calculate it. Besides, he doesn’t know how to code, which is the icing on the cake. It’s time to help Rambo! 1
2 Clarification
Let’s say the race starts from Samandıra Tesisleri and finishes at Şükrü Saraçoğlu stadium. The flags are at 1st Istanbul Bridge and 2nd Istanbul Bridge. Before the race, he must cut all the flags using the shortest possible path. There are no restrictions on the order in which he cuts the flags. He can start from the 1st Bridge, then go to the 2nd Bridge, or vice versa.
Thanks to public transportation, he can travel the same exact path as many times as he wants after traveling a path between two flags once, without getting tired. (More detailed explanation is given with the graphs in the More Examples section.) During the race, he has to start from Samandıra Tesisleri and finish at Şükrü Saraçoğlu by running the shortest route. • He has to cut all the flags, starting from any point with a flag. • He can cut the flags in any order that will lead to the minimum distance path. • There can be many different paths between any two flags.
• He can travel using the same point more than once. However, if he uses the same exact path between two flags, he can travel with public transportation (at no cost). • Exact route: Let’s say s1 and s4 contain flags. If Rambo Ocon uses the s1-s2-s3-s4 path without passing through any other points, then he can travel this same path with no cost (s1-s2-s3-s4 and s4-s3-s2-s1). • He can use both directions of all point connections (e.g., graph is undirected).
3 Input & Output
3.1 Input • The first line represents (V) the number of points in Istanbul (e.g., the number of all the nodes in the graph). 0 ≤ Ei ≤ 100 where Ei is the number of edge count for Vi . • The second line represents the total number of flags (M). 2 ≤ V ∗ M ≤ 5.106 and 2 ≤ V ≤ 5.106 • The third line represents the name of the starting and ending points, respectively. • The fourth line represents the name of the points where the flags are located. • Each next line will give the name of a point in Istanbul and the names and lengths of the points that can be reached from that point in pairs.
For example: 2 There are ways from s1 point to s2, s3, and s4 points of length 1, 2, and 3, respectively. Then input line will be s1 s2 1 s3 2 s4 3 If there is no way from s2, input line for s2 will be s2 Input Explanation 9 The race path has 9 points. 2 There are 2 flags in the path. s0 s8 The race will start from s0 point and end at s8 point. s3 s4 The flags are located at s3 and s4 s0 s1 4 s2 3 The point with ID s0 has a way to s1 and s2 with length of 4 and 3 respectively.
This also means that s1 has a way to s0 with length of 4. s1 s2 1 s3 7 s2 s3 6 s4 7 s3 s6 5 s5 17 s4 s6 4 s5 s6 5 s8 8 s6 s7 11 s7 s8 3 s8 Table 1: Sample Input with Explanations s0 s1 s2 s3 s4 s5 s6 s7 s8 3 4 1 7 7 6 5 17 4 5 8 11 3 3 3.2 Output • An integer, the length of the path during the race day. (If finishing the race is not possible, then there must be something wrong with the map so print -1.) • An integer, the length of the path to cut the flags. (If cutting all the flags is not possible, then there must be something wrong with the map so print -1.)
Output Explanation 27 The length (cost) of the path that Rambo used during the race. (s0 → s2 → s4 → s6 → s5 → s8) 9 The length of the path that Rambo used to cut the flags. (s3 → s6 → s4) Table 2: Expected Output File 4 Submission Your code will be graded automatically. Therefore, it’s important that you follow the submission instructions. This is your fourth project, so it is assumed that you are able to follow these instructions. First, all of your source files should be collected under Project4/src. Then, you should zip the Project4 folder and rename it to .zip. This zip file will be submitted through moodle. Name of your main class must be project4.java.
Your program will be compiled with the command below: javac -target 17 Project4/src/*.java -d ./ The input and output files can be in any folder. Design your code to accept the full path for file arguments. Your program will be run with the command below: java project4 Make sure your final submission compiles and runs with these commands.
4 5 Grading Grading of this project is based on the automatic compilation, run, and the success of your code in test cases. If your code compiles and runs with no error, then you will get 10/100 of the project grade. The rest of your grade will be the sum of collected points from each test case. You can also get partial credit for each input. If you find the length of the path Rambo used during the race, you will get %30 from that test case and %70 if you find the other length. The maximum grade for this project is 100. The 20 point worth of test case will be for checking the complexity value of your code with large input sizes.
6 Warnings 1. This is an individual project. 2. All source codes are checked automatically for similarity with other submissions and exercises from previous years. Do not copy codes from the internet or your friends. Make sure you write and submit your own code. Any sign of cheating will be penalized, and you will get -50 points for the project, and you will get F grade in case of recurrence in any other project. 3. There will be time limit on test cases, so the most important side of this project is to write your code in an efficient manner.
Even if your code is completely correct, you will not get full points if it is not efficient. 4. Parallel Programming is not allowed. The direct use of any parallel programming structure such as ForkJoin, Stream or Thread will result in a point reduction. 5. If the entire path you find is not suitable, you cannot get points for that route. We will not accept objections like: ”but my route is correct except for the last two points.” 6.
You can add as many files as you can as long as they are in the “src” folder and your project can be compiled as above. But the entry point of your program should be “project4.java”. 7. Make sure you document your code with necessary inline comments and use meaningful variable names. Do not over-comment or make your variable names unnecessarily long. This is very important for partial grading. 8. Expected running time of each test case is provided with input/output files. They are not strict limits; it is given so that you have an idea about the approximate running times. Execution times may vary for each run or computer to computer. If it works in 10 seconds on my computer, it can run in 20 seconds on another computer.
However, if it’s running in 100 seconds on another computer, there might be something wrong with your code. 5 7 More Input & Output Examples 7.1 Example1 Input 6 4 s0 s5 s1 s2 s3 s4 s0 s2 3 s1 s2 8 s2 s3 4 s4 2 s3 s4 s5 5 s5 Output Explanation 10 (s0 → s2 → s4 → s5) 14 (s1 → s2 → s3 → s2 → s4) Table 3: Sample Input2 and Output2 with Explanations s0 s1 s2 s3 s4 s5 3 8 4 2 5 Explanation: While cutting the flags, Rambo starts from s1. Then he goes to s2. Then he goes to s3. He traveled 12 distances in total. Since he used exactly the same path between s2-s3 before, he uses public transport here and returns to s2 again. His total distance is still 12. Then he goes to s4 and finishes cutting the flags with a distance of 14. Note that it is also okay to start from s2, s3, or s4. All of them will give the same result. But he can’t start from s0 or s5. 6 7.2 Example2 Input 9 4 s0 s8 s2 s4 s5 s7 s0 s2 3 s1 s2 8 s4 8 s2 s3 4 s6 2 s3 s5 4 s4 s5 s6 s7 2 s7 s8 5 s8
Output Explanation 12 (s0 → s2 → s6 → s7 → s8) 28 (s4 → s1 → s2 → s3 → s5 → s3 → s2 → s6 → s7) Table 4: Sample Input3 and Output3 with Explanations s0 s1 s2 s3 s4 s5 s6 s7 s8 3 8 8 4 2 4 2 5 Explanation: While cutting the flags, Rambo starts from s4 and follows the path s1, s2, s3, s5 and the total distance is 24. Because he used the exact s5-s3-s2 path before, he goes to s2 at no cost. Then he goes to s6 and s7. The spanned total distance is 28. Note that it is also okay to start from s7, s5 or s2. All of them will give the same result. However, he can’t start from any other nodes without flags. 7 7.3 Example3 Input 6 3 s0 s5 s1 s3 s4 s0 s1 4 s1 s2 2 s3 11 s4 10 s2 s3 1 s4 3 s3 s4 7 s5 5 s4 s5 4 s5 Output Explanation 12 (s0 → s1 → s2 → s3 → s5) 7 (s1 → s2 → s3 → s2 → s4) Table
5: Sample Input4 and Output4 with Explanations s0 s1 s2 s3 s4 s5 4 2 1 3 4 5 7 10 11 Explanation: While cutting the flags, Rambo starts from s1. Then follows the path s2-s3 with a total distance of 3. Now he has to go to s4 but because he never traveled the exact path s3-s2-s4, he can’t use public transportation. He has to follow s2, s4 with a total distance of 3+4 = 7. 8 7.4 Example4 Input 6 3 s0 s5 s1 s3 s4 s0 s1 4 s1 s2 2 s3 20 s4 10 s2 s3 10 s4 3 s3 s4 20 s5 20 s4 s5 20 s5 Output Explanation 29 (s0 → s1 → s2 → s4 → s5) 17 (s1 → s2 → s3 → s1 → s2 → s4) Table 6: Sample Input4 and Output4 with Explanations s0 s1 s2 s3 s4 s5 4 2 10 3 20 20 20 10 20 9
CmpE 250 Project 5 – Reclaim the Iron Throne
1 Introduction
Rhaenyra Targaryen, the first-born child of King Viserys I Targaryen, was considered the rightful heir to the Iron Throne. She was going to rule all the Westeros but her half-brother, Aegon Targaryen, seized the throne by force. Rhaenyra is now determined to reclaim the Iron Throne from Aegon. However, she heard from her consultants that Aegon started to gather support from all corners of Westeros to maintain his power.
She knows that in order to defeat Aegon, she needs to prevent him from gathering enough support. So she trusts your algorithm skills and asks you to help her take her rightful place as queen. Aegon’s main purpose is to construct the biggest army with soldiers from all the regions in King’s Landing. He began by sending envoys to The Reach, Riverlands, Dorne, The Vale of Arryn, The Westerlands, and The Stormlands, offering alliances and promises of rewards in exchange for support (e.g. troops).
He is pleased to receive enthusiastic responses from these 6 regions and begins to mobilize his forces. The regions are willing to send all their troops to King’s Landing but because of limited transportation resources, there are a limited amount of troops that can reach the King’s Landing. But Aegon and his consultants know how to maximize the number of troops that can come to King’s Landing to support him. For Rhaenyra to defeat Aegon, she must first know the size of the troops he’s gathering in King’s Landing.
Also, she wants to block the route of all the troops, so needs to know where to send her armies to. Your duty is to give this crucial information to Rhaenyra using your CmpE250 knowledge. 1
2 Details
• There are exactly 6 regions willing to send all the troops they have. • Each troop travels to King’s Landing and each troop has the same number of soldiers. • There are many cities in the routes of the troops and only a limited number of troops can travel between two cities due to transportation limitations and harsh conditions. Luckily, we know the capacity of each road. • If there is a road from one city to another, let’s say from city 1 to city 2, it doesn’t mean that there is also a road from 2 to 1.
• A region is most vulnerable when preparing to send all the troops it has and a road is most vulnerable when the troops are traveling at the maximum capacity of that road. Rheanyra wants to send her armies to the vulnerable regions and roads. She also wants to block all the troops going to King’s Landing, so you must find the cut with full capacities that add up to the maximum number of troops. (Sounds like a familiar problem. doesn’t it? :)) • There are no roads from cities to regions or from King’s Landing to cities/regions.
3 Input & Output
3.1 Input • The first line represents the total number of cities except King’s Landing. • The second line contains 6 integers, each representing the number of troops a region is willing to send. • The next 6 lines will give the ID of a region, the number of troops they are trying to send, the IDs of the cities that are reachable from the given region, and the capacity of the road from that region to that city. • Each next line will give the ID of a city, the IDs of the cities that are reachable from the given city, and the capacity of the road between these two cities. 2
3.2 Output • An integer, the maximum number of troops that can reach the King’s Landing. • (BONUS) Regions and roads (as pairs of vertices line by line) that Rhaenyra must send her armies to.
3.3 Example Input Explanation 4 There are 4 cities in the route, except King’s Landing. 50 40 60 29 43 20 r0 is willing to send 50 troops, r1 40, r2 60, r3 29, r4 43 and r5 20. r0 c0 25 The capacity of the road from r0 to city c0 is 25. r1 c0 20 c1 30 r2 There is no road from r2 to cities. r3 c2 9 r4 c3 7 r5 c3 18 KL 37 c0 c2 30 KL 19 The capacity of the road from c0 to c2 is 30, from c0 to the King’s Landing is 19. c1 c0 10 c2 c0 19 KL 33 c3 KL 15 Table 1: Sample Input with Explanations 3 r0 25/50 r1 18/40 r2 0/60 r3 9/29 r4 7/43 r5 20/20 c0 c1 c2 c3 KL 25/25 18/20 0/30 9/9 7/7 0/18 20/37 24/30 0/10 19/19 0/19 33/33 7/15 Vulnerable roads and regions that must be blocked are shown in red. A/B indicates that A troops are using the road with B capacity. The dashed line shows the blocking cut.
Output Explanation 79 r5 r4 c3 c0 KL c2 KL Maximum number of troops. (20+7+33+19) These are vulnerable regions and roads, and the sum of their capacities are the maximum number of troops. Table 2: Expected Output File 4
4 Submission
Your code will be graded automatically. Therefore, it’s important that you follow the submission instructions. First, all of your source files should be collected under Project5/src. Then, you should zip the Project5 folder and rename it to .zip. This zip file will be submitted through moodle. Name of your main class must be project5.java. Your program will be compiled with the command below: javac -target 17 Project5/src/*.java -d ./ The input and output files can be in any folder. Design your code to accept the full path for file arguments.
Your program will be run with the command below: java project5 Make sure your final submission compiles and runs with these commands.
5 Grading The grading of this project is based on the automatic compilation and run and the success of your code in test cases. If your code compiles and runs with no error, then you will get 10/100 of the project grade. The rest of your grade will be the sum of collected points from each test case. If you provide the correct number of maximum troops for each test case, then you will receive 100 points. Finding the regions and roads is an optional task which is worth 15 bonus points. If your submission is not autorunnable, then you will receive 0 at first and then have to issue an objection.
6 Warnings 1. This is an individual project. 2. All source codes are checked automatically for similarity with other submissions and exercises from previous years. Do not copy codes from the internet or your friends. Make sure you write and submit your own code. Any sign of cheating will be penalized, and you will get -50 points for the project, and you will get F grade in case of recurrence in any other project. 5 3. There will be time limit on test cases, so the most important side of this project is to write your code in an efficient manner.
Even if your code is completely correct, you will not get full points if it is not efficient. 4. You can add as many files as you can as long as they are in the “src” folder and your project can be compiled as above. But the entry point of your program should be “project5.java”. 5. Make sure you document your code with necessary inline comments and use meaningful variable names. Do not over-comment or make your variable names unnecessarily long. This is very important for partial grading. 6
