Algorithms Homework 5 You have been hired by a library to develop a book management system

Confidential Teaching Materials

Homework 5 Criteria, Page 1 of 11

Homework 5 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] 15 points

Each of the following code segments contain a single error. Identify the error, explain why it is an error, and

write a corrected code segment. The following error-free linked list definition applies to all three segments:

List_Node definesa record

data isoftype Num

next isoftype ptr toa List_Node

endrecord

a) procedure Add_To_Front (head isoftype in/out ptr toa List_Node,

data_to_add isoftype in Num)

temp isoftype ptr toa List_Node

temp <- new (List_Node)

temp^.data <- data_to_add

temp^.next <- head^.next

head <- temp

endprocedure

(b) procedure Delete_Last_Node (head isoftype in/out ptr toa List_Node)

if (head^.next = NIL) then

head <- NIL

else

Delete_Last_Node (head^.next)

endif

endprocedure

(c) procedure Add_to_End (head isoftype in/out ptr toa List_Node,

data_to_add isoftype in Num)

if (head = NIL) then

head^.data <- data_to_add

head^.next <- NIL

else

Add_To_End (head^.next, data_to_add)

endif

endprocedure

[c1] 15 points

Confidential Teaching Materials

Homework 5 Criteria, Page 2 of 11

GRADING:

Premise for Problems 2 through 8.

You have been hired by a library to develop a book management system. Each book in the library has the

following information:

* ISBN (a number that uniquely identifies the book)

* Title

* Author

* Copyright year

* Total quantity

* Quantity on hand

Books should be stored in a binary search tree, arranged by ISBN. The library desires the following capabilities:

* Add a new book – prompts the user for ISBN, title, author, copyright year, and total quantity, then adds

the book to the database (BST of books). The “quantity on hand” field should be set to 0 when a new book

is added.

* Find book – the user enters a ISBN. The BST is then searched, and all information about the book

corresponding to the ISBN is printed. If no book for the given ISBN exists, “No book found” is printed.

* Check out book – the user enters a ISBN. The book is then retrieved, and it’s “quantity on hand” field is

decremented. (You may assume that if the user wishes to check out a book, there will always be one

available.) If the given ISBN is not found in the tree, “Book not found” should be printed.

Confidential Teaching Materials

[p2] 5 points

Declare the necessary data structure to hold information on ONE book.

[c2] 5 points

Sample Solution:

[p3] 5 points

Declare the necessary data structure for a binary search tree of books.

[c3] 5 points

Sample Solution:

GRADING:

-2 for not having the “… definesa record” part (rec)

[p4] 10 points

Write a module that will print out information on a single book. The module will be passed a book record

(defined in problem 2), and print out all information on the book (author, title, etc.)

[c4] 10 points

Sample Solution:

procedure Print_Book_Record (book isoftype in Book_Record)

Confidential Teaching Materials

GRADING:

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

[p5] 20 points

Write a module to add a new book to the tree. The module should take as parameters an already-filled-in book

record and a pointer to the root of the library tree, and add the book in the appropriate place based on its ISBN.

[c5] 20 points

Sample Solution:

procedure Add_Book (new_book isoftype in Book_Record,

GRADING:

-2 for not making it a procedure (pro)

-1 for omitting the new_book parameter ( npo)

Confidential Teaching Materials

-2 for not recursing (rsr)

-1 for not recursing in the right direction (log)

-2 for not comparing record fields properly (wrt)

[p6] 20 points

Write a module that will return a pointer to information on a book given it’s ISBN (i.e., a pointer to a book

record). Your module should take in an ISBN and a pointer to the root of the library tree

as parameters, search the tree for the given book, and return a pointer to the book record once the book is found.

If the book is not found in the tree, then the module should return NIL.

[c6] 20 points

Sample Solution:

function Get_Book_Ptr returnsa ptr toa Library_Tree (isbn isoftype

GRADING:

-1 for not making the function return a pointer ( ptr)

-0.5 for not making it an in (inp)

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

-2 for not seeing if isbn’s are equal (nto)

Confidential Teaching Materials

Homework 5 Criteria, Page 6 of 11

-2 for not checking to go to the right (wrt)

-2 for not recursing with proper parameter (rsr npo)

[p7] 20 points

Write a module that will print information on a book given the book’s title. The book’s title and a pointer to the

root of the library tree will be passed to your module as parameters; the tree should be searched for the title, and

when the corresponding book is found, its information should be printed. If the book is not found in the tree, then

nothing should be printed.

[c7] 20 points

Sample Solution:

procedure Print_Book_Info (book_title isoftype in string,

GRADING:

-1 for not making it a procedure (pro)

-0.5 for not making it an in (inp)

-1 for no root parameter (npo)

-0.5 for not making it a pointer (ptr)

-3 for not checking if the current should be printed ( nto)

[p8] 60 points

Write the main algorithm and any supporting modules necessary to complete the system specifications given

above. You may use any of the modules you wrote in previous problems without re-copying them.

Confidential Teaching Materials

Homework 5 Criteria, Page 7 of 11

[c8] 60 points

Sample Solution:

procedure Menu (selection isoftype out Num)

print (“1 – Add a new book “)

print (“2 – Find book “)

print (“3 – Check out book “)

print (“4 – Check in book “)

Confidential Teaching Materials

Homework 5 Criteria, Page 8 of 11

GRADING:

There are several ways that this problem can be done correctly. Use this criteria as a general

guide, and e-mail any specific questions to the instructor.

-6 for not having an InOrder traversal procedure (ppa)

-1 for not initializing the the tree to NIL (ibu)

Selection processing:

If they did not use the Get_Book_Ptr for selections 2 – 4, deduct 2 points each for PPA.

[p9] 10 points

Explain the difference between a static and a dynamic data structure. Give an example of when each is best.

[c9] 10 points

[p10] 30 points

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

Confidential Teaching Materials

Homework 5 Criteria, Page 9 of 11

* 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).

Your job is to provide a design for these specifications. In your design, you should include all data structures and

module headers (including purpose comments) that the system will require. YOU DO NOT HAVE TO WRITE

ANY CODE FOR THE MODULES.

[c10] 30 points

There are many ways to do this one. Use the criteria as a guide, and e-mail specific questions

to the instructor.

Confidential Teaching Materials

Homework 5 Criteria, Page 10 of 11

-1 for not making it the proper module type (pro fun)

-1 for no purpose comments. (pcn)

[p11] 5 points

Declare an array data structure to hold 10 numbers.

[c11] 5 points

Sample Solution:

[p12] 10 points

Write a module that fills in an array of 10 numbers with input from the user and passes the filled-in array back to

the calling module.

[c12] 10 points

Sample Solution:

Confidential Teaching Materials

Homework 5 Criteria, Page 11 of 11

GRADING:

-1 for not having the parameter (npo)

-0.5 for not making it an array (arr)

-2 for no loop/endloop (nal)

-1 if they did not use a constant in test (con)

[p13] 10 points

Write an iterative module that will print out all elements in an array of 10 numbers.

[c13] 10 points

Sample Solution:

GRADING:

-1 for not making it a procedure (pro)

-0.5 for not making it an in (oup)

-1 for not having a loop control variable (nav)

-2 for wrong exitif condition (wrt)