ITI 1220 Fall 2005 - Assignment 4

Available: Friday September 30
Due: Tuesday October 11, noon (NOTE:  Unusual day due to Thanksgiving holiday)

Instructions

This assignment is to be done in TEAMS OF TWO PEOPLE. The assignment should be submitted only once by a member of your team, but please ensure that the identification material contains the information for both team members. Follow the instructions in the lab manual for submitting assignments.

Your algorithms should be developed using the format used in class. Your algorithm traces should use the format shown in class; a separate table is to be used for each call to each algorithm. Programs should be based on the template file, and should follow good coding practices as described in the course lab manual.

Marking Scheme (total 100 marks)

Question 1 (10 marks)

In this question, you should use the algorithm format for Boolean expressions.  Keep in mind the difference between a Boolean expression, and a test used in a branch or loop.  You need only to write the expression (example:  A ≤ (B + 3) ), and not a branch structure.

 

The Boolean expressions that you write for this question should use only the comparison operators (<, >, =, etc.), Boolean operators (AND, OR, NOT), and math operators +, –, ×, /, or MOD.  Use parentheses where necessary.


Question 1a)

 

Student participants in the 2005 ACM intercollegiate programming contest must satisfy the criteria listed below, based on the following variables for a student:  IsFullTimeStudent, PreviousContestParticipations, FirstUniversityYear, Age, and NumberOfSemesters.

 

The eligibility criteria are:

 

 

Write a Boolean expression that will be true if a student can participate in the contest, and false otherwise.

 

IsFullTimeStudent AND PreviousContestParticipations ≤ 5 AND (FirstUniversityYear ≥ 2001 OR Age < 24 OR NumberOfSemesters ≤ 8)

 

Question 1b)

 

Suppose that you have three numbers A, B, and C, which are greater than zero.  Write a Boolean expression that is true if any of the three numbers is evenly divisible by at least one of the other two numbers.

 

(A MOD B = 0) OR (A MOD C = 0) OR (B MOD A = 0) OR (B MOD C = 0) OR (C MOD A = 0) OR (C MOD B = 0)

 

Question 2 (10 marks)

In this question, you should use the Java format for Boolean expressions.  Keep in mind the difference between a Boolean expression, and a test used in an if statement.  You need only to write the expression (example:  A <= (B + 3) ), and not the complete if statement..

 

The Java Boolean expressions that you write for this question should use only the comparison operators (<, >, ==, etc.), logical operators (&&, ||, !), and math operators +, –, *, /, or %.  Use parentheses where necessary.

 

Question 2a)

 

Suppose that day is an integer variable with value 1 through 7, where 1 represents Sunday, 2 represents Monday, and so on through to 7 representing Saturday.  Another variable, hour, is an integer from 0 to 23.  Finally, there is a Boolean variable holiday, which is true on days that are holidays.

 

The ITI 1220 professor is usually on campus from 10 a.m. until 7 p.m. on Mondays through Fridays, except on holidays.  Write a Boolean expression that is true if the ITI 1220 professor would be on campus, and false otherwise.

 

(day >= 2 ) && (day <=6) && (hour >= 10) && (hour <= 19) && ! holiday

 

Question 2b)

 

The rules for passing the course ITI 1220/1620 are as follows:

 

 

Suppose that you have the variables assignAverage, midterm, and exam representing the corresponding values for a student and all three values are numbers between 0.0 and 100.0.  Write a Boolean expression that will be true if the student passes the course, and false otherwise.

 

(0.25 * assignAverage + 0.2 * midterm + 0.55 * exam >= 50.0) && (0.2 * midterm + 0.55 * exam >= 37.5 )


Question 3 (30 marks)

 

Implement the following algorithm in Java:

 

GIVENS:

            Income                                                (a person’s taxable income, in dollars)

 

RESULTS:

            Tax                                                      (amount of federal tax)

 

HEADER:

            Tax ← CalculateFederalTax( Income )

 

ASSUMPTIONS:

            Income is greater than or equal to zero.

 

CONSTRAINTS:

            Make sure that Base1 through Base4 are increasing amounts.

 

INTERMEDIATES:

            Base                                                   (base amount for income bracket, line 2 of table)

            Rate                                                    (tax rate for income in excess of base amount, line 4 of table)

            BaseTax                                             (tax on base amount, line 6 of table)

            Base1                                                 (CONSTANT:  base amount in column 1)

            Rate1                                                  (CONSTANT:  tax rate in column 1)

            BaseTax1                                          (CONSTANT:  base tax in column 1)

            Base2                                                 (CONSTANT:  base amount in column 2)

            Rate2                                                  (CONSTANT:  tax rate in column 2)

            BaseTax2                                          (CONSTANT:  base tax in column 2)

            Base3                                                 (CONSTANT:  base amount in column 3)

            Rate3                                                  (CONSTANT:  tax rate in column 3)

            BaseTax3                                          (CONSTANT:  base tax in column 3)

            Base4                                                 (CONSTANT:  base amount in column 4)

            Rate4                                                  (CONSTANT:  tax rate in column 4)

            BaseTax4                                          (CONSTANT:  base tax in column 4)

 

 

