Algorithms Homework 4 List and explain the three characteristics that all recursive modules must have

Confidential Teaching Materials

Homework 4 Criteria, Page 1 of 11

Homework 4 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] 9 points

List and explain the three characteristics that all recursive modules must have.

[c1] 9 points

GRADING:

[p2] 15 points

Identify all of the errors in the following code. Note that there may be no errors.

function Compute_Sum returnsa Num (end_number isoftype in/out Num)

// computes the sum of all numbers between 1 and end_number,

// inclusive.

if (end_number != 1) then

Compute_Sum returns end_number + Compute_Sum (end_number)

endif

endfunction

[c2] 15 points

Sample Solution:

GRADING

Confidential Teaching Materials

Homework 4 Criteria, Page 2 of 11

Premise for Problems 3 through 11:

The professor needs the following abilities for the system:

* Add a new reading – prompts the user to enter all of the information about a reading, then

adds the reading to the end of the linked list.

All dates will be stored using the following data structure:

Date_Record definesa record

You may also assume that the following modules have been written for you. You may use these

freely without writing the code for them.

procedure Read_Date (date_to_read isoftype out Date_Record)

// prompts the user to enter each part of the date, reads in each

Confidential Teaching Materials

[p3] 6 points

Declare the necessary data structure to hold all of the information for ONE meter reading.

[c3] 6 points

Sample Solution:

GRADING:

-2 for not having “Meter_Reading_Rec definesa record”

[p4] 13 points

Write a module that is passed a meter reading record (from the previous problem) as a parameter

and prints all of the information about the reading. Sample output:

Date: 01/29/1998

Time: 1200

Reading: 15

By: George Jetson

[c4] 13 points

Sample Solution:

GRADING:

-1 for not making it a procedure (pro)

-0.5 for not making it an in (inp)

Confidential Teaching Materials

Homework 4 Criteria, Page 4 of 11

[p5] 12 points

Write a module that fills in a meter reading record and passes it back to the calling module. Your

module should prompt the user for each item in a meter record.

[c5]12 points

Sample Solution:

GRADING:

-1 for not making it a procedure (pro)

-0.5 for not making it an out (oup)

-0.5 (x4) for not prompting the user (wro)

[p6] 5 points

Declare the necessary data structure for a linked list of meter readings.

[c6]5 points

Sample Solution:

Confidential Teaching Materials

Homework 4 Criteria, Page 5 of 11

GRADING:

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

If they did not use Meter_Reading_Rec as their data field and re-copied the stuff

in Meter_Reading_Rec, deduct 3 points (pda).

[p7] 15 points

Write a module that, given an already-filled-in meter reading record and a pointer to the head of a

linked list of readings as parameters, adds the reading record to the end of the linked list.

[c7] 15 points

Sample Solution:

procedure Add_Reading (head isotype in/out ptr toa Reading_LL_Rec,

GRADING:

-1 for not having the head parameter (npo)

-0.5 for not making it a pointer (ptr)

-0.5 for not making it an in (inp)

-2 for not checking for the terminating condition (NIL) (nto)

-1 if they did not use new ( Reading_LL_Rec) or equiv. (rec)

-2 for not assigning NIL to next (log)

Confidential Teaching Materials

Homework 4 Criteria, Page 6 of 11

[p8] 15 points

Write a module that is passed a reading value and a pointer to the head of a reading linked list as

parameters and prints all readings in the list that are greater than or equal to the given reading

value. If no readings meet this criteria, your module should not print anything.

[c8] 15 points

Sample Solution:

procedure Print_High_Reading (cutoff_value isoftype in num,

head isoftype in ptr toa

GRADING:

-1 for not making it a procedure (pro)

-0.5 for not making it an in (inp)

-1 for not having the cutoff_value parameter (npo)

-0.5 for not making it a Num (num)

-3 for not checking if the current node’s reading

is high enough (nto wrt)

-3 for not printing the data (wro)

[p9] 15 points

Write a module that, given a pointer to the head of a linked list and a date record, deletes all

records in the linked list that were made on that day. If there are no readings in the list for the

given day, your module should leave the list unaffected.

[c9] 15 points

Sample Solution:

Confidential Teaching Materials

Homework 4 Criteria, Page 7 of 11

procedure Delete_Readings (head isotype in/out ptr toa

GRADING:

-1 for not having the head parameter (npo)

-0.5 for not making it a pointer (ptr)

-0.5 for not making it an in (inp)

-3 for not checking for NIL (nto)

-3 for not setting head <- head^.next when dates are equal (log)

-2 for not recursing with head^.next otherwise (rsr)

[p10] 30 points

Write the main algorithm to tie all of these modules together and meet the above requirements

specification. Your algorithm should present the professor with a menu:

1 – Add a new reading

2 – Delete all readings for a given date

3 – Print all readings

4 – Print all of the readings above a certain value

5 – Quit

The algorithm should read in the professor’s selection, process it according to the specifications

given above, and then re-display the menu until he selects the quit option. Note that you may use

helper modules in addition to the algorithm to meet the requirements given above.

[c10] 30 points

Sample Solution:

Confidential Teaching Materials

Homework 4 Criteria, Page 8 of 11

procedure Menu (selection isoftype out num)

Confidential Teaching Materials

Homework 4 Criteria, Page 9 of 11

GRADING:

There are several ways of doing this, so use the critera as a guide

and contact instructor with any specific questions.

-5 if they didn’t have a menu procedure (ppa)

-0.5 for not making it a procedure (pro)

-1 for not checking for NIL (wrt nto)

-0.5 if they did not use the

Print_Reading_Data procedure (ppa)

-2 for not taking care of the pre-conditions

Confidential Teaching Materials

Homework 4 Criteria, Page 10 of 11

[p11] 30 points

You have been hired by a bank to design a new system to keep track of all of their accounts. The

accounts should be stored in a linked list; each account has the following information associated

with it:

* Account Number

* Account Holder Name

* Account Holder Social Security Number

* Date opened

* Transaction list

The transaction list is a linked list of transactions for the account. Each transaction contains the

following information:

* Date

* Type (credit or debit)

* Amount

The bank desires the following functionality:

* Add a new account – reads in information about the new account from the user and adds the

account to the account linked list.

* Close an account – reads in an account number from the user, then deletes the given account

from the linked list of accounts.

* Add a transaction – given an account number and a transaction record, adds the transaction

to the account’s transaction list.

* Display account balance – displays the balance for an account number that the user enters.

* Display all accounts that are overdrawn – displays the account number and balance for all

accounts that have a balance less then zero.

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.

[c11] 30 points

Confidential Teaching Materials

Homework 4 Criteria, Page 11 of 11