CMSC 100 Algorithms Review and Extra Credit
The goal of this handout is to give you three things:
(1) a summary of pseudocode constructs that
you should be using in your pseudocode algorithms; (2) some
practice problems that you can get feedback on if you wish;
and (3) optional extra credit problems that you may turn in for credit.
The total amount of credit that you can receive is equal
to half a homework assignment, and will be added to your homework
grade.
To receive credit, the extra credit problems must be turned in by
Friday, 12/16 via Blackboard.
Pseudocode Summary
Here is a list of constructs that you should be using in your
pseudocode. There is generally no reason to use anything else (other
than specific mathematical functions that I may provide from time to
time). If your pseudocode doesn't look like these constructs in its
syntax, you're probably doing something wrong.
The syntax <NAME> means that an expression (i.e., a
variable name, a constant, or a mathematical expression)
should appear
in this location (but it doesn't have to have the same name I've used
here). A condition means that the variable name, constant, or
mathematical expression should evaluate to either TRUE
or FALSE.
Procedures and Functions - defines a named block of code and the data that it requires
- procedure <NAME> (<VAR>, ...) { ... }
- function <NAME> (<VAR>, ...) { ... }
- return (<EXPR>)
example:
function findItem(List L, item)
defines a function called findItem that requires a list that will be assigned to L and some value that will be stored in item.
Assignment - stores a value in a named memory location
- <VAR> ← <EXPRESSION>
- <VAR> <- <EXPRESSION>
example:
count ← 45
assigns the value 45 to a memory location called "count". This value can be retrieve by referencing "count" in an expression. E.g.,
print count+1
prints 46. Note that value stored in count does not change. However, a command like
count ← count+1
Evaluates the right side of the assignment, coming up with 46. Then that 46 is assigned to count.
Output - prints a value
If statement - execution based on a condition
- if <CONDITION> then { ... }
- if <CONDITION> { ... }
- if <CONDITION> then { ... } else { ... }
- if <CONDITION> { ... } else { ... }
Loops - repeat code
- for <VAR> in <LIST> { ... }
- for <VAR> in <LIST> do { ... }
example, assuming bunchOfNames is a list:
for someVariable in bunchOfNames
will run the code in the loop with someVariable equal to the first element of the list, then again with someVariable equal to the second element of the list, then again with someVariable equal to the third element of the list...
- for <VAR> from <MIN> to <MAX> { ... }
- for <VAR> from <MIN> to <MAX> do { ... }
for aNumber from firstNumber to lastNumber
will run the code in the loop with aNumber equal to firstNumber, then again with aNumber equal to firstNumber+1, then again with aNumber equal to firstNumber+2, until lastNumber is reached.
- while <CONDIION> do { ... }
- do { ... } until <CONDIION>
a while loop tests a condition, and then runs the code while the condition is true (i.e., test, run, test,..., run, test). A do-while loop runs the code first, and then tests the condition, and runs the code while the condition is true (i.e., run, test,..., run, test, run, test).
Mathematical Expressions:
- <VAR> (e.g., sum)
- <EXPR1> + <EXPR2> (e.g., sum + otherValue)
- <EXPR1> - <EXPR2>
- <EXPR1> * <EXPR2>
- <EXPR1> / <EXPR2>
- <EXPR1> ^ <EXPR2>
- "<any string>" (e.g., "hello")
- length (<L>)  (the length of a list) (e.g., length(listOfNames)
- <L>[<I>]  (the Ith item in a list) (e.g., listOfNames[4])
- (<EXPR>) (e.g., 4)
These constructs can be nested and combined.
Other standard mathematical operations (log, sqrt (square root),
abs (absolute value), etc.)
are also fine to use (unless, of course, that's what you're told to
compute, as in practice problem #3).
Logical (Boolean) Conditions:
- <COND1> and <COND2>
- <COND1> or <COND2>
- not <COND2>
- <EXPR1> == <EXPR2> (test for equality)
- <EXPR1> > <EXPR2>
- <EXPR1> < <EXPR2>
- <EXPR1> >= <EXPR2>
- <EXPR1> <= <EXPR2>
Note that the comparison operators can also be applied to strings
(to test whether they are equal, or in alphabetical order).
As with mathematical expressions, these constructs can be nested
and combined.
In some cases, I may indicate particular functions
that you can use (e.g., even(<EXPR>) to test whether
an integer expression is even or not).
Practice Problems
Here is a list of algorithms that you can try to write
if you want more practice in thinking about algorithm
design.
Since these problems are not for credit, if
you email me your solution, we will be happy
to comment on your pseudocode and give you feedback.
Practice Problem #0 (easy)
a)What does
function doThis(list listOfNumbers){
for sum in listOfNumbers{
print sum
}
}
print out if called with doThis(2,3,5,7,11) ?
b)What does
function doThis(list listOfNumbers){
for sum in listOfNumbers{
if sum > 5{
print sum
}
}
}
print out if called with doThis(2,3,5,7,11) ?
Practice Problem #1 (easy)
Write a function that is given a list of students' grades (on a scale
from 0 to 100), and returns the number of students who have an A in
the class (grade >= 90).
Practice Problem #2 (easy to medium)
A student's grade is based on a midterm (15% of the grade), final exam
(40% of the grade), and three homework assignments (45% of the grade:
15% each). Write a procedure that takes as input five arguments (HW1,
HW2, HW3, midterm, and final, all on a scale from 0-100), and prints
four messages:
- The student's two exam grades
- The student's average homework grade
- The student's total grade average
- The student's letter grade (using the cutoffs 90%=A, 80%=B, 70%=C, 60%=D, <60%=F)
Practice Problem #3 (medium to hard)
(Brookshear Chapter 5 Review Problem #43, page 236 -- algorithm only.)
Design an algorithm to find the square root of a positive number by
starting with the number itself as the first guess and repeatedly
producing a new guess from the previous one by averaging the previous
guess with the result of dividing the original number by the previous
guess.
Hint: Unless the original number is a perfect square, you'll never
find the exact square root, since it must be an irrational
number. Therefore, your loop should stop not when the guess times
itself equals the original number, but when the guess times
itself is within epsilon (for some very small value of epsilon,
like 0.00001) of the original number. Think hard about how to check
for this condition!
Practice Problem #4 (hard)
Write a procedure that is given a sorted list of strings as its
argument, and prints out all of the strings that appear exactly once
in the list.
Practice Problem #5 (hard)
Write a function that "cycles" a list, by moving each element
one place earlier in the list, and moving the first element to the last
place in the list. Note that because you'll "lose" each element when
you write into that space, you'll need at least one variable
that is used to hold a value temporarily while writing the
other values into their new locations.
Hint: Imagine yourself doing this with a list written on the
whiteboard. To write each number one place over, you first have
to erase what was there. Imagine that you have zero short-term memory
so you have to save what you are about to erase by writing it somewhere
else to keep track of it. How would you go about doing this?
Extra Credit Problems
These problems may be turned in for credit, as explained above.
You may turn in any subset of the problems, but you should turn
everything in at one time, and before the deadline in order to receive
credit.
Extra Credit Problem #1 (easy: 5 points)
Write a procedure Rectangle that takes as input the lengths
of two adjacent sides of a
rectangle, and prints the rectangle's area, circumference, and a
message saying whether the rectangle is a square or not. For example,
Rectangle (3, 3) should print:
The area is 9.
The circumference is 12.
The rectangle is a square.
Extra Credit Problem #2 (easy: 5 points)
Write a procedure that takes as input a list of numbers (not
necessarily sorted),
and prints out the largest and smallest numbers in the list.
Extra Credit Problem #3 (medium: 10 points)
Write a procedure that takes as input a starting bank balance, a monthly
interest rate (which will be between 0 and 1),
and a number of months, and prints the new balance
after each month. (Recall that the formula for computing
a balance with an interest rate is
new_balance = old_balance * (1 + interest_rate)
At the end, the procedure should print the total amount of
interest that was earned. For example, ComputeBalance (100,
.05, 3) would print:
The starting balance is 100.
The balance after month 1 is 105.
The balance after month 2 is 110.25.
The balance after month 3 is 115.76.
The total amount of interest earned is 15.76.
(Don't worry about rounding off; you can just print
the balance you've computed and assume that the print
statement will format/round it correctly.)
Extra Credit Problem #4 (hard: 15 points)
Write a function that takes a list L as input, reverses
the list, and returns the reversed list as output.
You may assume that the length of the list is even.
Note that because you'll have to swap values (e.g.,
the first value in the list with the last value in the
list), you'll need at least one variable that is used
to hold one of these values temporarily while writing
the other value into that location. (This problem is
a bit similar to Practice Problem #4.)
Extra Credit Problem #5 (hard: 15 points)
Write a function CountOverlap
that takes two sorted lists of strings, L1 and L2,
and counts the number of times that the same string appears in both
lists. (This number should be returned by the function.)
You may assume that the same string doesn't ever appear twice
within a single list.
For example, CountOverlap (["banana", "cherry", "pear"],
["apple", "cherry", "pear", "quince"]) should return
the value 2.