BODY:

 

 

// ITI 1220 Fall 2005, Assignment 4, Question 3

// Name: Alan Williams, Student# 81069665

 

import java.util.Scanner;

 

/**

 * This program calculates the federal tax payable for a person with a specified

 * taxable income.

 */

 

class A3Q1a

{

      public static void main( String[] args )

      {

            // SET UP KEYBOARD INPUT

 

            Scanner keyboard = new Scanner( System.in );

 

            // DECLARE VARIABLES/DATA DICTIONARY

 

            double income;      // GIVEN:        taxable income for a person

 

            double tax;         // RESULT:       amount of federal tax

            double averageRate; // RESULT:       average rate of tax

 

            double rate;        // INTERMEDIATE: the rate selected for the tax calculation

            double base;        // INTERMEDIATE: the selected base amount

            double baseTax;     // INTERMEDIATE: tax on the selected base amount

 

            double rate1;       // INTERMEDIATE: (constant) tax rate for column 1 of tax table

            double base1;       // INTERMEDIATE: (constant) base amount for column 1 of tax table

            double baseTax1;    // INTERMEDIATE: (constant) tax on base amount for column 1 of tax table

            double rate2;       // INTERMEDIATE: (constant) tax rate for column 2 of tax table

            double base2;       // INTERMEDIATE: (constant) base amount for column 2 of tax table

            double baseTax2;    // INTERMEDIATE: (constant) tax on base amount for column 2 of tax table

            double rate3;       // INTERMEDIATE: (constant) tax rate for column 3 of tax table

            double base3;       // INTERMEDIATE: (constant) base amount for column 3 of tax table

            double baseTax3;    // INTERMEDIATE: (constant) tax on base amount for column 3 of tax table

            double rate4;       // INTERMEDIATE: (constant) tax rate for column 4 of tax table

            double base4;       // INTERMEDIATE: (constant) base amount for column 4 of tax table

            double baseTax4;    // INTERMEDIATE: (constant) tax on base amount for column 4 of tax table

 

            // PRINT OUT IDENTIFICATION INFORMATION

 

            System.out.println( );

            System.out.println( "ITI 1220 Fall 2005, Assignment 4, Question 3" );

            System.out.println( "Name: Alan Williams, Student# 81069665" );

            System.out.println( );

 

            // READ IN GIVENS

 

            System.out.println( "Enter the taxable income." );

            income = keyboard.nextDouble( );

 

            // BODY OF ALGORITHM

 

            // Initialize all the constants according to the tax table.

 

            // Column 1

            base1 = 0.0;

            rate1 = 0.16; // Percentages are expressed in 0 to 1 range.

            baseTax1 = 0.0;

 

            // Column 2

            base2 = 35595.0;

            rate2 = 0.22;

            baseTax2 = 5695.0;

 

            // Column 3

            base3 = 71190.0;

            rate3 = 0.26;

            baseTax3 = 13526.0;

 

            // Column 4

 

            base4 = 115739.0;

            rate4 = 0.29;

            baseTax4 = 25109.0;

 

            // Is income in first bracket?

 

            if ( income <= base2 )

            {

                  // Use column 1

 

                  base = base1;

                  rate = rate1;

                  baseTax = baseTax1;

            }

            else

            {

                  // Is income in second bracket?

 

                  if ( income <= base3 )

                  {

                        // Use column 2

                       

                        base = base2;

                        rate = rate2;

                        baseTax = baseTax2;

                  }

                  else

                  {

                        // Is income in third bracket?

 

                        if ( income <= base4 )

                        {

                              // Use column 3

                             

                              base = base3;

                              rate = rate3;

                              baseTax = baseTax3;

                        }

                        else

                        {

                              // Use column 4

                             

                              base = base4;

                              rate = rate4;

                              baseTax = baseTax4;

                        }

                  }

            }

           

            // The above selected the values for 'base', 'rate', and 'baseTax'. 

            // Use the selected values to calculate the tax.

           

            tax = ( income - base ) * rate + baseTax;

           

            // Determine average tax rate.

           

            averageRate = tax / income;

 

            // PRINT OUT RESULTS AND MODIFIEDS

 

            System.out.println( "The amount of tax is: " + tax );

            System.out.println( "The average tax rate is:  " + averageRate );

 

      }

 

}

