INFO 16029
Problem Solving & Programming Logic

Exercise Solutions

Solutions to various exercises in the on-line notes.

Lesson 1

Simple Statements

  1. Interrogative
  2. Assertion
  3. Assertion
  4. Imperative
  5. Exclamatory
  6. Assertion
  7. Interrogative
  8. Exclamatory
  9. Assertion
  10. Interrogative
  11. Assertion (two of them)
  12. Imperative

Compound Statements

  1. Simple
  2. Compound
    1. I'd like a rum-and-coke.
    2. My friend would like a Guinness.
    Connective: AND
  3. Compound
    1. The car needs to be back by 9pm.
    2. The car needs to be back earlier than 9pm.
    Connective: OR
  4. Compound
    1. That show is boring.
    2. That show is stupid.
    Connective: AND
  5. Compound
    1. That cat swallowed your parrot.
    2. That cat threw up on the floor.
    Connective: THEN
  6. Compound
    1. Candy is dandy.
    2. Liquor is quicker.
    Connective: BUT

AND, OR, NOT Operators

  1. State the truth value for each of the following statements:
    1. false
    2. true
    3. true
    4. true Λ true = true
    5. true V false = true
    6. false V false = false
    7. ~(false) Λ true = true Λ true = true
  2. Write each of the following logical expressions in plain english:
    1. a Λ b = Gramma has a cat and the cat is a Calico. You could also say this as Gramma has a Calico cat.
    2. c Λ ~d = The dog is a dope and a sheep doesn't say "woooo!".
    3. b V c = The cat is a Calico or the dog is a dope.
    4. ~d V a = A sheep doesn't say "woooo!" or Gramma has a cat.
  3. Write each compound statement as a logical expression:
    1. Let A = You're bald.
      Let B = "Your skin is grey."
      A Λ B
    2. Let A = I will teleport to your house. Let B = I will arrive in my hot-air balloon.
      A V B
    3. Let A = He built a sheep launcher.
      Let B = He built a talking cow.
      A Λ B
    4. Let A = Our land is sandy.
      Let B = Our land is rocky.
      A Λ ~B
    5. Let A = There are classes today.
      Let B = There are events today.
      ~(A V B) or you could also use ~A Λ ~B

Lesson 2

Review

  1. 1 + 0 = 1
  2. 1 * 0 = 0
  3. 1 * ~0 = 1 * 1 = 1
  4. ~1 + ~0 = 0 + 1 = 1
  5. ~(1 * 0) = ~(0) = 1

Order of Precedence

  1. 0 * 1 + 1 = 0 + 1 = 1
  2. 1 + 1 * ~1 = 1 + 1 * 0 = 1 + 0 = 1
  3. 0 * 1 + 1 * 0 = 0 + 0 = 0
  4. 0 * (1 + 1) * 0 = 0 * 1 * 0 = 0 * 0 = 0
  5. ~F Λ T = T Λ T = T
  6. ~T V F = F V F = F
  7. ~(T V F) = ~(T) = F
  8. ~T V ~F = F V T = T
  9. (F V ~F) Λ (T V T) = (F V T) Λ (T) = T Λ T = T
  10. (F Λ T) V ~(~F V ~T) = (F) V ~(T V F) = F V ~(T) = F V F = F

Truth Tables

1. Create the Truth Table of the following compound statements:

  1. ~A + B
    ~A + B
    AB~A~A + B
    1101
    1000
    0111
    0011
  2. A * B + C
    A * B + C
    ABCA * BA * B + C
    11111
    11011
    10101
    10000
    01101
    01000
    00101
    00000
  3. ~(A + B) * C
    ~(A + B) * C
    ABCA + B~(A + B)~(A + B) * C
    111100
    110100
    101100
    100100
    011100
    010100
    001011
    000010

2. What if I had reworded the last example and said:
The program terminates when we reach the end of the file or the department number is invalid (valid numbers are between 0 and 100, exclusive (meaning, not including 0 and 100)).When deptNum is invalid, it is <= 0 or >= 100.
Let A = Reach the end of the file
Let B = deptNum <= 0
Let C = deptNum >= 100

a. Write a logical expression:

A + (B + C)

b. Draw and evaluate the truth table for the expression in (a).

A + (B + C)
ABC(B + C)A + (B + C)
11111
11011
10111
10001
01111
01011
00111
00000

3. A program prints the value of x when x meets certain criteria. The following statements and variables are used to define this criteria:
Let A = X is prime
Let B = x >= 1
Let C = X <= 5
Let D = x is an even number

For each of the situations below, write the logical expressions that define when to print the value of X.

Example: Print x when the value of x is prime or x is between 1 and 5, inclusive.
Solution: A + B * C

  1. Print x when x is between 1 and 5 inclusive or is an odd number. B * C + ~D
  2. Print x when x isn't a prime number, is between 1 and 5 inclusive, and is odd. ~A * B * C * ~D
  3. Print x when x is less than 1 or is an odd number greater than or equal to 5. ~B + (~D * C)

4. Draw the truth tables for your expressions in question 3.

a.

B * C + ~D
BCD~DB * CB * C + ~D
111011
110111
101000
100101
011000
010101
001000
000101

b.

~A * B * C * ~D
ABCD~A~D~A * B~A * B * C~A * B * C * ~D
111100000
111001000
110100000
110001000
101100000
101001000
100100000
100001000
011110110
011011111
010110100
010011100
001110000
001011000
000110000
000011000

c.

~B + (~D * C)
BCD~B~D(~D * C)~B + (~D * C)
1110000
1100111
1010000
1000100
0111001
0101111
0011001
0001101

Lesson 3 - Laws/Theorems of Boolean Algebra

1. Draw the truth table to prove part b of DeMorgan's Laws.

~(A * B)
AB(A * B)~(A * B)
1110
1001
0101
0001

~A + ~B
AB~A~B~A + ~B
11000
10011
01101
00111

2. Prove each of the following statements, using the laws and theorems you learned in this lesson.

