CMSC 15200-1 Optional Exercises

Last updated: 08/05/05

The difficulty level of these problems is rated as follows:

[*]: Very easy. Straightforward to code.
[**]: Easy. Might require some thinking before you actually start coding.
[***]: Average difficulty. Make sure you think of the algorithm you will follow before starting. You might have to read about material not seen in class to solve this problem.
[****]: Difficult. This problem is composed of several subproblems. Make sure you lay out a plan to solve each subproblem. You will almost certainly have to look up material not seen in class.
[*****]: Very difficult. Earns you considerable bragging rights.

Week #1

[**] Write a program that, given two numbers, finds the greatest common divisor (g.c.d.) of those two numbers. Hint: Don't try to come up with the algorithm yourself. Euclid is your friend.

[**] Write a program that asks the user for two numbers expressed as fractions (i.e. for each number, you will have to ask for the numerator and the denominator). You must output the sum and product of these two fractions as a real number and as a fraction. The fraction need not be simplified, but you get extra bragging rights if you do simplify the fractions.

[**] Integer division by successive subtraction. Given two integer numbers A and B, compute the integer quotient A/B and the integer remainder. You must do this using only the subtraction operator.

[*] Write a program that, given dimensions x and y, will output a rectangle composed of x times y asterisks. e.g. Given x=5 and y=3, the program should output:

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

[**] Modify the above program so the output will be a checkerboard of asterisks and hyphens. e.g. Given x=5 and y=3:

*-*-*
-*-*-
*-*-*

[**] Encapsulate the above program in a function with four parameters: x, y, char1, char2 (char1 and char2 are the two characters used in the checkerboard). The user must specify these four parameters, and the main program will use them to invoke the function.

[**] Absolute C++, 2nd Edition, Chapter 2 programming project 2, pg 92.

[**] Write a program that asks the user for 15 numbers, and then writes them on the screen in inverse order.

[**] Write a program that computes the solution to the quadratic equation A·x² + B·x + C = 0. The user will specify A, B, C and the program will take into account the following cases:

If A=0, B=0, and C=0, then tell the user that he/she has specified the identity 0=0.
If A=0 and B=0 then the equation has no solution.
If A=0 then warn the user that he/she has specified a linear equation, but output the solution nonetheless (-C/B).
Otherwise, we will be concerned with the value of the discriminant (B²-4·a·c). In your program, write a function that computes the value of the discriminant and then:

If the discriminant is greater than 0, then there are two different real solutions. Print the solutions.
If the discriminant is 0, then there is a unique real solution. Print the solution.
If the discriminant is less than 0, then there are two different complex number solutions. You are not required to print out these solutions.

[***] Write a program that asks the user for 15 numbers. The program sorts the list of numbers (in increasing order) and then prints out the numbers on screen. Sorting algorithms will be explained in the third week. For this exercise, you must look up an existing sorting algorithm (we recommend simple algorithms like bubblesort or insertion sort) and use it in your program. You are free to use existing implementations, as long as you cite your source. Also, you are encouraged to look at the algorithm and mentally follow its steps to see how it works.

[***] Write a program to convert between different units of measurement:

Length: Meters, kilometers, inches, miles
Area: Square meters, acres
Volume: Cubic meters, litres, gallons
Weight: Grams, kilograms, ounces, pounds

The program must ask for the following:

Initial unit of measurement (user must choose from a list displaying all the above units of measurement)
New unit of measurement (user must choose from a list)
Quantity (user must type in a number)

The program must convert the quantity from the initial unit of measurement to the new unit of measurement. You can use fictional conversion ratios, but you must check that the initial and new units are coherent (e.g. you must allow the user to convert from meters to miles, but not from gallons to inches).

NOTE: This problem can be solved two different ways. One way is by including a huge boolean expression to check that the two units of measurement are coherent, and then using a separate if-then statement for every possible pair of coherent units of measurement. This is generally regarded as 'caveman programming'. You are encouraged to solve this problem in such a way that making the actual conversion (regardless of the units chosen) requires one simple statement. Hint: Think of how you would structure this program if you foresaw that you will be adding new units of measurement to the program in the future.

Week #2

[**] Write a program that, given a string, determines the number of words in the string. You can assume that the space character ' ' is the only possible separator between words.

[***] Write a program that, given a string, determines the number of times each letter of the alphabet appears in the string.

[***] Rewrite the two previous programs to work with text files, not with strings typed by the user. For the word-counting program, you will have to take into account that a newline also qualifies as a word separator.

[**] Write a recursive function to compute the power of a number. In other words, given a and x, your function must recursively compute a^x.

[***] Implement the following functions. Unless specified, it is up to you to determine what the return type and parameter types must be. You must also write some code in the main() function to show how your functions must be invoked.

void invertArray(???);
Takes a 1-dimensional array and inverts it.
??? multiplyMatrix(???);
Takes two 2-dimensional array, multiplies them, and stores the result in a third 2-dimensional array. This third array must be passed as a parameter.
??? multiplyMatrix(???);
Same as above, but the third array (the one with the result of the multiplication) must not be passed as a parameter.
??? strcmp(???);
Implement the standard strcmp function recursively (make sure you define your recursive and base cases correctly).

[**] Assume you have a text file with a list of numbers (one integer per line). You must write a program that takes that file and creates two new files, one with the odd numbers and one with the even numbers. Your program must do this by making a single pass through the text file and without loading its contents into memory. Note: The ordering in the source and target files is not significant.

[**] Assume you have a text file with an ordered list of numbers (one integer per line). You must write a program that asks the user for a number and then creates a new text file with the numbers from the original file and the number specified by the user (in the correct position so the resulting list of numbers is still in increasing order. Your program must do this by making a single pass through the text file and without loading its contents into memory.

[****] Implement a prefix notation evaluator. An expression written in prefix notation (also called polish notation), places the operator before the operands. For example:

+ 2 3

This expression evaluates to 5 (and is equivalent to the infix expression 2 + 3). An attractive feature of prefix notation is the fact that it does not require parentheses to determine the order in which the operators must be evaluated. For example:

+ * 1 5 / 9 3

Evaluates to:

+ 5 3

And then to 8. We could rewrite the original expression with parentheses, although they would be redundant:

(+ (* 1 5) (/ 9 3))

Your program must ask the user for a prefix expression, and output the value it evaluates to. You will only consider the addition, subtraction, multiplication, and division operators (for extra bragging rights, you can consider the unary negation operator). Hint: This problem can be solved relatively easily using a recursive algorithm.

Week #3

[***] Implement a postfix notation evaluator using a stack data structure. Postfix notation (and how to write an evaluator using a stack) was described in class. You can also find a good introduction here.

<-- Back to main page