Programming Assignment Due in 9th OCT

KING ABDULAZIZ UNIVERSITY

Faculty of Computing & Information Technology

Computer Science Department CPCS 204: Data Structures I

Assignment I – Fall 2017

Due date: – October 9th, 2017 at 11:59pm

Purpose

• The main purpose of this program is for you to review file I/O (input/output) and to implement binary search in the program.

Read Carefully:

• This program is worth 6% 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 by 11:59 PM on Monday, October 9 2017. 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 P1.zip

Question: 1 2 3 Total

Points: 20 20 60 100

Score:

Concept Application & Algorithmic Part

1. Consider the following array

3 14 27 31 39 42 55 70 74 81 85 93 98

(a)(10 points) Apply the binary search algorithm on the above array searching for the key 85. Please list the value of mid, low, and high at the end of each iteration for searching for the key 85.

Solution: mid low high

initialization - 0 12 iteration 1 6 7 12

... ...

... ...

(b)(10 points) Apply the linear search algorithm on the above array searching for the key 85, Please list the values of checked array’s index in each iteration for searching for the key 85.

Solution:

checked array’s index iteration 1 0

... ...

2.(20 points) Algorithm Write up. Please rewrite binary search algorithm to find a search key in an array that contains values of descending order (from largest to smallest values)

Solution:

public s t a t i c i n t b i n S e a r c h ( i n t [ ] a , i n t v a l u e ) { i n t low = 0 ; i n t h i g h = a . l e n g t h −1;

}

CPCS 204 Assignment I, Page 2 of 8

Programming Part: FCIT SuperStore

Objective Practice all concepts from CPCS-202 and CPCS-203, with a focus on making classes and creating objects from these classes. Specifically, you will practice making an array of objects and manipu- lating/using the data inside the array. Finally, and VERY important is that this program requires you to read from a file and write to a file (practice with File I/O). This is very important because all programs during the semester will use File I/O.

The Problem FCIT is growing so large that theyre actually starting a mini-supermarket, FCIT SuperStore, stocked with typical supermarket products along with all the studying essentials (selection of teas, coffees, expresso, and many containers of Red Bull and sweets!)

FCIT SuperStore is in need of a program that:

• manages all products in the store, along with the stock (quantity) for that product • manages the reordering of depleted products (once the stock for that item reaches zero) • manages the total sales to all customers.

During the program, the following things can occur (just as in a normal store):

• New products can be added to the list of products. For example, perhaps the store doesnt initially carry Cheerios. So this new product, Cheerios, can be added as a new product for FCIT SuperStore. Note: when new products are added for the first time, they are initialized with a specific stock amount associated with that product. It is guaranteed that newly added items will always have a quantity of at least one unit.

• Customers can come throughout the day to purchase items from the store. If the items are available, they are purchased, and the stock of those specific products are all reduced by the quantity purchased. If a product is not available (stock is zero), the customer simply does not purchase that product.

• A purchase occurs when a customer finds at least one of the items they are looking for. All such purchases will need to be saved as described later in this write up. However, if a customer enters the store and all of the desired items have a stock of zero, this customer did not make a purchase, and therefore, does not need to be saved.

• As customers purchase products, the quantity for that product is clearly reduced. Once the inventory level for a product reaches zero, no more product can be purchased (of that item) until the RESTOCK command occurs.

• Reorders can be made, and this will happen whenever the RESTOCK command is read from the input file. Products that are reordered will have their stock increased based on a fixed restock quantity associated with that particular product.

You will use File I/O to read input from a file and then print the output to a file. To be clear, you will read COMMANDS from an input file. Example commands are ADDITEM, RESTOCK, CUSTOMER, etc. Then, depending on the command, you will either add a new item, restock the items, process a customer/sale, etc. But instead of printing to the console window (screen), you will print to an output file.

Sample input and output files have been provided for you on the blackboard.

CPCS 204 Assignment I, Page 3 of 8

3.(60 points) For this program, you will create two Classes (UML diagram shown below):.

FCITSuperStoreSale

Data Members

private String firstName

private String lastName

private int numItemsOnList

private int itemsPurchased[]

private static int numSales

Operations/Methods

public String getFirstName( )

public String getLastName( )

public int getNumItemsOnList( )

public int[] getItemsPurchased( )

public static int get numSales( )

public void setFirstName( String firstName )

public void setLastName( String lastName )

public void setNumItemsOnList( int numItemsOnList )

public void setItemsPurchased( int[] itemsPurchased )

public static void setNumSales ( int numSales )

FCITSuperStoreProduct

Data Members

private int itemNum

private String itemName

private double itemPrice

private int quantity

private int restockQuantity

private static int numProducts

Operations/Methods

public int getItemNum( )

public String getItemName( )

public double getItemPrice( )

public int getQuantity( )

public int getRestockQuantity( )

public static int getNumProducts ( )

public void setItemNum( int itemNum )

public void setItemName( String itemName )

public void setItemPrice(double itemPrice )

public void setQuantity( int quantity )

public void setRestockQuantity( int restockQuantity )