a) A * (~A + B) = A * B
A * ~A + A * B = A * B (distributive law a)
0 + A * B = A * B (complement law b)
A * B = A * B (identity law a)

b) A * B + A * ~B = A A * (B + ~B) = A (distributive law a)
A * (1) = A (complement law a)
A = A (identity law b)

c) [(A + B) * A] * (A + B) = A
[A] * (A + B) = A (absorption law b)
A = A (absorption law b)

d) [C * (~C + A)] * B = (C * A) * B
[C * ~C + C * A] * B = (C * A) * B (distributive law a)
(0 + C * A) * B = (C * A) * B (complement law b)
(C * A) * B = (C * A ) * B (identity law a)

e) [(~A * (B + C)] + (A * B) = B + ~A * C
[~A * B + ~A * C] + (A * B) = B + ~A * C (distributive law a)
(~A * B + A * B) + (~A * C) = B + ~A * C (associative law a)
B * (~A + A) + (~A * C) = B + ~A * C (distributive law a)
B * (1) + (~A * C) = B + ~A * C (complement law a)
B + (~A * C) = B + ~A * C (identity law b)
B + ~A * C = B + ~A * C (you don't need brackets around ~A * C because of order of precedence)

f) [ A * (~A + B)] * C = A * B * C
[A * ~A + A * B] * C = A * B * C (distributive law a)
(0 + A * B) * C = A * B * c (complement law b)
(A * B) * C = A * B * C (identity law a)
A * B * C = A * B * C (don't need brackets around A * B due to order of precedence)

g) [A * (~A + B)] * (A + B) = A * B
[A * ~A + A * B] * (A + B) = A * B (distributive law a)
(0 + A * B) * (A + B) = A * B (complement law b)
(A * B) * (A + B) = A * B (identity law a)
A * B * A + A * B * B = A * B (distributive law a - multipied (A * B) to (A + B))
A * A * B + A * B * B = A * B (associative law b)
A * B + A * B * B = A * B (idempotent law b)
A * B + A * B = A * B (idempotent law b)
A * B = A * B (idempotent law a)

3. Use the other theorems you've learned to prove these two laws.

  1. A + ~A * B = A + B
  2. A * (~A + B) = A * B

a) (A + ~A) * (A + B) = A + B (distributive law b)
(1) * (A + B) = A + B (complement law a)
(A + B) = A + B (identity law b)
A + B = A + B (associative law a)

b) (A * ~A) + (A * B) = A * B (distributive law a)
(0) + (A * B) = A * B (complement law b)
(A * B) = A * B (identity law a)
A * B = A * B (associative law b)

4. (advanced) Prove DeMorgan's Laws.

DeMorgan's Law #1. ~(x + y) = ~x * ~y

If ~(x + y) = ~x * ~y, then x + y must be the complement of ~x * ~y.

Recall that the complement laws say that x + ~x = 1 and x * ~x = 0

Therefore, we need to prove that
a) (x + y) + (~x * ~y) = 1 and
b) (x + y) * (~x * ~y) = 0

a) prove (x + y) + (~x * ~y) = 1

((x + y) + ~x) * ((x + y) + ~y) (distributive law b to distribute (x + y) over (~x * ~y))
(~x + (x + y)) * (~y + (y + x)) (commutative law a)
((~x + x) + y) * ((~y + y) + x) (associative law a)
(1 + y) * (1 + x) (complement law a on (~x + x) and (~y + y))
1 * 1 (identity law c on (1 + y) and on (1 + x))
= 1 (the AND operation)

b) prove (x + y) * (~x * ~y) = 0

(~x * ~y) * (x + y) (commutative law b to move the (~x * ~y) term and (x + y) term around)
(~x * ~y) * x + (~x * ~y) * y (distributive law b to distribute (~x * ~y) over (x + y))
x * (~x * ~y) + y * (~y * ~x) (commutative law b)
(x * ~x) * ~y + (y * ~y) * ~x (associative law b)
(0 * ~y) + (0 * ~x) (complement law b for (x * ~x) and (y * ~y))
0 + 0 (identity law d on (0 * ~y) and (0 * ~x))
= 0 (the OR operation)

Therefore, since (x + y) + (~x * ~y) = 1 and (x + y) * (~x * ~y) = 0, then (x + y) must be the complement of (~x * ~y).

Therefore, ~(x + y) must be equal to (~x * ~y).

DeMorgan's Law #2. ~(x * y) = ~x + ~y

If ~(x * y) = ~x + ~y, then x * y must be the complement of ~x + ~y.

Recall that the complement laws say that x + ~x = 1 and x * ~x = 0

Therefore, we need to prove that
a) (x * y) + (~x + ~y) = 1 and
b) (x * y) * (~x + ~y) = 0

a) prove (x * y) + (~x + ~y) = 1

(~x + ~y) + (x * y) (commutative law a)
((~x + ~y) + x) * ((~x + ~y) + y) (distributive law b to distribute (~x + ~y) over (x * y))
(x + (~x + ~y)) * (y + (~x + ~y)) (commutative law a)
((x + ~x) + ~y) * ((y + ~y) + ~x) (associative law a)
(1 + ~y) * (1 + ~x) (complement law a on (x + ~x) and on (y + ~y))
1 * 1 (identity law c on (1 + ~y) and on (1 + ~x))
= 1 (the AND operation)

b) prove (x * y) * (~x + ~y) = 0

(x * y) * ~x + (x * y) * ~y (distributive law a to distribute (x * y) over (~x + ~y))
~x * (x * y) + ~y * (y * x) (commutative law b)
(~x * x) * y + (~y * y) * x (associative law b)
0 * y + 0 * x (complement law b on (~x * x) and on (~y * y))
0 + 0 = 0 (the OR operation)

Therefore, since (x * y) + (~x + ~y) = 1 and (x * y) * (~x + ~y) = 0, then (x * y) must be the complement of (~x + ~y).

