Course Description
Advanced concepts of data, storage, organization and retrieval. Topics include multiple linked lists, balanced trees, graphs, abstract data types, classes and methods, object oriented programming, searching and sorting.

Course Overview
This class will build upon your knowledge of C++ as we examine, analyze, and manipulate more advanced data structures such as binary trees, heaps, stacks, and queues. By understanding the advantages and disadvantages of these algorithms, you will better be able to utilize these tools in real life problems.

CISS 350 CISS350 CISS/350 ENTIRE COURSE HELP – COLUMBIA COLLEGE

CISS350A Advanced Algorithms and Data Structures

CISS350 Entire Course includes:

CISS 350 Programming Assignment 1 Checkout System
CISS 350 Programming Assignment 2 Computer Dating Service
CISS 350 Programming Assignment 3 Local Medical Clinic
CISS 350 Programming Assignment 4 Circular Linked List
CISS 350 Programming Assignment 5 Towers of Hanoi
CISS 350 Programming Assignment 6 Police Department
CISS 350 Programming Assignment 7 Compare Two Implementations of a Priority Queue

CISS 350 CISS350 CISS/350 ENTIRE COURSE HELP – COLUMBIA COLLEGE

CISS 350 Programming Assignment 7 Compare Two Implementations of a Priority Queue

Programming Assignment 7
Your assignment is to write and compare two implementations of a priority queue whose highest priority element is the one with the smallest key value. The elements have the following declarations:

The first implementation uses a minimum heap. You need to modify the heap operations to keep the minimum, rather than maximum, element in the root. The comparison function should compare key fields.
The second implementation uses a linear linked list, whose elements are ordered by key value.

Test Data
Create a data set that contains 50 items with priorities generated by a random-number generator.

Comparing the Implementations
To compare the operations, you must modify the Enqueue and Dequeue operations to count how many elements are accessed (compared or swapped, in the case of reheaping) during its execution.
Write a driver to Enqueue and Dequeue the 50 test items and print out the number of elements accessed for the Enqueue and Dequeue operations. Run your driver once with each implementation.

Deliverables

A listing of specification and implementation files for both priority queue implementations
A listing of your driver
A listing of your test data
A listing of the output from both runs
A report comparing the number of elements accessed in executing each operation.

CISS 350 Programming Assignment 1 Checkout System
CISS 350 Programming Assignment 2 Computer Dating Service
CISS 350 Programming Assignment 3 Local Medical Clinic
CISS 350 Programming Assignment 4 Circular Linked List
CISS 350 Programming Assignment 5 Towers of Hanoi
CISS 350 Programming Assignment 6 Police Department
CISS 350 Programming Assignment 7 Compare Two Implementations of a Priority Queue

CISS 350 CISS350 CISS/350 ENTIRE COURSE HELP – COLUMBIA COLLEGE

CISS 350 Programming Assignment 6 Police Department

Programming Assignment 6
Write a program for a police department that has collected a database of information on various suspects for a given crime. (Luckily for you, the department is only investigating one crime at a time.) Each suspect has a set of attributes, such as shifty eyes, a limp, or a parrot on his shoulder. The maximum number of such attributes for any suspect is not known. Your program accepts commands to manipulate the database in order to narrow down the list of suspects, in the hope of pinpointing the villain.

Input

The retained criminal information, generated by the previous execution of this program, is input from file “Criminal.mf” at the beginning of each execution of the program.
The user inputs commands from the keyboard, in the format shown below. Names and attributes are strings of no more than 20 characters. The program should not be case sensitive (e.g., ‘JOE’ and ‘Joe’ are the same name). To simplify the processing, you can assume that names are unique; that is, no two criminals use the same professional handle. The commands are discussed in detail in the Command Processing instructions below.

Output

Responses to user commands are to be written to the screen, as described in the Command Processing instructions below.
Echo print each command and show the results of any PRINT commands in a file called “Criminal.trn”. You may determine the format of the information in this file; it should be labeled and formatted clearly. A hard copy of this file is turned in with your program for grading.
If any new suspects were added (see ADD command), file “Criminal.mf” must be rewritten to contain the updated collection of criminal information.