Question 4 (40 marks)

A company records historical data for the amount of sales (measured in millions of dollars) of their products for each month.  The sales amount for each month has already been stored in an array Sales, with length NumMonths.  Note that the monthly sales record could extend for several years, and you should not assume the array has size 12.

 

The company’s management is interested in finding out whether the sales trend is good or not, and you have been asked to find the answer to the following question:  What is the largest number of consecutive months for which sales have increased from one month to the next? 

 

For example, suppose that for a period of 12 months previously, the sales were:

 

{5, 4, 6, 8, 8, 9, 11, 13, 12, 14, 15, 14}

 

The answer to the question would be 4 for the above sales figures, for the set of months with sales {8, 9, 11, 13}

 

Question 4a)

 

Design an algorithm that will determine the largest number of consecutive months for which sales have increased from one month to the next, using an array containing sales in millions of dollars.

 

GIVENS:

            Sales                          (an array containing sales figures in millions of dollars)

            NumMonths                (the length of the array Sales)

 

RESULT:

            MaxStreak                 (maximum number of months with consecutive sales increases)

 

ASSUMPTIONS:

            The number of months in the result counts the data points and not the number of intervals between them.

 

HEADER:

            MaxStreak ← SalesIncrease( Sales, NumMonths )

 

INTERMEDIATES:

            Index                           (current array position)

            CurrentStreak            (current number of months for which sales has increased)

 

 

Question 4b)

 

Trace your algorithm on the following array of sales:

 

{12, 14, 13, 18, 19, 20, 19, 24}

 

#

Statement

Sales

NumMonths

MaxStreak

Index

CurrentStreak

0

initial values

{12, 14, 13, 18, 19, 20, 19, 24}

8

?

?

?

1

Index  ← 1

 

 

 

1

 

2

CurrentStreak ← 1 

 

 

 

 

1

3

MaxStreak  ← 1

 

 

1

 

 

4

Index < NumMonths : true

 

 

 

 

 

5

Sales[Index] > Sales[Index-1] : true

 

 

 

 

 

6

CurrentStreak  ← CurrentStreak + 1 

 

 

 

 

2

7

CurrentStreak > MaxStreak : true

 

 

 

 

 

8

MaxStreak  ← CurrentStreak  

 

 

2

 

 

10

Index  ← Index + 1 

 

 

 

2

 

4

Index < NumMonths : true

 

 

 

 

 

5

Sales[Index] > Sales[Index-1] : false

 

 

 

 

 

11

CurrentStreak  ← 1 

 

 

 

 

1

10

Index  ← Index + 1 

 

 

 

3

 

4

Index < NumMonths : true

 

 

 

 

 

5

Sales[Index] > Sales[Index-1] : true

 

 

 

 

 

6

CurrentStreak  ← CurrentStreak + 1

 

 

 

 

2

7

CurrentStreak > MaxStreak : false

 

 

 

 

 

9

Ć

 

 

 

 

 

10

Index  ← Index + 1

 

 

 

4

 

4

Index < NumMonths : true

 

 

 

 

 

5

Sales[Index] > Sales[Index-1] : true

 

 

 

 

 

6

CurrentStreak  ← CurrentStreak + 1 

 

 

 

 

3

7

CurrentStreak > MaxStreak : true

 

 

 

 

 

8

MaxStreak  ← CurrentStreak

 

 

3

 

 

10

Index  ← Index + 1 

 

 

 

5

 

4

Index < NumMonths : true

 

 

 

 

 

5

Sales[Index] > Sales[Index-1] : true

 

 

 

 

 

6

CurrentStreak  ← CurrentStreak + 1

 

 

 

 

4

7

CurrentStreak > MaxStreak : true

 

 

 

 

 

8

MaxStreak  ← CurrentStreak  

 

 

4

 

 

10

Index  ← Index + 1

 

 

 

6

 

4

Index < NumMonths : true

 

 

 

 

 

5

Sales[Index] > Sales[Index-1] : false

 

 

 

 

 

11

CurrentStreak  ← 1

 

 

 

 

1

10

Index  ← Index + 1

 

 

 

7

 

4

Index < NumMonths : true

 

 

 

 

 

5

Sales[Index] > Sales[Index-1] : true

 

 

 

 

 

6

CurrentStreak  ← CurrentStreak + 1 

 

 

 

 

2

7

CurrentStreak > MaxStreak : false

 

 

 

 

 

9

Ć

 

 

 

 

 

10

Index  ← Index + 1 

 

 

 

8

 

4

Index < NumMonths : false