Algorithms Homework 6 You have been hired by an airline to design a system to keep track of their flights

Confidential Teaching Materials

Homework 6 Criteria, Page 1 of 15

Homework 6 Grading Criteria

Note: To receive any credit whatsoever, your answers must be legible and readily readable in the

judgment of the grader. Add brief explanatory comments as necessary to make sure your answers

are clear and unambiguous to the grader.

[p1] 100 points

Last week, you were asked to design a system to keep track of airline flights. Here is the problem description

again:

You have been hired by an airline to design a system to keep track of their flights. Each flight has the following

information associated with it:

* Flight number

* Date

* Time

* Plane number

* Originating City

* Destination City

* Passenger Information

Each passenger has the following information:

* Passenger ID number

* Name

* Frequent Flyer Number

* Seat Number

* Class (first class or coach)

You should store the flights as a binary search tree sorted on flight number; the passenger information should be

stored in a linked list within each flight node.

The airline wishes to be able to perform the following functions:

1. Add a flight – asks the user for information on a new flight and adds it to the binary search tree by flight

number. When the flight is first added to the tree, the passenger list should be set to nil.

2. Add a passenger to a flight – prompts the user for a flight number and passenger information, then adds

the passenger information to the appropriate flight.

3. Remove a passenger from a flight – given a passenger ID and a flight number, removes the given

passenger from the passenger list of the flight.

4. Cancel a flight – removes a given flight from the tree.

5. Print passenger list for a flight – prints out a list of all of the passengers for a given flight number

(entered by the user).

Using your design from last week, write all of the data structures, procedures, functions, and main algorithm to

implement this system. Your system should display a menu

Confidential Teaching Materials

with the 5 functions above (plus a “quit” option), read a selection from the user, process the selection, and then

re-display the menu until the quit selection is taken.

NOTE: You DO NOT have to implement selection 5 from the menu. Just include the appropriate module

header(s) and purpose comments, but the actual code for deleting an item from a tree is not necessary.

If you wish to implement some modules that were not present in your design last week, please document this fact

in the module’s purpose comments.

[c1] 100 points

Sample Solution:

//

// data structures

//

Passenger_Rec definesa record

passenger_id isoftype num

name isoftype string

freq_flyer_num isoftype num

seat_num isoftype num

plane_num isoftype num

orig_city isoftype string

dest_city isoftype string

passenger_list isoftype ptr toa Passenter_List

endrecord

//

print (“Enter class: “)

read (pass.class)

endprocedure

procedure Get_Flight_Info (flight isoftype out Flight_Rec)

print (“Enter flight number: “)

Homework 6 Criteria, Page 3 of 15

read (flight.orig_city)

print (“Enter destination city: “)

read (flight.dest_city)

passenger_list <- NIL

endprocedure

//

else

Add_Flight (flight_tree^.right, new_flight)

endif

endprocedure