Command Processing
New suspects can be added to the collection of criminal information using the ADD command. An inquiry consists of a set of commands with respect to a single crime, at the end of which the crime is assumed to be solved. An inquiry must be completed within the execution of the program; it cannot be “saved” to finish on a subsequent execution. After an inquiry is complete, a new inquiry (the investigation of another crime) can begin. Each new inquiry starts over with the entire collection of suspects.

[table]
Command, Processing
ADD, “Add a suspect to the Suspects data structure. Prompt the user for the suspect’s name and a list of attributes. ADD commands can be issued only before an inquiry begins.”
INQUIRY, “Prompt user for code name of this inquiry. Once the inquiry has begun, do not allow the user to issue the ADD command until this inquiry is complete.”
TIP, “Prompt user for the tip information (a particular attribute). Process the tip, reducing the set of current suspects by deleting suspects who do not match the attribute mentioned in the tip. If there is only one suspect left in the set of active suspects, print out a message indicating that the crime is solved. Be sure to include the suspect’s name and inquiry code name. This terminates the current inquiry.”
CHECK, “Prompt the user for a suspect’s name. Check the set of active suspects to see if this name is there; print out an appropriate response.”
PRINT, “Print the set of active suspects (those who have not yet been eliminated).”
QUIT, “If any new suspects have been added during this execution of the program, rewrite the “Criminal.mf” file. Be careful about how you go about saving the records; the traversal order affects the shape of the tree that is built on the next execution of the program. Terminate the program.”
[/table]

CISS 350 Programming Assignment 1 Checkout System
CISS 350 Programming Assignment 2 Computer Dating Service
CISS 350 Programming Assignment 3 Local Medical Clinic
CISS 350 Programming Assignment 4 Circular Linked List
CISS 350 Programming Assignment 5 Towers of Hanoi
CISS 350 Programming Assignment 6 Police Department
CISS 350 Programming Assignment 7 Compare Two Implementations of a Priority Queue

Sample Input
(Some of the labels shown in the sample input are not typed in by the user, but are only printed for clarity. For this example, the “Criminal.mf” file is empty and all the potential suspects are added by command.)

ADD       Name:             Quickdraw McGraw
          Attributes:       has a Texas accent
                            has a body guard
                            is computer literate
ADD       Name:             Twingun Morgan
          Attributes:       has a New York accent
                            has red hair
                            smokes cigars
ADD       Name:             Jackda Ripper
          Attributes:       has a body guard
                            bites his fingernails
                            carries a knife
                            is computer literate
ADD       Name:             Annie Getcher Gunn
          Attributes:       has a New York accent
                            has red hair
                            eats Fritos
                            smokes cigars
ADD       Name:             Slowdrawl Raul
          Attributes:       has a Texas accent
                            carries a knife
                            is computer literate
                            eats Fritos
ADD       Name:             Sloan de Uptake
          Attributes:       has a body guard
                            has red hair
                            bites his fingernails
                            is computer literate
INQUIRY            Code Name: Bang Bang
TIP                Tip Info: has a New York accent
CHECK              Quickdraw McGraw
TIP                Tip Info: has red hair
CHECK              Annie Getcher Gunn
TIP                Tip Info: eats Fritos
INQUIRY            Code Name: Holdup
TIP                Tip Info: has a Texas accent
CHECK              Slowdrawl Raul
CHECK              Sloan de Uptake
TIP                Tip Info: is computer literate
INQUIRY            Code Name: Tough Stuff
TIP                Tip Info: bites his fingernails
PRINT
CHECK              Twingun Morgan
TIP                Tip Info: has a body guard
CHECK              Slowdrawl Raul
TIP                Tip Info: is computer literate
QUIT

Data Structures