public static void setNumProducts ( int numProducts )

You will use the FCITSuperStoreProduct class to create nodes of type FCITSuperStoreProduct, and you will use the FCITSuperStoreSale class to create nodes of type FCITSuperStoreSale.

The first two lines of the input file are as follows: Line 1: the maximum number of products that can be in the SuperStore Line 2: the maximum number of sales recorded by the system

CPCS 204 Assignment I, Page 4 of 8

You must read these values into appropriate variables.

Next, you will use these new values to make two new arrays:

1. An array of FCITSuperStoreProduct object references

2. An array of FCITSuperStoreSale object references

3. See pages 71-78 of Chapter 8 slides (from 203) for help on array of object references

To help you, here is the code to do this:

FCITSuperStoreProduct [ ] products = new FCITSuperStoreProduct[maxProducts]; FCITSuperStoreSale [ ] sales = new FCITSuperStoreSale[maxSales];

What do these lines do? They create an array of references. Note: each reference has a default value of null. Until now, we have NOT created any objects. For example, FCITSuperStore- Product objects are only created when we see the command ADDITEM. At that time, a new FCITSuperStoreProduct object will be created and the reference for that object will be saved in the appropriate location of the array.

Input File Specifications You will read in input from a file, “FCITSuperStore.in”. Have this AUTOMATED. Do not ask the user to enter “FCITSuperStore.in”. You should read in this automatically.

Note: a *.in file is just a regular text file. Also, a *.out file is a regular text file. Do not be scared by this. Instead of calling the input and output file as input.txt and output.txt, it is better for those files to have a good name. Therefore, the input file will be called FCITSuperStore.in and the output file will be called FCITSuperStore.out.

The first line of the file will be an integer, d, representing the maximum number of products in the SuperStore. The second line of the file will be an integer representing the maximum possible number of recorded sales for the SuperStore. Each of the remaining lines will have a command, which is then followed by relevant data as described below (and this relevant data will be on the same line as the command).

The commands you will have to implement are as follows:

1. ADDITEM Makes a new product which is added to the store. The command will be followed by the following information all on the same line: itemNum, an integer representing the item number for this product; itemName, the name of the item, no longer than 20 characters; unitPrice, the price of a single item; stockQty, the initial amount of stock for this product (guaranteed to be at least 1); restockQty, the quantity by which the product should be restocked whenever a reorder is placed.

When you read the ADDITEM command, you must make a new object of type FCITSu- perStoreProduct. Next, you must scan the additional information (listed above) and save this information into the correct data members of the new object. Each item will be unique. Meaning, the input file is guaranteed to not have duplicate items added to the store inventory via the ADDITEM command. Finally, you must save the reference of this object inside the appropriate index of the product array.

*Note: this array must stay in sorted order based on the ID of the product. So the prod- uct with the smallest ID value will be at index 0, the product with the next smallest at index 1, and so on. Therefore, when you save the object reference into the array, you must first find the correct sorted index. After you find the correct insertion location, if there is no object at that location, then you can easily save the object reference at this index. BUT, IF there is an object at the index that you find, you must SHIFT that object,

CPCS 204 Assignment I, Page 5 of 8

AND all objects to the right of it, one space to the right. This is how you make a new space in the array for the new object.

Example: if your array already has 6 product object references, from index 0 to index 5. And now you want to add a new product object reference at index 4 (based on the sorted location). Before you can add the new product object reference at index 4, you must SHIFT the product object references at index 4 and index 5 to index 5 and index 6. Basically you need to move them one position over to the right. Now, you have an empty spot at index 4 for the new product object reference.

2. FINDITEM This command will be followed by an integer on the same line. This integer represents the Item number of the item you must search for. You must perform a Binary Search on your array of FCITSuperStoreProduct object references. If the product is found, you should print the required information for the product. (see output).

*See output for different printing possibilities.

**Note: I want to confirm that you are using Binary Search for this task. Therefore, you should print each “mid” that is visited during the binary search (See output).

3. RESTOCK This command will have no other information on the line. When this command is read, all items that have a stock of zero must be restocked. You do this as follows:

• You must iterate over all objects in the products array. • You will check the stock of each item. If the stock is zero, you will reset the stock using

the restockQty variable.

4. CUSTOMER This command is for customers attempting to make purchases. It is followed by the following on the same line: a first name, then a last name, each no longer than 20 characters; an integer, n, representing two times (2x) the number of different products the customer wants to purchase, followed by n integers, which will be pairs of item numbers and the respective quantity purchased of that item number. For example, if n were six, this means the customer wants three items. Pretend those following six integers were as follows: 5437 2 8126 1 9828 4. This means the customer wants 2 units of product 5437, 1 unit of 8126, and 4 units of product number 9828.

As mentioned previously, a purchase occurs when a customer finds, and of course then buys, one of the items on their shopping list. When this happens, a new object of type FCITSuperStoreSale must be made, which records this sale. The data members of the object must be saved correctly. One member of the FCITSuperStoreSale node is itemsPurchased. This is an array that must be made based on the size (number) on the original shopping list. If the product is found and purchased, the item number is added to the corresponding cell of this array, along with the quantity purchased. We assume that if the stock for a given item is available, the customer will purchase the full desired quantity on their shopping list (of that item). If the product is not found, a zero is recorded in that cell of the array.