procedure Add_Passenger (passenger isoftype in Passenger_Rec,

if (flight_tree^.data.flight_num = flight_num)

Get_Passlist_For_Flight returns flight_tree^.data.pass_list

elseif (flight_tree^.data.flight_num > flight_num) then

Print_Passlist_For_Flight (flight_tree^.left, flight_num)

else

Confidential Teaching Materials

passlist <- Get_Passlist_For_Flight (flight_tree, flight_num)

if (passlist != NIL)

Add_Passenter (pass, passlist)

end

endprocedure

procedure Remove_Passenger_From_Flight (flight_tree isa ptr toa

Flight_Tree, flight_num isoftype in num,

pass_id isoftype in Num)

passlist isoftype ptr toa Passenger_List

exitif (passenger_list = NIL)

print (passenger_list^.data.name)

passenger_list <- passenger_list^.next

endloop

endprocedure

print (“4. Cancel a flight”)

print (“5. Print passenger list for a flight”)

print (“6. Quit”)

read (sel)

endprocedure

Homework 6 Criteria, Page 5 of 15

exitif (sel == 6)

if (sel = 1)

Get_Flight_Info (temp_flight)

Add_Flight (flight_tree, temp_flight)

elseif (sel = 2)

elseif (sel = 4)

Get_Flight_Num (temp_flightnum)

Remove_flight (flight_tree, temp_flightnum)

GRADING:

*** There are many, many ways of doing this problems correctly. Use the criteria as a guide

and mail any specific questions to the instructor.

Data Structures (17 points)

~~~~~~~~~~~~~~~

Passenger record (3.5 points)

-0.5 (x5) for each missing field or wrong type (nav etc.)

Flight record (4.5 points)

-0.5 (x7) for each missing field or wrong type (nav etc.)

Passenger list

Confidential Teaching Materials

Homework 6 Criteria, Page 6 of 15

-2 for not having a “data” field (pda)

-1 for not having a right pointer (ptr)

-1 for not making it a procedure (pro)

-0.5 for not making it an out (oup)

-1 (x5) for each wrong read (ird)

-0.5 for incorrectly accessing record (uri)

-1 for no parameter (npo)

-0.5 for not making it a record (rec)

-0.5 for incorrectly accessing record (uri)

-1 for not setting passenger list to NIL (ibu)

-1 for no flight_tree parameter (npo)

-0.5 for not making it a pointer (ptr)

-0.5 for not making it an in (inp)

-1 for not checking for NIL first (wrt dnp)

-1 for not assigning data field of new node (ibu)

-1 for not checking to go left or right (wrt)

-1 for not going right where appropriate (log)

Confidential Teaching Materials

Remove_Flight (3 points)

-1 for not making it a procedure (pro)

-0.5 for not making it in/out (iop)

-1 for no flight_to_delete parameter (npo)

-0.5 for not making it a num (rec)

-1 for not making it a procedure (pro)

-0.5 for not making it an “in” (inp)

-1 for de-referencing NIL (dnp)

-1 for not going to next passenger (wro)

Add_Passenger (7 points)

~~~~~~~~~~~~~~~~~~~~~~~~

-1 for not making it a procedure

-0.5 for wrong type

-4 for not adding the node to the list (log)

-1 for not inserting node (log)

-1 for not assigning data field of new node (log)

Remove_Passenger (7 points)

~~~~~~~~~~~~~~~~~~~~~~~~~~~

-1 for not making it a procedure

-0.5 for wrong type

-4 for not removing the node properly (log)

Confidential Teaching Materials

-1 for not checking for NIL first (dnp)

-1 for not removing current if necessary (log)

-1 for not going to next node otherwise (log)

Get_Passlist_For_Flight (10 points)

~~~~~~~~~~~~~~~~~~~~~~~

-0.5 for not making it return a pointer (ptr)

-1 for not checking for NIL first (dnp)

-1 for returning current node where appropriate (ret)

-1 for not returning NIL if the node was not found (ret)

Add_Passenger_To_Flight (7 points)

~~~~~~~~~~~~~~~~~~~~~~~

-1 for not making it a procedure (pro)

-1 for not somehow obtaining the passenger list of flight (log)

-1 for not calling other procedure to add passenger (pci)

Remove_Passenger_From_Flight (6 points)

~~~~~~~~~~~~~~~~~~~~~~~~~~~~

-1 for not making it a procedure (pro)

-1 for not somehow obtaining the passenger list of flight (log)

-1 for not calling other procedure to remove passenger (pci)

Menu procedure

~~~~~~~~~~~~~~

Main Algorithm

~~~~~~~~~~~~~~

Confidential Teaching Materials

Homework 6 Criteria, Page 9 of 15

-1 for not setting the main flight_tree to NIL first (ibu)

For each selection:

-1.5 for not calling all appropriate modules (log)

[p2] 10 points

Explain the difference between recursion and iteration. Give at least one example of when each should be used.

[c2] 10 points

Sample Solution:

[p3] 10 points

Define a 2-dimensional array of numbers. Your array should have 4 rows and 3 columns.

[c3] 10 points

Sample Solution:

GRADING:

-1 for not having “… defines array ” (arr)

-3 (x2) for doing 2-D part wrong (arr)

-1 for not making the array of num’s (num)

Confidential Teaching Materials

Homework 6 Criteria, Page 10 of 15

[p4] 15 points

Write a module that is passed a 2-dimensional array (from problem 2) as a parameter and returns the sum of all

of the numbers in the array.

[c4] 15 points

Sample Solution:

GRADING:

-0.5 for not making the function return a num (num)

-0.5 for not making the parameter an in (inp)

-0.5 (x3) for each missing temp variable (nav)

-0.5 for not initializing row_lcv to 1 (ibu)

-2 for wrong exitif condition (wrt)

-1 for no inner loop/endloop (nal)

-0.5 for not adding to total (log)

-1 for not incrementing outer lcv (nai)

-0.5 for not returning total (ret)

Confidential Teaching Materials

[p5] 18 points

Write a module that prints the sum of each row in a 2-dimensional array (as defined in problem 2). The array

will be passed to the module as a parameter. Your output should correspond to the example below. For

example, if the array passed to the module looked like:

1 5 9

2 6 10

3 7 11

4 8 12

Your module should print:

Row 1: 15

Row 2: 18

Row 3: 21

Row 4: 24

[c5] 18 points

Sample Solution:

procedure Print_Row_Totals (arr isoftype in Two_D_Array)

GRADING:

-1.5 for missing parameter (npo)

-1 for not making the parameter a Two_D_Array (arr)

-0.5 for not initializing row_lcv to 1 (ibu)

-2 for wrong exitif condition (wrt)

-1 for not setting col_lcv to 1 inside loop (ibu log)

Confidential Teaching Materials

Homework 6 Criteria, Page 12 of 15

-1 for no inner loop/endloop (nal)

-0.5 for not adding to total (log)

-1 for not printing total after inner loop (wro)

-0.5 for not returning total (ret)

[p6] 15 points

Discuss three advantages the use of object-oriented programming offers over regular procedural programming.

[c6] 15 points

Sample Solution:

[p7] 10 points

Explain the purpose of the public section and the private section with respect to classes.

[c7] 10 points

Sample Solution:

GRADING:

[p8] 30 points

Write a class for a Person. The class should hold the following attributes:

* Name

* Age

* Social security number

* Birthday

* Hair color

Confidential Teaching Materials

All of this data should be stored in the private section of your class; the public section should contain the

appropriate accessor modules to set and get the information. (i.e. you might have modules called Get_Name and

Set_Name to return the name from within the class and to set the name in the class, respectively)

[c8] 30 points

Sample Solution:

class Person

public:

procedure SetName (in_name isoftype in String)

procedure SetAge (in_age isoftype in Num)

procedure SetSSN (in_ssn isoftype in Num)

procedure SetName (in_name isoftype in String)

name <- in_name

endprocedure

procedure SetAge (in_age isoftype in Name)

endfunction

function GetAge returnsa Num ()

GetAge returns age

endfunction

function GetSSN returnsa Num ()

Confidential Teaching Materials

Homework 6 Criteria, Page 14 of 15

GRADING:

-0.5 for no purpose comments (pcn)

-0.5 for making it the wrong type (str num)

-0.5 if they didn’t copy the header from the public (log)

section

[p9] 15 points

Write a class for a Student. A student is a person, so it should have all of the features of the person class, plus

the following:

* Major

* GPA

* Class (freshman, sophomore, etc.)

Again, this information should be contained in the private section of your class; use accessor functions to

retrieve manipulate the information.

[c9] 15 points

Sample Solution:

class Student

inherits Person

public:

procedure Set_Major (in_major isoftype in String)

procedure Set_GPA (in_gpa isoftype in Num)

Confidential Teaching Materials

Homework 6 Criteria, Page 15 of 15

procedure Set_GPA (in_gpa isoftype in Num)

gpa <- in_gpa

endprocedure

GRADING:

-1.5 (x6) for each missing header (pro fun)

-1 (x3) for each missing protected variable (nav)

-0.5 (x6) for each module that does not do the right thing (log)