King Abdulaziz University Faculty of Computing and Information Technology Computer Science Department
CPCS204, Spring 2019 Program 1: DNA Sequences
Assigned: Monday, Jan 23rd, 2019 Due: Monday, Feb 3rd, 2019
Purpose
- Learn to implement linked list for a real world problem.
- Review file I/O (input/output).
Read Carefully:
This program is worth 5% of your final grade.
WARNING: This is an individual project; you must solve it by yourself. Any form of cheating will result in receiving zero in the assignment.
The deadline for this project is Monday, Feb 3rd 2019 by 11:59 PM.
Note: Once the clock becomes 11:59PM, the submission will be closed! Therefore, in reality, you must submit by 11:58 and 59 second.
LATE SUBMISSION: You are allowed to make a late submission, but there is a penalty. If you submit within 24 hours of the due date (so on Tuesday by 11:59PM), you will receive a 25% deduction. If you submit within 48 hours of the due date (so on Wednesday by 11:59PM), you will receive a 50% deduction.
Blackboard Submission:
This project must be submitted online via blackboard.
The source file(s) of your program should be zipped up. You must name the zip file using the following naming convention: SectionNumber_StudentID_ProgramNumber.zip
Example: EA_1110348_P2.zip
|
Question:
|
1
|
2
|
3
|
Total
|
|
|
|
|
|
|
|
Points:
|
20
|
20
|
60
|
100
|
|
|
|
|
|
|
|
Score:
|
|
|
|
|
|
|
|
|
|
|
Question 1: (20 points)
1. Concept Application: Suppose a linked list contains following DNA sequences stored in any order. Write the steps to delete the sequence “tgtgct” from this list by showing the position of pointer and the status of linked list after every step.
|
|
SeqNext
|
SeqNext
|
SeqNext
|
SeqNext
|
SeqNext
|
|
Seq
|
Next
|
|
|
head
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
null
|
|
|
aattgg
|
|
|
ttccgc
|
|
|
tgtgct
|
|
|
taaggt
|
|
|
tgtccc
|
|
|
tacggt
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Question 2:(20 points)
2. Algorithm Write up: Suppose a linked list contains DNA sequences stored in any order. Write an algorithm which must count and print how many of them contain the nucleotide base called adenine (A) (i.e. the sequences should be printed ‘AATTGG’, ‘TAAGGT’, while the sequence should not be printed ’TGTGCT’).
For example, if linked list contains the following nodes
|
|
SeqNext
|
SeqNext
|
SeqNext
|
SeqNext
|
SeqNext
|
|
Seq
|
Next
|
|
|
head
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
null
|
|
|
aattgg
|
|
|
ttccgc
|
|
|
tgtgct
|
|
|
taaggt
|
|
|
tgtccc
|
|
|
tacggt
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
The output of algorithm should be
Number of sequences contain the nucleotides called adenine (A): 3
Aattgg, taaggt, tacggt.
Algorithm:
Input:
Output:
Method:
UPDATED
CPCS204, 1st Term 2019_Fall 2018
Program 4: Grocery Store Cashier Line Simulator
Practice using stacks and queues.
Concept Application & Algorithmic Part (30 Points)
(10 points) Concept Application: (Queues and Stacks)
Program 4: (70 Points)
Grocery Store Cashier Line Simulator
Objective
Practice using stacks and queues.
The Problem Settings and Environment
A local grocery store wants to improve their customer service. The store currently has three cashier machines. They want to decide whether or not to add another cashier machine based on the average waiting time of each customer in the current cashier lines. They decided to use a simulator to calculate the average waiting time. Your job is to implement this simulator that finds the average waiting time for customers. The store manager indicated that the peak hours are from 12:00 pm till 5:00 pm. Thus, your program will simulate this period only.
As mentioned, the local store is a small growing business, which has three cashier Agents [Agent1, Agent2 and Agent3] to serve customers. When a customer wants to check out, he/she automatically (and naturally) will enter the shortest line. If two (or more) of the lines are equally short, the customer will enter the line with the "smaller" line number. Meaning, if Line 1 was very long but Line 2 and Line 3 were both equally short, the customer would enter Line 2 because it has the "smaller" number.
Example for customers’ line up at cashier queues:
Bilal Alzahrani wants to check out at 12:04PM. Line 1 has eight people waiting. Line 2 has seven people waiting. And Line 3 has seven people waiting. So the shortest lines are Line 2 and Line 3, but they are equal. Therefore, Ali should enter into the “smaller” line number. Line “2” is smaller than Line “3”. Therefore, Ali will enter Line “2”.
Once a customer arrives at the front of the cashier line, they will initiate their check out process. For checking out the following assumptions was made:
- Each customer takes a constant amount of time to make a payment using cash or a credit card at the end of their checking out process. This time is assumed to be the same for all the customers and therefore it is not included in our simulator.
- The time taken for checking out depends on the number of items in the customer’s shopping cart. The assumption was based on the time taken to scan each item in the shopping cart and bagging that item, which can be approximated to 1 minutes. For example, if a customer has 12 items in his/her shopping cart, the entire check out process would take 12 minutes.
- The minimum time taken to check out a customer is 1 minute even if the time taken to scan the items in his/her shopping cart is less than 1 minute.
- The unit of time is taken to be one minute. Any fractions of a minute are ignored.
Example for time taken to serve a customer:
Huda Ali arrives at 1:04 PM. There are many people in front of her. Finally, she makes it to the front of the Line 3 at 1:19 PM. She has 18 items in her shopping cart. Therefore, the actual check out process will take 18 minutes. Hence, he leaves the cashier line at 1:37 PM.
After each check out transactions, one electronic copy of that transaction will be saved onto the shared Daily Transaction Log (DTL), which is a stack of e-transactions to be printed at the end of each day. The store manager uses these transactions for future reference. Given the fact that this is a small local store, there is only one, local LAN network printer that is shared by all three cashier agents. Finally, at the end of the day, the DTL is printed to the output in reverse order. See sample output for more details.
Your Assignment is to design a simulator that models the aforementioned system for local store check-out. The simulation will run over n number of days, where the simulation runs over each minute of every day, from 12:00 PM to 5:00 PM.
- So this simulation is simply a FOR loop (or WHILE loop) that will iterate one time for each minute between 12:00 PM and 5:00 PM (and possibly longer if people are still waiting to check out in any of the lines (entry, or cashier lines). See more details below.
Implementation Details:
To solve this program, you will need:
- 3 Queues: each queue will contain objects of type Customer. Therefore, each queue will be an object of the same Customer queue.java class.
- 1 additional queue for the Entry Line (see below). This queue will also contain objects of type customer.
- 1 stack for Daily Transaction Log (DTL). The stack will contain Transactions objects
The UML Diagrams for required Java classes are at the end of this write-up.
Entry Line:
For a given day, you will first read in, from a file, all the customers that will ultimately arrive during that day. Customers will be in chronological order in the file – i.e. the first customers in the file will be first to enter the store. For each customer you read, you must create a new object of type Customer, save their appropriate (read-in) information into their object, and then you will enqueue them into what we call the “Entry line.”
What is the “Entry line”?
It is clearly a queue, which contains all of the customers who are expected to shop at the store in that particular day. As time moves forward, you will remove (dequeue) customers from the Entry line IF the currentTime (your daily looping variable over each minute) equals the “arrival” time of the customers who is at the front of the “Entry line”. We could say that this time is when a customer has finished shopping at the store and he is ready for check out.
Once a customer is ready to check out, he/she is dequeued from the “Entry line”. Then, he/she is immediately enqueued into one of the three lines (Line 1, Line 2, or Line 3). Note: it is possible that multiple customers are ready to check out at the same time. Meaning, multiple customers can possibly have the same “ready” time within the “Entry line”. Customers who are “ready” at the same time are placed in the lines in the order that they arrive (based on the chronological order of the input file).
Three Check Out Lines (Queues):
As mentioned, as soon as a customer is ready to check out, he/she must line up in one of the three lines for check-out.
Stack of Daily Transaction Log:
When a customer is done with his/her checking-out, an electronic copy of this transaction will be saved onto the shared Daily Transaction Log (DTL), which is a stack. Then, at the end of the day, all e-transactions will be printed (see output file). Therefore, at the beginning of the next day, the DTL stack will be empty.
- Important note regarding queues and stack implementations:
- The “Entry line” and the three check-out lines MUST be implemented using a linked-list based queue.
- The DTL stack must be implemented using a linked lists stack.
Important Details:
- If an arrival and departure occur during the same minute, the departure is processed first.
- When a customer is “ready” to check out, that customer is immediately placed in one of the three cashier check-out lines (during the same minute).
- If the line was empty, this means the customer will be at the front of the line. Therefore, the customer will enter the store and will automatically be at the front of the line. HOWEVER, we will assume that it takes one minute to walk to the front of the line (or perhaps to grab the desired item from the store).
- So if the customer enters at 1:13PM and if a line is empty, the customer will start his/her checkout at 1:14PM (one minute later).
- Once at the front of the cashier Line, a customer can only leave this line once their transaction is finished (based on number of items in his shopping cart…I minute per item). So if you are at the front of Line 3 at 4:20 PM and if you have 20 items, you will finish check-out at 4:40 PM and leave the line at the same time.
- Once the check-out is complete, the transaction is immediately created and placed on the stack of DTL.
- If a customer leaves the line at 4:21 PM, the next customer will automatically be at the front of the line at that same minute (4:21PM). However, they will not begin their check-out until the following minute (4:22PM).
- For this simulation, we are only concerned about the time from 12:00 to 5:00 PM. This means that no new customers can enter the store at 5PM (or after). However, the store does stay open to check out the all customers who arrived by 4:59 PM. So even if 100 customers arrive at 4:59 PM, this is no problem. The store will stay open until all customer check-out have been processed. However, it is guaranteed that this will never take beyond 11:59 PM.
Input File Specifications
- You will read in input from a file, "GroceryStoreSim.in".
- No input is entered by the user. You should read in this automatically.
- The first line of the input file will contain an integer, m, which represents the number of days of the simulation (for example, the number of days in “GroceryStoreSim.in” is 8 days.
- The lines after that in the input file contain an integer, k, representing the number of customers at the grocery store on that day. Each customer's information will be on a single line as follows:
Output File Specifications
Your program must output to a file, called "GroceryStoreSim.out". You must follow the program specifications exactly. You will lose points for formatting errors and spelling.
Where X is the nth day of the simulation. Follow this header with one blank line.
There are many different types of output lines. You should study the sample input/output files to see what lines should be printed for the different scenarios.
The time should be printed out in the following format:
(H)H:MM PM
The first one (or possibly two) digits represent the hour. The hour must not be printed as 0 if it is between noon and 1:00, so you’ll need to check for this. This is followed by a colon and then the next two digits represent the minute. If the minute value is less than 10, you’ll need to add a leading 0, so that it prints as 3:05, not 3:5. (It probably makes sense to have a method that takes in as input the number of minutes after 12:00 PM and, in turn, prints out the corresponding time in this format.)
Follow each day's output with one blank line. Then you will print all the E-Transactions (from the DTL stack) as shown in the sample input and output files.
Follow each day's summary with TWO blank lines.
See sample input and output files for examples.
***WARNING***
Your program MUST adhere to this EXACT format (spacing capitalization, use of colons, periods, punctuation, etc). The graders will use very large input files, resulting in very large output files. As such, the graders will use text comparison programs to compare your output to the correct output. If, for example, you have two spaces in the output when there should be only one space, this will show up as an error even through you may have the program correct. You WILL get points off if this is the case, which is why this is being explained in detail. Minimum deduction will be 10% of the grade, as the graders will be forced to go to text editing of your program in order to give you an accurate grad