There is no upper bound to the number of suspects or number of attributes for a given suspect. You cannot use an array-based list to store the suspects or the attributes for a given suspect.
The CHECK operation must be very efficient, because suspects are continually being pulled off the street for questioning and we must decide whether to let them go or ruthlessly interrogate them. Using a simple linked list to store the suspects is not sufficient. You must use a binary search tree. Suspects must be actually deleted from the structure when they are eliminated by TIP information. Because you destroy the list of suspects, as suspects are eliminated by TIP information, each inquiry should work on a copy of the original tree.
TIP is executed much less often than CHECK and hence can be less efficient. It is acceptable if processing a TIP command requires searching the whole data structure of (active) suspects. Thus, a list of attributes can be stored with each suspect. You do not have to link all the suspects with the same attributes together. (This could potentially make for a much faster TIP operation.) You may do this if you want, but it complicates things.

Deliverables

Your design and CRC cards for any classes
A listing of any test driver necessary to check classes
A listing of the test plan for any class as input to the driver
A listing of the source code
A listing of the test plan as input to the program
A listing of the output from the test run

CISS 350 Programming Assignment 1 Checkout System
CISS 350 Programming Assignment 2 Computer Dating Service
CISS 350 Programming Assignment 3 Local Medical Clinic
CISS 350 Programming Assignment 4 Circular Linked List
CISS 350 Programming Assignment 5 Towers of Hanoi
CISS 350 Programming Assignment 6 Police Department
CISS 350 Programming Assignment 7 Compare Two Implementations of a Priority Queue

CISS 350 CISS350 CISS/350 ENTIRE COURSE HELP – COLUMBIA COLLEGE

CISS 350 Programming Assignment 5 Towers of Hanoi

Programming Assignment 5
Towers of Hanoi:
A toy that many children play with is a base with three pegs and five disks of different diameters. The disks begin on one peg, with the largest disk on the bottom and the other four disks added on in order of size. The idea is to move the disks from the peg they are on to another peg by moving only one disk at a time and without ever putting a larger disk on top of a smaller one. This child’s toy is actually an example of a classic mathematical puzzle.

Write a recursive solution to this problem. It may take you a while to see the solution, but the program itself is quite short.

Input
The program should prompt for and input the number of pegs.

Output
The series of moves should be written to the screen, properly labeled.

Deliverables

A listing of your program.
A listing of your test plan as input to the program.
A listing of the output file.
- CISS 350 Programming Assignment 1 Checkout System
- CISS 350 Programming Assignment 2 Computer Dating Service
- CISS 350 Programming Assignment 3 Local Medical Clinic
- CISS 350 Programming Assignment 4 Circular Linked List
- CISS 350 Programming Assignment 5 Towers of Hanoi
- CISS 350 Programming Assignment 6 Police Department
- CISS 350 Programming Assignment 7 Compare Two Implementations of a Priority Queue

CISS 350 CISS350 CISS/350 ENTIRE COURSE HELP – COLUMBIA COLLEGE

CISS 350 Programming Assignment 4 Circular Linked List

Programming Assignment 4
Implement the following specification of UnsortedType using a circular linked list as the implementation structure.

template <class ItemType>
struct NodeType;
/* Assumption:  ItemType is a type for which the operators 
"<" and "==" are defined—either an appropriate built-in type or a class that overloads these operators. */
template <class ItemType>
class UnsortedType
{
public:
  // Class constructor, destructor, and copy constructor
  UnsortedType();
  ~UnsortedType(); 
  UnsortedType(const UnsortedType<ItemType>&);
  void operator=(UnsortedType<ItemType>);
  bool IsFull() const;
  // Determines whether list is full.
  // Post: Function value = (list is full)
  int  GetLength() const;
  // Determines the number of elements in list.
  // Post: Function value = number of elements in list.
  void RetrieveItem(ItemType& item, bool& found);
  // Retrieves list element whose key matches item's key 
  // (if present).
  // Pre:  Key member of item is initialized.
  // Post: If there is an element someItem whose key matches  
  //     item's key, then found = true and item is a copy of
  //     someItem; otherwise found = false and item is 
  //     unchanged.
  //     List is unchanged.
  
void InsertItem(ItemType item); 
  // Adds item to list.
  // Pre:  List is not full.
  //       item is not in list. 
  // Post: item is in list.
  void DeleteItem(ItemType item);
  // Deletes the element whose key matches item's key.
  // Pre:  Key member of item is initialized.
  //       One and only one element in list has a key matching 
  //       item's key.
  // Post: No element in list has a key matching item's key.
  void ResetList();
  // Initializes current position for an iteration through the 
  // list.   
  // Post: Current position is prior to list.
  void GetNextItem(ItemType&);
  // Gets the next element in list.
  // Pre:  Current position is defined.
  //       Element at current position is not last in list.
  // Post: Current position is updated to next position.
  //       item is a copy of element at current position.
private:
  NodeType<ItemType>* listData;
  int length;
  NodeType<ItemType>* currentPos;
};