Therefore, ~(x * y) must be equal to (~x + ~y).

Lesson 4

Structured English

Rewrite the following process descriptions using Structured English:

NOTE: There is more than one correct answer for these; if you're not sure of your own, please check with your prof.

1. Our discount policy depends on whether a customer is a new or repeat customer, but we also give a seniors' discount: New customers get a 20% discount on their second order, and repeat customers get free shipping. Customers 65 and over also get a 10% discount their current purchase.

Discount Policy:
If the customer is new then
    Offer a 20% discount to their next order
Otherwise
    Give the customer free shipping
If the customer is 65 or over then
    Offer a 10% discount on their current purchase

2. A boss wants to give all her employees a nice bonus. She tells you:
"I need a report listing every employee and the bonus I plan to give him or her. Everybody gets at least $100. All the employees in Department 2 get $200, but if they have more than 5 dependents, they should get $500, and the employees in department 3 should all get $500."

Assigning Employee Bonuses:
Assign a bonus of $100 to all employees.
If the employee is in department 2 then
    If the employee has more than 5 dependents then
        Add $500 to the bonus amount
    Otherwise,
        Add $200 to the bonus amount
Otherwise, if the employee is in department 3 then
    Add $500 to the bonus amount

Reading Decision Tables

  1. Free delivery
  2. delivery is $5
  3. Free delivery
  4. Free delivery

Creating Decision Tables

1. Check Cashing Policy:

