CMSC 100 Algorithms Review and Extra Credit

October 27, 2009

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. (That is, since each homework is worth 20% of your homework grade, the extra credit can add up to 10% of the average homework grade for the class. Homework counts for 35% of your grade, so this means potentially raising your grade by 1/3 of a letter grade -- as well as practicing some more with algorithms, which will surely be on the final exam.)

To receive credit, the extra credit problems must be turned in by Thursday 11/19 (three weeks from now).

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:

procedure <NAME> (<VAR>, ...) { ... } function <NAME> (<VAR>, ...) { ... }

return (<EXPR&gr;)
Note that a function returns a value using the return statement, whereas a procedure does not (typically a procedure will print information out, and a function will not).

Assignments and Printing:

<VAR> = <EXPRESSION> print <EXPR>, ...

If Statements:

if <CONDITION> then { ... } if <CONDITION> then { ... } else { ... }

Loops:

for <ITEM> in <LIST> do { ... } for <I> from <MIN> to <MAX> do { ... } while <CONDIION> do { ... } do { ... } until <CONDIION>

Mathematical Expressions:

<VAR> <EXPR1> + <EXPR2> <EXPR1> - <EXPR2> <EXPR1> * <EXPR2> <EXPR1> / <EXPR2> <EXPR1> ^ <EXPR2> "<any string>" length (<L>) (the length of a list) <L>[<I>] (the Ith item in a list)

(<EXPR>)
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 (or the TA) your solution, we will be happy to comment on your pseudocode and give you feedback.

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 257 -- 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. Please turn these in as hardcopy (handwritten neatly) or typeset, preferably in a plain text editor (like WordPad) in a fixed-width (e.g., Courier) font.

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: 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. (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.