Deliverables

A listing of the specification and implementation files for UnsortedType
A listing of the driver program for your test plan
A listing of the test plan as input to the driver.
A listing of the output from the driver.
- CISS 350 Programming Assignment 1 Checkout System
- CISS 350 Programming Assignment 2 Computer Dating Service
- CISS 350 Programming Assignment 3 Local Medical Clinic
- CISS 350 Programming Assignment 4 Circular Linked List
- CISS 350 Programming Assignment 5 Towers of Hanoi
- CISS 350 Programming Assignment 6 Police Department
- CISS 350 Programming Assignment 7 Compare Two Implementations of a Priority Queue

CISS 350 CISS350 CISS/350 ENTIRE COURSE HELP – COLUMBIA COLLEGE

CISS 350 Programming Assignment 3 Local Medical Clinic

Programming Assignment 3
The local medical clinic has decided to automate its scheduling services. You have been assigned to design the initial version of the schedules. The basic functions that the clinic has in mind are doctor check-in and check-out and patient check-in and check-out.

A doctor checks in by telling the scheduler his or her name, an examination room number, and a medical specialty code. Each doctor has a favorite room. The scheduler checks to see whether the room is free. If so, it assigns this doctor to the room; if not, it rejects the request with a message, and the doctor can try again to check in. When a doctor checks out, the examination room is freed.

A patient checking in gives a name, age, specialist code, and emergency indication. The scheduler tries to match up the patient with a doctor according to a set of rules that are described here. If there is a match, the patient is seen by the assigned doctor. If this doctor is currently seeing a patient, the new patient is queued to see the doctor.

The rules for assigning doctors to patients are as follows:

Any patient under age 16 is assigned to see a pediatrician.
Patients age 16 and older are assigned a doctor according to the specialty requested. If there is no doctor in the clinic with the requested specialty, the patient is assigned to a general practitioner (GP). If there is no GP, the patient can be assigned to any doctor.
If there is more than one doctor of the requested specialty, the patient is assigned to the doctor with the shortest waiting list. When a patient checks out, the doctor he or she was assigned to is available to see the next patient, if there is anyone in the waiting list.

Input
Because this is an interactive system, your program should prompt the users to input the correct information.
The initial prompt is:
‘ Type D for Doctor or P for Patient:
‘ The next prompt is Type I for check-in or O for checkout: According to the request, your program should prompt the user for any other needed information, as indicated in the following table:
[table]
Action, Additional Information
Doctor check-in,Doctor’s name~~Room number~~Specialty code
Doctor check-out,Doctor’s name
Patient check-in,Patient’s name~~Age~~Specialty (code requested)
Patient check-out,Patient’s name~~Room number
[/table]
You may define the format for the input processed by your program.

Output
The output for each request is in the form of messages to the user, according to the request, as indicated in the following table.
[table]
Action, Message
Doctor check-in, Confirmation that room is available or Error message if room is in use.
Doctor check-out, Good-bye message
Patient check-in, “Message telling patient which room to go to and which doctor has been assigned. If no doctor is available, apologetic message.”
Patient check-out, “Good-bye message. At a later time we may add billing information at this point. In addition to printing the messages on the screen, you should also write the requests and messages to a transaction file (trans.out), to be turned in with your program listing.”
[/table]

Details and Assumptions