If you have trouble identifying the conditions and their values, and the actions, it helps to break up each individual sentence into its actions and conditions. This problem is particular difficult because it's written in conversational language, and you have to pick out the important bits of information and interpret them in the proper way:
1. this first sentence provides no useful information
2. Condition: If the person has a valid account.
3. Condition: If they do (if they meet condition in sentence 2) Action: Cash the check with just the signature
4. Condition: if the check is a government check and [the person] has a valud photo ID. Action: cash the check
5. This sentence just adds to the condition that they don't have to have a valid customer id to cash a government check with photo id, but it's still a condition (it would go with the condition in #2).

Conditions:
Customer has valid account number (Values = Y, N)
Check is a government check (Values = Y, N)
Customer has photo ID (Values = Y, N)

Actions:
Cash check with signature
Cash check
Don't cash check

Number of rules: 2 values * 2 values * 2 values = 8 rules.

When populating the condition alternatives section of this table, the first condition will have a pattern of 4 Y's and 4 N's (# rules / # values = 8 / 2 = 4 of each value). The second row, will be the previous row's result divided by the # of values for the 2nd condition (4 / 2 = 2 of each). The third row will be the previous row's result divided by the # of values for the third condition (2 / 2 = 1 of each).

Check Cashing PolicyRules
12345678
Customer has valid accountYYYYNNNN
Government checkYYNNYYNN
Customer has photo IDYNYNYNYN
Cash check    X   
Cash check with signatureXXXX    
Don't cash check     XXX

Reduce the table: We can reduce rules 1 to 4 because they have the same action for all possibilities under "customer has a valid account = Y" and the values of the rest of the conditions don't matter (they will use indifference (--) symbol). We can also reduce rules 7 and 8 because they have the same action for "customer has a valid account number = N" and "government check = N" (photo ID value doesn't matter so it will receive indifference (--) symbol).

Check Cashing PolicyRules
1234
Customer has valid accountYNNN
Government check--YYN
Customer has photo ID--YN--
Cash check X  
Cash check with signatureX   
Don't cash check  XX

2. Medical Insurance Policy:

Pick out actions and conditions in policy description:

1. Introduces the conditions (a couple of factors) and actions (patients receiving some kind of reimbursement)
2. Condition: Until the deductible has been met. Action: no reimbursement to the patient.
3. Condition: If the deductible has been met...
4. Conditions: type of visit is doctor's office; type of visit is hospital, type of visit is lab; Actions: Reimburse 80%, reimburse 70%, reimburse 50%

Conditions:
Deductible has been met (Values = Y, N)
Type of visit(Values = (D)octor, (H)ospital, (L)ab)

Actions:
No reimbursement
Reimburse 80%
Reimburse 70%
Reimburse 50%

Number of rules: 2 values * 3 values = 6 rules.

Medical Insurance PolicyRules
123456
Deductible has been metYYYNNN
Type of visitDHLDHL
No reimbursement   XXX
Reimburse 80% X    
Reimburse 70%  X   
Reimburse 50%X     

D = Doctor's visit, H = Hospital visit, L = Lab visit

We can reduce this table by combining rules 1 to 3 since they all have the same action and the "Deductible has been met" is Yes for all, and the "Type of Visit" covers all possible options (D, H, L):

Medical Insurance PolicyRules
1234
Deductible has been metYYYN
Type of visitDHL--
No reimbursement   X
Reimburse 80% X  
Reimburse 70%  X 
Reimburse 50%X   

D = Doctor's visit, H = Hospital visit, L = Lab visit

Extended Entry Version:

Medical Insurance PolicyRules
1234
Deductible StatusMetMetMetNot Met
Type of visitDoctorHospitalLab--
Amt. of Reimbursement50%80%70%0%

3. Company Discount Policy:

Pick out actions and conditions in policy description:

1. Just indicates there is a customer type: wholesale and retail.
2. Condition: customer is a wholesale customer. Action: customer receives 2% discount
3. Conditions: customers are wholesale or retail; customer paid cash; Action: an additional 2% discount.
4. Condition: customer purchased 50+ units; Action: additional 2% discount.

Conditions:
Customer type (Values = (W)holesale, (R)etail)
Customer paid cash (Values = Y, N)
Number of units purchased (Values = >=50, <50

Actions:
2% discount
additional 2% discount (4%)
additional 2% dicsount (6%)
No discount (I added this even though it wasn't in the description; you'll see why later)

Number of rules: 2 values * 2 values * 2 values = 8 rules.

Customer Discount PolicyRules
12345678
Type of customerWWWWRRRR
Customer paid cashYYNNYYNN
Number of units purchased<50>=50<50>=50<50>=50<50>=50
No discount        
2% discountXXXX    
additional 2% discountXX  XX  
additional 2% discount X X X X

W = Wholesale, R = Retail

Notice that rule #7 has no action. The policy description implies that retail customers who don't pay cash and don't buy 50 units or more get no discount, so an X should go in the "No discount" row of rule # 7.

Furthermore, we can clean up the table and make it easier to read by changing the discount actions to 2%, 4%, and 6%. Then we can have only one X per rule. This will also make it easier to determine if the table can be reduced:

Customer Discount PolicyRules
12345678
Type of customerWWWWRRRR
Customer paid cashYYNNYYNN
Number of units purchased<50>=50<50>=50<50>=50<50>=50
No discount      X 
2% discount  X X  X
4% discountX  X X  
6% discount X      

W = Wholesale, R = Retail

We can now easily see that the table can't be reduced at all.

As an Extended Entry Table:

Customer Discount PolicyRules
12345678
Type of customerWholesaleWholesaleWholesaleWholesaleRetailRetailRetailRetail
Customer paid cashYYNNYYNN
Number of units purchased<50>=50<50>=50<50>=50<50>=50
Amt. of Discount4%6%2%4%2%4%0%2%

4. Airline Discount Policy:

Conditions:
Destination (India, Asia)
Passenger Age (<= 2, > 2 && < 18, > 18
Depart on Monday or Friday (Yes, No)
Stay 6 days or more (Yes, No)

Actions:
Travel Free
0% discount
10% discount
20% discount
40% discount

Number of rules: 2 values * 3 values * 2 values * 2 values = 24 rules

Airline
Discount
Policy
Rules
12345678 910111213141516 1718192021222324
Destination:IIIIIIII AAAA AAAAAAAAAAAA
Passenger Age:<=2<=2<=2<=2 3-183-183-183-18>18>18>18>18 <=2<=2<=2<=2 3-183-183-183-18>18>18>18>18
Depart Mon/Fri?YYNNYYNN YYNNYYNN YYNNYYNN
Stay >= 6 Days?YNYNYNYN YNYNYNYNYN YNYNYN
No Discount          X             X  
10% DiscountX X X  X X X  X X X  X X X 
20% Discount           XX              
25% Discount                XX   XX  XX
40% Discount    XX XX         XX XX    
Travel FreeXXXX          XXXX         

For rules 1 to 4, and 13 to 16, you've got an interesting set of actions: some of these columns state a 10% discount for staying 6+ days, but all of these columns also state that these passengers travel for free. Since a passenger traveling for free can't receive an additional discount, we can combine all 8 rules into rule #1, below.

You can reduce rules 10 and 22 (passengers over 18 departing on a Monday/Friday who are staying less than 6 days, regardless of destination, get no discount at all) although this may be hard to see until after you reduce the table at least once.

We can also reduce rules 5/7 (passengers traveling to India, between 3 and 18 years of age, staying 6+ days, doesn't matter what day they leave) and 6/8 (same as previous, except staying less than 6 days).

You can reduce rules 10 and 22 (passengers over 18 departing on a Monday/Friday who are 6 days or more, regardless of destination, get no discount at all) although this may be hard to see until after you reduce the table at least once.

Similarly, you can reduce rules 9 and 21 (passengers over 18 departing on a Monday/Friday who are staying less than 6 days, regardless of destination, get a 10% discount).

Reduced Table:

Airline
Discount
Policy
Rules
12345678 910111213
Destination:--II-- --II AAAAAA
Passenger Age:<=2 3-183-18 >18>18>18>18 3-183-183-183-18 >18>18
Depart Mon/Fri?------ YYNN YYNNNN
Stay >= 6 Days?--YNNY YN YNYNYN
No Discount   X           
10% Discount  X XX  X X X  
20% Discount      XX        
25% Discount           XXXX
40% Discount XX      XXXX  
Travel FreeX               

You could display the action stub/entry in extended entry format:

Airline
Discount
Policy
Rules
12345678 910111213
Destination:--II-- --II AAAAAA
Passenger Age:<=2 3-183-18 >18>18>18>18 3-183-183-183-18 >18>18
Depart Mon/Fri?------ YYNN YYNNNN
Stay >= 6 Days?--YNNY YN YNYNYN
Discount100%40%50%0%10%30% 20%50%40%75%65% 35%25%

5. Delivery Fee Policy

Pick out actions and conditions in policy description:

1. Condition: if a customer buys $500 or more; Action: delivery is free.
2. Condition: if a customer buys $500 to $100; unless they are a valued customer; Action: delivery is $10.
3. Condition: In this case (meaning, if the customer is a valued customer and buys between $500 and $100, continuing from #2); Action: delivery charge is $5; Condition: unless they paid cash; Action: delivery is free
4. Condition: if customer buys $100 or less; Action: delivery is $10; Condition: unless they paid cash; Action: delivery is $5

Conditions:
Purchase amount: (Values = >=500, <500 and >100, <=100
Valued customer: (Values = Y, N)
Customer paid cash (Values = Y, N)

Actions:
Free delivery
Delivery is $5
Deliver is $10

Number of rules: 3 values * 2 values * 2 values = 12 rules.

Delivery Fee PolicyRules
123456789101112
Purchase Amount $:>=500>=500>=500>=500 500 to 100500 to 100500 to 100500 to 100 <=100<=100<=100<=100
Valued CustomerYYNNYYNNYYNN
Paid CashYNYNYNYNYNYN
Delivery is $10      XX X X
Delivery is $5     X  X X 
Delivery is FreeXXXXX       

We can reduce this table by combining rules 1 to 4: They all have the same action and they cover all the possibilities for "Valued Customer" and "Paid Cash" when the customer has purchased $500 or more worth of merchandise. This should make sense from the first sentence in the description.

Additionally, we can combine rules 7 and 8, which say that if the purchase amount is between $500 and $100 and the customer is not a valued of customer, it doesn't matter if they paid cash or not, the action ($10 delivery fee) is the same.

We can also reduce rules 9 and 11: both show the same action of $5 delivery fee when the purchases of $100 or less and the customer paid cash, regardless of whether or not they're a valued customer.

Finally, we can reduce rules 10 and 12 because they indicate that a customer pays $10 delivery fee if they purchase $100 or less and don't pay with cash, regardless of whether or not they're a valued customer.

Delivery Fee PolicyRules
123456
Purchase Amount $:>=500500 to 100500 to 100500 to 100<=100<=100
Valued Customer--YYN----
Paid Cash--YN--YN
Delivery is $10   X X
Delivery is $5  X X 
Delivery is FreeXX    

As an Extended Entry Table:

Delivery Fee PolicyRules
123456
Purchase Amount $:>=500500 to 100500 to 100500 to 100<=100<=100
Valued Customer--YYN----
Payment Method--CashCredit/Debit--CashCredit/Debit
Delivery ChargeFreeFree$5.00$10.00$5.00$10.00

Reading Decision Tables

1.

  1. Free delivery
  2. delivery is $5
  3. Free delivery
  4. Free delivery

2.

DISPLAY "Enter age of student:"
GET age
IF age >= 21 THEN
    residence = "Laurier"
ELSE
    DISPLAY "Does student request co-ed accomodation? (Y/N)"
    GET coed    
    IF coed = "Y" THEN
        residence = "Trudeau"
    ELSE
        residence = "MacDonald"
DISPLAY "Residence Assigned: " + residence

3.

DISPLAY "Enter total amount due:"
GET amount
DISPLAY "Has deductible been paid? (Y/N)"
GET paidDeductable
IF paidDeductable = "Y" THEN
    DISPLAY "Enter type of visit: (D)octor, (H)ospital, or (L)ab: "
    GET visitType
    IF visitType = "D" THEN
        reimburseRate = .5
    ELSE IF visitType = "H" THEN
        reimburseRate = .8
    ELSE IF visitType = "L" THEN
        reimburseRate = .7
ELSE
    remiburseRate = 0
CALCULATE reimburseAmt AS amount * reimburseRate
DISPLAY "Reimbursement Amount: $" + reimburseAmt

Lesson 4

Pseudocode: Sequence

Calculate the total value of an inventory item:

DISPLAY "Enter item name:"
GET itemName
DISPLAY "Enter quantity on hand:"
GET itemQoh
DISPLAY "Enter cost of item:"
GET itemCost
totalCost = itemQoh * itemCost
DISPLAY "Total cost of ", itemName, ": $", totalCost

Relational Expressions

Given that:
a = 5 b = 2 c = 4 d = 6 e = 3
What is the result of each of the following relational expressions?

  1. a > b
    5 > 2 = TRUE
  2. a <> b
    5 <> 2 = TRUE
  3. d % b = c % b
    5 % 2 = 4 % 2
    0 = 0 = TRUE
  4. a * c <> d * b
    5 * 4 <> 6 * 2
    20 <> 12 = TRUE
  5. d * b = c * e
    6 * 2 = 4 * 3
    12 = 12 = TRUE
  6. a * b < a % b * c
    5 * 2 < 5 % 2 * 4
    10 < 1 * 4
    10 < 4 = FALSE
  7. c % b * a = b % c * a
    4 % 2 * 5 = 2 % 4 * 5
    0 * 5 = 2 * 5
    0 = 10 = FALSE
  8. b % c * a <> a * b
    2 % 4 * 5 <> 5 * 2
    2 * 5 <> 5 * 2
    10 <> 10 = FALSE

Relational Expressions

1. Given that:
a = 5 b = 2 c = 4 d = 6 e = 3
What is the result of each of the following compound relational expressions?

  1. a < b AND a < d
    5 < 2 AND 5 < 6
    false AND true = false
  2. a < 5 AND a > b
    5 < 5 AND 5 > 2
    false AND true = false
  3. a <= 5 OR a >= b
    5 <= 5 OR 5 >= 2
    true OR true = true
  4. d <> e * b OR d < a
    6 <> 3 OR 6 < 5
    true OR false = true
  5. NOT(d < a) AND c = b2
    NOT(6 < 5) AND 4 = 22
    NOT(false) AND true
    true AND true = true
  6. e >= a OR a = 5 AND NOT(e > 2)
    3 >= 5 OR 5 = 5 AND NOT(3 > 2)
    false OR true AND NOT(true)
    false OR true AND false
    false OR false = false

2. For each of the following statements, assign variable names for the unknowns and rewrite the statements as relational expressions.

  1. A customer's age is 65 or more.
    age >= 65
  2. The temperature is less than 0 degrees.
    temperature < 0
  3. A person's height is over 6 feet.
    height > 6
  4. The current month is 12 (December).
    month = 12
  5. The user enters the name "Fred".
    userName = "Fred"
  6. The user enters the name "Fred" or "Wilma".
    userName = "Fred" OR userName = "Wilma"
  7. The person's age is 65 or more and their sub total is more than $100.
    age >= 65 AND subTotal > 100
  8. The current day is the 7th of the 4th month.
    day = 7 AND month = 4
  9. A person is older than 55 or has been at the company for more than 25 years.
    age > 55 OR numYears > 25
  10. A width of a wall is less than 4 metres but more than 3 metres.
    width < 4 AND width > 3 (I prefer writing it as width > 3 AND width < 4, just makes more sense)
  11. An employee's department number is less than 500 but greater than 1, and they've been at the company more than 25 years.
    deptNum < 500 AND deptNum > 1 AND numYears > 25 (again, I'd prefer deptNum > 1 AND deptNum < 500 AND numYears > 25)

Selections

1.

DISPLAY "Enter a whole number:"
GET number
IF number % 2 = 0 THEN
    DISPLAY "your value is even"
ELSE
   DISPLAY "your value is odd"
END IF

You can also write it as:

DISPLAY "Enter a whole number:"
GET number
IF number % 2 = 1 THEN
    DISPLAY "your value is odd"
ELSE
   DISPLAY "your value is even"
END IF

2.

DISPLAY "Enter the number of years:"
GET years
IF years > 5 THEN
    interestRate = .075
ELSE
   interestRate = .045
END IF

You can also write it as:

DISPLAY "Enter the number of years:"
GET years
IF years <= 5 THEN
    interestRate = .045
ELSE
   interestRate = .075
END IF

3.

DISPLAY "Enter the final grade:"
GET grade
IF number >= 65 THEN
    DISPLAY "Pass"
ELSE
   DISPLAY "Fail"
END IF

You can also write it as:

DISPLAY "Enter the final grade:"
GET grade
IF number < 65 THEN
    DISPLAY "Fail"
ELSE
   DISPLAY "Pass"
END IF

4.

INIT MAX_HOURS = 40
INIT REG_PAY = 10
INIT OT_PAY = 15
DISPLAY "Enter the hours worked:"
GET hoursWkd
IF hoursWkd <= MAX_HOURS THEN
    pay = REG_PAY * hoursWkd
ELSE
   pay = (MAX_HOURS * REG_PAY) + (hoursWkd - MAX_HOURS) * OT_PAY
END IF
DISPLAY "Total Pay: $", pay

5.

INIT RATE1 = .05
INIT RATE2 = .075
INIT RATE3 = .1
INIT RATE4 = .15
INIT MAX1 = 1000
INIT MAX2 = 2000
INIT MAX3 = 3500
DISPLAY "Enter the sales amount:"
GET sales
IF sales < MAX1
   rate = RATE1
ELSE IF sales < MAX2
   rate = RATE2
ELSE IF sales < MAX3
   rate = RATE3
ELSE
   rate = RATE4
END IF
pay = sales * rate
DISPLAY "Total Pay: $", pay

6. (including bonus to check for leap years, and I added Java-style comments to help you understand the logic)

DISPLAY "Enter the year:"
GET year
DISPLAY "Enter the month number:"
GET month
DISPLAY "Enter the date:"
GET date
// if date is not from 1 to 31, or month is not 1 to 12, invalid
IF date <=0 OR date > 31 OR month <=0 OR month > 12 THEN
    DISPLAY "Invalid Date"
ELSE // date is 1 to 31 and month is 1 to 12
    IF month = 2 THEN // february
        // if this is a leap year
        IF year % 4 = 0 AND year % 100 <> 0 OR year % 400 = 0 THEN
            IF date > 29 THEN  // anything > 29 is invalid
                DISPLAY "Invalid Date"
            ELSE 
                DISPLAY "Valid Date"
            END IF
        ELSE // not a leap year
            IF date > 28 THEN // anything > 28 is invalid
                DISPLAY "Invalid Date"
            ELSE 
                DISPLAY "Valid Date"
            END IF 
    // months with 30 days
    ELSE IF month = 4 OR month = 6 OR month = 9 OR month = 11 THEN
        IF date = 31 THEN // all dates but 31 are valid
            DISPLAY "Invalid Date"
        ELSE
            DISPLAY "Valid Date"
        END IF
    ELSE // all other months have 31 days - if we're here, it's valid
        // (otherwise, we would have been caught by the very first if-stmt)
        DISPLAY "Valid Date'
    END IF
END IF

Lazy Evaluation

  1. 60% have dental, 85% have medical; we want either one or both (OR) therefore, ask the most likely first: IF medical OR dental THEN
    Proof: Say of 1000 employees, you ask 1000 about dental: 600 will have it and 300 won't. You have to ask the other 300 about medical, for a total of 1300 checks. If you ask 1000 about medical first, 850 will have it and 150 won't; you have to ask that 150 if they have dental to see if you get a true result. Therefore you've done 1150 checks, which is less than 1300 checks and therefore more efficient.
  2. 34% in SCLS and 90% are mobile; you want both (AND) so ask the least likely first: IF scls AND mobile THEN
    Proof: 1000 students checked for mobile - 900 are, 100 aren't. Since you're using AND, you know that you can forget the 100 that aren't since you need both true. But you have to ask the other 900 to see if they are in SCLS. You've done 1900 checks. If you ask about SCLS first, you can forget about the 660 who aren't in SCLS and check the other 340 if they are mobile. Here you've done 1340 checks, which is less than 1900 so therefore it's more efficient to ask about SCLS first.
  3. 55% have term gpa of 3.5+ 40% have cumulative gpa of 3.75+; we want both (AND) so ask the least likely first: IF cumulativeGpa >= 3.7 AND termGPA >= 3.5 THEN
    Proof: Ask term gpa first: 1000 + the 550 you'll have to check for the cumulative gpa (can ignore the other 450) for a total of 1550. Ask cumulative gpa first: 1000 + the 400 that you'll have to check for term gpa (can ignore the other 600) for a total of 1400 checks. Therefore asking about cumulative gpa first is more efficient.

Lesson 5

While Loops (Pre-Test)

1. A program that asks for the weekly sales for 5 sales people, then calculates the average sales.

INIT NUM_PEOPLE = 5
INIT avgSales = 0
INIT counter = 0
INIT totalSales = 0

WHILE (counter < NUM_PEOPLE)
     DISPLAY "Enter sales amount:"
     GET salesAmt
     ADD salesAmt TO totalSales
     ADD 1 TO counter

CALCULATE avgSales AS totalSales / NUM_PEOPLE
DISPLAY "Average Sales: ", avgSales

2. A program that asks the user for 10 numbers. After all 10 numbers are entered, the highest number is displayed. HINT: Use an IF statement inside your loop to keep track of the highest value entered.

Assuming user can enter anything, positive, negative, whatever.

INIT NUMS = 10
INIT number = 0
INIT highest = 0
INIT counter = 1;

DISPLAY "Enter a value:"
GET number
highest = number

WHILE (counter <= NUMS-1)
     DISPLAY "Enter a value:"
     GET number
     IF (number > highest) THEN
          highest = number
     END IF

DISPLAY "Highest value entered: ", highest

3. A program that asks the user to enter a series of test scores. Add each test score to a total. After each test score is entered, ask the user if they'd like to enter another test score. If they say yes, the loop continues, but if they say anything else, the loop terminates. After the loop terminates, display the average of all the scores entered.

INIT keepGoing = "Y"
INIT scoreNum = 0
INIT totalScore = 0
WHILE (keepGoing = "Y")
    DISPLAY "Enter score #" + (scoreNum+1)
    GET score
    ADD score TO totalScore
    INCREMENT scoreNum
    DISPLAY "Would you like to enter another score?"
    GET keepGoing
CALCULATE avgScore AS totalScore / scoreNum
DISPLAY "Average Score: " + avgScore

Lesson 5 - While Loops (Post-Test)

Write the pseudocode, using post-test While loops, for each of the following:

1. A program that asks the user for a department number. The department number must be greater than 0. As long as the user keeps entering an invalid department number, ask again. Stop asking when the department number is valid.

REPEAT
    DISPLAY "Enter Dept# (> 0): "
    GET deptNum
    WHILE (deptNum <= 0)

2. Modify question 1, assuming that the department number must be between 1 and 10, inclusive.

REPEAT
    DISPLAY "Enter Dept# (> 0): "
    GET deptNum
    WHILE (deptNum < 1 OR deptNum > 10)

3. What is the output of the following loops?

INIT counter = 1
REPEAT
     INCREMENT counter
     WHILE (counter > 1)
INIT counter = 1
WHILE (counter <> 10)
     ADD 2 TO counter
     DISPLAY counter

We call these kinds of loops "endless loops" because they never end!

The output of the first loop is 1 2 3 4 5... etc and will never stop because the counter starts at 1, increments by 1 each iteration, but the condition says to continue as long as counter is greater than 1: it's ALWAYS greater than 1!!

The output of the second loop prints 3, 5, 7, 9, 11, 13, 15, ... etc and keeps on going. This time, the counter starts at 1 but is incremented by 2 each iteration. The condition of the loop says to continue as long as counter is not equal to 10. In this one, it will NEVER be equal to 10. This is why we rarely use "equal to" or "not equal to" in our loops; we try to use an inequality such as >= or <= . To fix this loop, try changing the condition to counter <= 10, then the loop will terminate after it increments to 11 (output will be 3 5 7 9 11)

Until Loops (Post-Test)

Write the pseudocode, using Until loops, for each of the following:

1. A program that asks the user for whole numbers until they enter a value that's even.

REPEAT
    DISPLAY "Enter a whole number: "
    GET num
UNTIL (num % 2 = 0)
      

2. A program that asks the user for a valid department number. Department numbers must always be between 1 and 55. Keep prompting the user until they enter the correct department number.

REPEAT
    DISPLAY "Enter department number: "
    GET deptNum
UNTIL (deptNum >=1 AND deptNum <= 55)
      

For Loops

Write the pseudocode, using FOR loops, for each of the following:

1. A program that displays the numbers from 1 to 10 along with each number's square and cube.

FOR counter = 1 TO 10 DISPLAY counter, counter^2, counter^3

2. A program that calculates n! ("n-factorial") where n is a user-entered value. A factorial is calculated as 1 * 2 * 3 * ... * n-1 * n. For example, 5! ("five factorial") is calculated as 1 * 2 * 3 * 4 * 5.

INIT factorial = 1
DISPLAY "Enter a number: "
GET n
FOR counter = 1 to n
   factorial = factorial * counter
DISPLAY n + "! is equal to " + factorial

3. Modify question 2: If the user enters a value that's less than 1 or greater than 20, display an error message that the value is invalid. Otherwise, calculate and display the factorial of the user-entered number.

INIT factorial = 1
DISPLAY "Enter a number: "
GET n
IF (n < 1 OR n > 20) THEN
   DISPLAY "Error! You entered an invalid number."
ELSE
   FOR counter = 1 to n
      factorial = factorial * counter
   DISPLAY n + "! is equal to " + factorial
END IF

Nested Loops

1. Write the pseudocode for a program that asks the user to enter a series of test results for a set of experiments. Each experiment involves 3 tests. After the user enters 3 test results, display the average of the three tests. Keep recording experiments until the user wishes to quit (e.g. you can ask them after each set of 3 tests if they wish to record another experiment).

INIT NUM_TESTS = 3
INIT continue = "Y"
INIT expNum = 1
INIT expTotal = 0
REPEAT
    DISPLAY "Entering results for experiment " + expNum
    FOR test = 1 to NUM_TESTS
        DISPLAY "Test #" + test + ": "
        GET testResult
        ADD testResult TO expTotal
    CALCULATE avgResult = expTotal / NUM_TESTS
    DISPLAY "Average for experiment " + expNum + ": " + avgResult
    expTotal = 0
    DISPLAY "Record another experiment? (Y/N)"
    GET continue
    WHILE continue = "Y"

2. Modify question 1: In addition to displaying the average for each experiment, display the overall average for all tests after all experiments have been recorded.

INIT NUM_TESTS = 3
INIT continue = "Y"
INIT expNum = 0
INIT expTotal = 0
INIT total = 0
REPEAT
    ADD 1 to expNum
    DISPLAY "Entering results for experiment " + expNum
    FOR test = 1 to NUM_TESTS
        DISPLAY "Test #" + test + ": "
        GET testResult
        ADD testResult TO expTotal
    CALCULATE avgResult = expTotal / NUM_TESTS
    DISPLAY "Average for experiment " + expNum + ": " + avgResult
    ADD expTotal TO total
    expTotal = 0
    DISPLAY "Record another experiment? (Y/N)"
    GET continue
    WHILE continue = "Y"
CALCULATE overallAvg = total / expNum
DISPLAY "Overall average: " + overallAvg

3. Write a program that prints a right-angled triangle of asterisks. Ask the user to specify how many rows the triangle should have. For example, if they say 5, your triangle will look like this:

*
**
***
****
*****

If the user enters 3, your triangle will look like this:

*
**
***
DISPLAY "Enter size of triangle: "
GET size
FOR row = 1 to size
    FOR column = 1 to row
        DISPLAY "*"

Nested Structures

1. Write a program that calculates the average final grade for a student who's taken some unknown number of courses. The final grade entered must be greater than or equal 0: if the user enters a negative grade, display an error message and ask again. Add all valid grades to a total and display the average grade after all grades have been entered.

INIT continue = "Y"
INIT numGrades = 0
INIT totalGrade = 0
REPEAT
    INCREMENT numGrades
    DISPLAY "Enter grade #" + numGrades
    GET grade
    WHILE grade < 0
        DISPLAY "Error:  Grade must be 0 or greater. Try again."
        GET grade
    ADD grade TO totalGrade
    DISPLAY "Enter another grade? (Y/N) "
    GET continue
    WHILE continue = "Y"
CALCULATE avgGrade = totalGrade / numGrades
DISPLAY "Average Grade: " + avgGrade

2. The roots of a quadratic equation can be calculated using the formulas found on page 108 (question 3.1) of your Java textbook. (see SOS Math: Quadratic Formula if you're not taking Java)

If the discriminant (b2 - 4ac) is positive, the equation has 2 roots. If the discriminant is negative, the equation has no roots. if the discriminant is 0, there is only one root.

Prompt the user to enter the values a, b, and c for a quadratic equation. If there are 2 roots, calculate and display the 2 roots. If there is one root, calculate and display the single root. If there are no roots, display the message "This equation has no roots."

Allow the user to run the program as many times as they wish: after each result is displayed, ask them if they want to do another equation. Terminate when they say no.

INIT continue = "Y"
WHILE continue = "Y"
    DISPLAY "Enter value for A: "
    GET aValue
    DISPLAY "Enter value for B: "
    GET bValue
    DISPLAY "Enter value for C: "
    GET cValue
    CALCULATE discrim = bValue2 - 4 * aValue * cValue
    IF discrim > 0  THEN
        CALCULATE root1 = (-bValue + discrim0.5) / 2 * aValue
        CALCULATE root2 = (-bValue - discrim0.5) / 2 * aValue
        DISPLAY "There are two roots: " + root1 + " and " + root2
    ELSE IF discrim = 0 THEN
        CALCULATE root = (-bValue - discrim0.5) / 2 * aValue
        DISPLAY "There is one root: " + root
    ELSE
        DISPLAY "There are no roots for that equation."
    END IF
    DISPLAY "Calculate for another equation? (Y/N) "
    GET continue

3. Write a program to analyse integer numbers: Ask the user to enter 100 whole numbers. Keep track of how many numbers entered are even, odd, positive, and negative. Display the results after all values have been entered.

INIT MAX_NUMS = 100
INIT even = 0;
INIT odd = 0;
INIT neg = 0;
INIT pos = 0;
FOR counter = 1 TO MAX_NUMS
    DISPLAY "Enter value " + counter + ": "
    GET num
    IF num % 2 = 0 THEN
        INCREMENT even
    ELSE
        INCREMENT odd
    END IF
    IF num > 0 THEN
        INCREMENT pos
    ELSE IF num < 0 THEN
        INCREMENT neg
    END IF
DISPLAY "Analysis of all values entered:"
DISPLAY "Even numbers: " + even
DISPLAY "Odd numbers: " + odd
DISPLAY "Positive numbers: " + pos
DISPLAY "Negative numbers: " + neg

4. Write a program to convert values from Fahrenheit to Celsius and from Celsius to Fahrenheit. First, ask the user if they'd like to convert from Fahrenheit to Celsius or from Celsius to Fahrenheit. Then prompt the user for the starting temperature and ending temperature. Lastly, display a table of conversions from start to end.

DISPLAY "Convert from (C)elsius or from (F)ahrenheit?" 
GET convert
IF convert = "C" THEN
    DISPLAY "Enter starting Celsius Temperature:"
    GET start
    DISPLAY "Enter ending Celsius Temperature:"
    GET end
    DISPLAY "Celsius", "Fahrenheit"
    FOR counter = start TO end
        CALCULATE fah = counter * 9 / 5 + 32
        DISPLAY counter, fah
ELSE IF convert = "F" THEN
    DISPLAY "Enter starting Fahrenheit Temperature:"
    GET start
    DISPLAY "Enter ending Fahrenheit Temperature:"
    GET end
    DISPLAY "Fahrenheit", "Celsius"
    FOR counter = start TO end
        CALCULATE cel = (counter - 32) * 5 / 9
        DISPLAY counter, cel
ELSE
    DISPLAY "Invalid conversion code."
END IF

Functions/Methods

1. a)

INIT value = "I love Java!"
CALL displayString()

FUNCTION displayString()
    FOR counter = 1 to 10
      DISPLAY value
END FUNCTION

1. b)

CALL displayString("I love Java!", 10)

FUNCTION displayString(message, numTimes)
    FOR counter = 1 to numTimes
      DISPLAY message
END FUNCTION

2. a)

DISPLAY "Enter radius of cylinder:"
GET radius
DISPLAY "Enter height of cylinder:"
GET height
DISPLAY "Circle Area: " + calcCircleArea(radius)
DISPLAY "Surface Area: " + calcSurfaceArea(radius, height)
DISPLAY "Volume: " + calcVolume(radius, height)

FUNCTION calcCircleArea(r)
    RETURN 2 * PI * r^2
END FUNCTION

FUNCTION calcSurfaceArea(r, h)
    RETURN calcCircleArea(r) * 2 + h * 2 * PI * r
END FUNCTION

FUNCTION calcVolume(r, h)
    RETURN calcCircleArea(r) * h
END FUNCTION