CS 99

Summer 2002: HW 1                                                                          06/25

 

Algorithms and the problem-solving process

Due Date: 07/01

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
As it turns out, there is intelligent life on Mars, and some of them want to visit us here on Earth.  You are on the phone with a Martian who knows nothing about life on Earth, and you are trying to help him prepare to interact with humans.  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.

 

1.     Maze of Torment
This example is based on mazes, like the ones you may have played with on paper when you were a child.  Given a random starting location in any maze, is there an algorithm that you could follow that would guarantee that you would find your way out of the maze in a finite amount of time?  Spend some time thinking about this.

 

If you can think of an algorithm, write it out clearly and concisely.  Explain why it works.

If you don’t think an algorithm exists, explain why you think so.

Label this as Question 2.

 

2.     Savings Account

Suppose you open a savings account at a bank in Ithaca with an initial deposit of $100.  The bank manager tells you that your balance will grow with an annual interest rate of r, and interest will be compounded continuously.  This means that after t years, your balance, B(t), is computed using the formula:

 

B(t) = 100ert

 

Where e is the exponential function.

 

Create an m-file called balance.m.  In it, write a program that asks the user how long she has had this savings account and outputs what her current balance is.

 

Use your program to compute the balance after 1, 2, and 7.5 years.

 

Hint: Use the help and lookfor functions to find the Matlab function for the exponential function.

 

At the top of balance.m, put your name, student ID, and the date.  At the bottom, put your results from computing the balance. Print a copy of the m-file and submit it with HW1.doc

3.     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 balance.m. Staple them together and give the signed assignment to the teaching assistant.