There are l 00 examination rooms at the clinic, each with a waiting room attached.
Specialty codes are as follows:
Pediatrics PED
General practice GEN
Internal medicine INT
Cardiology CAR
Surgeon SUR
Obstetrics OBS
Psychiatry PSY
Neurology NEU
Orthopedics ORT
Dermatology DET
Ophthalmology OPT
Ear, Nose, and Throat ENT
You may assume that no patient leaves without checking out. (That is, every doctor becomes free eventually.)
No one leaves before he or she sees the assigned doctor. (That is, no one has to be taken out of the waiting queue.) The clinic is open 24 hours a day, 7 days a week.
If a doctor checks out while there is still a waiting list of patients assigned to him or her, the patients must be reassigned to other doctors.

Data Structures
The basic data structure is a list of examination rooms with waiting lists attached to each. Because the number of rooms is fixed, you may use an array of records to represent it. It is the waiting list attached to each examination room that is of interest to us. We have seen that patients are seen in the order in which they are added to the list (a simple queue).

Deliverables

Your design including CRC cards for each class
A listing of your source program including all included files
A listing of your test plan as input to the program
A listing of your output from the test plan

CISS 350 Programming Assignment 1 Checkout System
CISS 350 Programming Assignment 2 Computer Dating Service
CISS 350 Programming Assignment 3 Local Medical Clinic
CISS 350 Programming Assignment 4 Circular Linked List
CISS 350 Programming Assignment 5 Towers of Hanoi
CISS 350 Programming Assignment 6 Police Department
CISS 350 Programming Assignment 7 Compare Two Implementations of a Priority Queue

CISS 350 CISS350 CISS/350 ENTIRE COURSE HELP – COLUMBIA COLLEGE

CISS 350 Programming Assignment 2 Computer Dating Service

Programming Assignment 2
Your assignment is to write a program for a computer dating service. Each client gives you his or her name, phone number, and a list of interests. It is your job to maintain lists of men and women using the service and to match up the compatible couples. You will find more details about the assignment, including the inputs, outputs, and deliverables in the course environment.

Input
Data about current clients should be on file “Clients.mf”. For each current client, the file contains the following information:

Sex 1 character, ‘M’ or ‘F’
Name up to 20 characters, followed by comma
Phone Number 8 characters
Number of Interests an integer
List of Interests 10 characters each separated by commas w/ a period after the final interest. Match up to 20 characters, followed by end-of-line.

Command Processing
[table]
,
NEWCLIENT, “(sex)(name)(number of interests)(interests) Add the client to the appropriate list by storing the appropriate information. Attempt to match this new client with a member of the opposite sex. A match occurs when the clients have three or more of the same interests. (You only have to find the first match for each new client.) Make sure you then designate both persons as matched, as described in the section on data structures above. Print the name of the new client, the name of his or her match, and both phone numbers. If no match is found, print an appropriate message.”
UNMATCH, Unmatch this name with his or her current match by removing from the matched person.
PRINTMATCH, Print a list of all matched pairs.
PRINTFREE, Print the names and phone numbers of clients who are not currently matched.
QUIT, Stop processing
[/table]

Output
Echo print all screen input and output on file “Dates.out.”

Data Structures
The problem requires you to maintain two lists of clients, one for men and one for women. When a new client is added to the list, he or she is added to the end of the appropriate list.
Each list element must include all the information for one client: name, phone number, number of interests (maximum number is 10), interests, and the name of this client’s current match (empty string if not matched). You must use one of the list classes developed in Chapter 3.

Deliverables

Your design.
A listing of your program.
A listing of your test plan as input to the program.
A listing of the output file.

CISS 350 Programming Assignment 1 Checkout System
CISS 350 Programming Assignment 2 Computer Dating Service
CISS 350 Programming Assignment 3 Local Medical Clinic
CISS 350 Programming Assignment 4 Circular Linked List
CISS 350 Programming Assignment 5 Towers of Hanoi
CISS 350 Programming Assignment 6 Police Department
CISS 350 Programming Assignment 7 Compare Two Implementations of a Priority Queue

