CS 99

Summer 2002: HW 1 06.27

Algorithms and the problem-solving process

Due Date: 07.02

1. Objectives

Completing all tasks in this assignment will help you learn about the process of algorithm development. In this assignment, we expect you to do the following:

· Follow all instructions

· Write clear algorithms without too much or too little information (we know this may be your first attempt)

· Write your first computer program

· Read the next section carefully and understand why Step 4 is the most important

First skim, and then carefully read the entire assignment before starting any tasks.

2. How To Solve Them

This is not a question, so much as an outline for how you should solve problems in this course—and everywhere else. Read and absorb.

The following is adapted from "How to Solve It" by G. Polya, 2nd ed., Princeton University Press, 1957, ISBN 0-691-08097-6.

1. UNDERSTANDING THE PROBLEM

• First. You have to understand the problem.
• What is the unknown? What are the data?

2. DEVISING A PLAN

• Second. Find the connection between the data and the unknown.
• You should obtain eventually a plan of the solution.
• Have you seen it before?
• Here is a problem related to yours and solved before. Could you use it? Could you use its method?
• Could you solve a part of the problem?
• Did you use all the data? Did you use the whole condition?

3. CARRYING OUT THE PLAN

• Third. Carry out your plan.
• Carrying out your plan of the solution, check each step.
• Can you see clearly that the step is correct?

4. Looking Back

• Fourth. Examine the solution obtained.
• Can you derive the solution differently? Can you see it at a glance?
• Can you use the method for some other problem?

3. A Friendly Martian
You are on the phone with a Martian who knows nothing about life on Earth. How would you explain which direction left was? Describe a procedure for doing so.

Submit your answer in a Word document called HW1.doc. Label it Question 1 in boldface.

4. Towers Of Hanoi
This example is based on a rather ancient puzzle known as the Towers of Hanoi, originating in a monastery in Tibet. Suppose we are given three pegs, A, B, and C. On the first peg, A, there are four rings piled in descending order of magnitude. The others are empty. We are interested in moving the rings from A to B, perhaps using C in the process. By the rules of the game, rings are to be moved one at a time, and at no instant may a larger ring be placed atop a smaller one. Write down the sequence of moves resolving this problem.


Next to the label Question 2 in HW1.doc, type your sequence in the form:

move A to B;
move A to C;
etc.?

5. Hyperbolic Cosine
The hyperbolic cosine function is defined by the equation

cosh(x) = (e^x + e^-x)/2

Create an M-file called HW1Q3.m. Now write a program that prompts the user for a value of x, then calculates the hyperbolic cosine of that value using the formula above. Use the program to calculate the hyperbolic cosine of 3.0. Compare the answer that your program produces to the answer produced by the MATLAB intrinsic function cosh.

At the top of HW1Q3.m, put your name, student ID, and the date. At the bottom, put your answer and the result of your comparison in commented form. Print a copy of the M-File and submit it with HW1.doc

6. Submitting Your Work
Type your name, student ID, and the date at the top of HW1.doc. Print the document and sign it along with HW1Q3.m. Staple them together and give the signed assignment to the teaching assistant.