Exanple : Based on the three-item example above, if the first and third items were available, with the second being unavailable (no stock), the itemsPurchased array would have SIX cells as follows: 5437, 2, 8126, 0, 9828, 4. This shows that 2 units of 5437 were purchased, and 4 units of 9828 were purchased; the zero after item 8126 simply shows that the item was not available

Finally, once all appropriate information is saved into the data members of the FCITSuper- StoreSale object, a reference to this object is then added to the next available position in the sales array. Note: a line of output is printed regardless of whether or not a purchase was made. Refer to sample output for examples.

5. INVENTORY This command will have no other information on the line. When this command is read, the current FCIT SuperStore inventory (each item with its respective

CPCS 204 Assignment I, Page 6 of 8

stock) is printed to the file in ascending order (the order that the product list is already in). See sample output file for specific formatting of this command. If there store does not have any inventory, an appropriate error message is printed (see sample output).

6. PRINTSUMMARY This command will have no other information on the line. When this command is read, a report of all sales, for that given day, will be printed to the output file. Please refer to sample output for exact specifications. Once the header information is printed (see sample output), all sales (nodes) found in the sales array will need to be printed. This will proceed as follows:

• You need to iterate over the entire sales array. • For every Sale (node) in the sales array, you need to print the Sale number (starting at

1), along with the first and last name of the customer (in that order). You then need to print the list of items that were successfully found and then purchased. Finally, you need to print the total amount paid. Please refer to the EXACT output format for specifics.

• Lastly, you must print out the total sales (dollar amount) for the given day

Output Format Your program must output to a file, called “FCITSuperStore.ou”. You must follow the program specifications exactly. You will lose points for formatting errors and spelling.

When examining the output file, you should notice that the INVENTORY command and the PRINTSALESSUMMARY command results in printing a “semi-formatted” line of text. To make everything clear and to guarantee the correctness of your format, we are providing those exact code needed to print those two lines below:

Here is the literal for printing inventory items in the INVENTORY command:

‘‘\t\|Item\%6d\|\%-20s|\$\%7.2f\|\%4d unit(s)\|\%n’’

And here is the literal for printing customer items in the PRINTSALESSUMMARY com- mand:

‘‘\t\t| Item \%6d | \%-20s | \$\%7.2f (x\%4d) |\%n’’

Note: You need to use formatted printing (output.format) to print these lines of output

Sample and Output Files A sample input file, with corresponding output file, can be found on the Moodle (the files have too many lines to paste here).

NOTE: These files do NOT test every possible scenario. That is the job of the programmer to come think up the possible cases and test for them accordingly. You can be sure that our graders will grade with very large input files, which are intended to, ideally, test all possible cases. It is recommended that you spend time thinking of various test cases and build your own input file for testing purposes.

***WARNING*** Your program MUST adhere to the EXACT format shown in the sample output file (spacing capitalization, use of dollar signs, 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 between 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 grade. Again, your output MUST ADHERE EXACTLY to the sample output.

CPCS 204 Assignment I, Page 7 of 8

Grading Details Your program will be graded upon the following criteria:

1. Adhering to the implementation specifications listed on this write-up.

2. Your algorithmic design.

3. Correctness

4. Use of Classes, Objects, and Arrays of Objects. If your program is missing these elements, you will get a zero.

5. The frequency and utility of the comments in the code, as well as the use of white space for easy readability. (We’re not kidding here. If your code is poorly commented and spaced and works perfectly, you could earn as low as 80-85% on it.)

6. Compatibility to the newest version of NetBeans. (If your program does not compile in NetBeans, you will get a large deduction from your grade.)

7. Your program should include a header comment with the following information: your name, email, course number, section number, assignment title, and date.

8. Your output MUST adhere to the EXACT output format shown in the sample output file.

Deliverables You should submit a zip file with THREE files inside:

(a) FCITSuperStoreProduct.java

(b) FCITSuperStoreSale.java

(c) FCITSuperStore.java (this is your main program)

***These three files should all be INSIDE the same package called fcitSuperStore. If they are not in this specific package, you will lose points.

NOTE: your name, ID, section number AND EMAIL should be included as comments in all files!

Suggestions: • Read AND fully understand this document BEFORE starting the program! • Next, start by making the two classes to create classes: FCITSuperStoreProduct and FCITSuperStoreSale

• So make those two classes, with all the data members, constructors, and accessor/mu- tator methods.

• Now, after you have made these two classes, make your main program file: FCITSuper- Store.java

• This is your main program that will read the commands from the file, process the commands, and print to the output file

• Use theIOexample.java program to help you create your main to read from a file and write to a file.

• Finally, one by one, implement the commands (ADDITEM, CUSTOMER, etc). Hope this helps.

Final suggestion: START EARLY!

CPCS 204 Assignment I, Page 8 of 8