CISS 350 CISS350 CISS/350 ENTIRE COURSE HELP – COLUMBIA COLLEGE

CISS 350 Programming Assignment 1 Checkout System

Programming Assignment 1
You will write, run, and test a C++ program to simulate the operation of a grocery store checkout system. Your program should first build a data structure to contain information on all the products available in the store. Then the program should print the cash register receipt for each customer.

Input
The input for this program has two sources: the inventory information is input from a text file, and the customer transactions are input from the keyboard.

The information about each product carried by the store is listed on a single line in the inventory file “Invent.dat”, in the following format:
(product number) (description) (price) (tax)
where is a five-digit positive (nonzero) integer, is a string of at most 12 characters with no embedded blanks, is a real number, and is a character (‘T’ if the product is taxable; ‘N’ if it is not taxable). The data in the inventory file is ordered from smallest to largest product number.
The customer transactions are input from the keyboard, in the following format:
(product number) (times)
where (product number) is as described above, and (times) is an integer in the range 1 to 100, indicating the quantity of this product desired. A zero input for (product number) indicates the end of the customer’s order. (The store will soon be using a scanner to input the product number, but for now it is typed in by the cashier.)

Output
The program outputs should be written to a text file called “Receipts.out.”

The inventory information is echo printed to the output file.
The cash register receipt for each customer is written to the output file. The receipts should be nicely formatted, with the product description (not the product number), number of items, item price, and total price for each product printed on a single line. At the end of each customer’s order, the subtotal for all items, amount of tax on taxable items, and total bill should be printed, clearly labeled. (The tax rate is 7.5% for taxable items.)

Processing

The program first reads in all of the inventory information from file “Invent.in.” echo printing the information to the output file.
The program then prompts the cashier to begin inputting the order for the first customer.
This customer’s order is processed, and the receipt is printed to the output file.
After each customer’s order is processed, the program should ask the cashier if another customer is to be processed. If the answer is ‘Y’, the program sets up to process the next customer; if the answer is ‘N’, the program terminates with a friendly message.

Error Checking
The following input errors are possible and should be handled by an exception class:

Duplicate in inventory file. Write an error message to the output file and skip the second entry.
not in inventory file. Write an error message on the receipt, ignore that product number, and continue with the next item.
not in the specified range. Write an error message to the output file, ignore that line, and continue with the next item.

Example
From File “Invent.in”:
11012 gallon-milk 1.99 N
11014 butter 2.59 N
11110 pie-shells 0.99 N
20115 laundry-soap 3.60 T
30005 homestyle-br 0.99 N

From keyboard (one customer):
11110 2
40012 3
20115 1
0

To “Receipts.out” file:
——————————————————
SEP 10, 1998 6:00 pm (* date and time optional *)
Customer 1
pie-shells 2 @ 0.99 1.98
*** item 40012 not in inventory ***
laundry-soap 1 @ 3.60 3.60 TX
Subtotal 5.58
Tax 0.27
Total 5.85

Data Structures
The inventory information can be stored in an array of product records. Assume that the maximum number of products is 50, for purposes of writing this program. You should specify this data structure as an ADT, as described in the chapter; define and implement a set of operations to encapsulate it. The ADT should be tested using a test driver.

Deliverables

Your design (either object-oriented or top-down)
A listing of the ADT
A listing of the test driver for the ADT
A listing of the test plan as input for the driver
A listing of the output from the test driver
A listing of your program
A listing of your test plan as input to the program
A listing of the output file.

CISS 350 Programming Assignment 1 Checkout System
CISS 350 Programming Assignment 2 Computer Dating Service
CISS 350 Programming Assignment 3 Local Medical Clinic
CISS 350 Programming Assignment 4 Circular Linked List
CISS 350 Programming Assignment 5 Towers of Hanoi
CISS 350 Programming Assignment 6 Police Department
CISS 350 Programming Assignment 7 Compare Two Implementations of a Priority Queue

New Solution: CISS 350 CISS350 CISS/350 ENTIRE COURSE HELP – COLUMBIA COLLEGE