Computer Algorithms I CS 305 Class Notes

Lecture Notes for Computer Algorithms I

4 September 2003 - Programs and Problem Solving

Art and Science

Solving problems with programs uses both science and art.
- Science gives you the building blocks.
- Art tells you how to stack the building blocks.
Good programmers are both scientists and artists.
- A scientist without art rarely adapts to new problems.
- An artist without science rarely produces effective solutions.
Good science can be taught; good artistry cannot.

Five Easy Pieces

Solving a problem with a program takes five steps:
1. Understanding the problem.
2. Designing the solution.
3. Coding the solution.
4. Testing the solution.
5. Maintaining the solution.

Understanding the Problem

You can't solve a problem you don't understand.
The two keys to understanding are questions and assumptions.
- Questions indicate things you don't understand.
- Assumptions indicate things you think you understand.
Questions eliminate things you don't know, including assumption.
Assumptions let you get on with it.

A Searching Example

Problem: Given an array, find an element as quickly as possible.
Do you understand this problem? Why not?

Ask Good Questions

Good questions are the hallmark of intelligent people.
A good question shows knowledge and thoughtfulness.
- I understand the problem, not the solution.
- I thought this was the solution, but it's not.
And remember, there are such things as stupid questions.
- Questions that have already been answered.
- Questions that you're too lazy to answer.
  - Also known as RTFM questions.

A Searching Example

Problem: Given an array, find an element as quickly as possible.
Do you understand this problem? Why not?
What questions should you be asking?
- Find what element?
- How quick is "as quickly as possible"?
- What if the element's not there?
- What if it's there? What do you want back?
- How big is the array?
  - This is a borderline good (C++)-bad (Java) question.

Make Good Assumptions

Good assumptions are the hallmark of skillful practitioners.
A good assumption is plausible and enhances the problem.
- Although not specified, the likely parameter values are...
- By assuming a general distribution, we can eliminate restrictions...
Document and check your assumptions.
- They may be wrong, you may have to make new ones.
- You should work to remove them by asking questions.

A Searching Example

Find what element?
- Assume the element's given along with the array.
How quick is "as quickly as possible"?
- Assume it means "faster than one-by-one search".
What if it's there? What do you want back?
- Assume we return the element's array index.
What if the element's not there?
- Return an invalid array index.
How big is the array?
- (C++) Assume it's input along with the array and search element.

Designing the Solution

Wishful thinking is a powerful design technique.
- What do you need to solve this problem?
- *Poof* there it is.
- Take it and solve the problem.
Where does that *poof* come from?
- Unless you have a genii, you have to provide it.
- You can use wishful thinking again.
This is known as top-down design.
- Start with a high level solution and refine it downwards.

A Searching Example

What do we wish we had to solve this problem?
- A function accepting an array A, an element e, and an array size, and returning the index of e in A or -1 if e isn't in A.
O.k. *poof*, there you go - problem solved.
- extern int find(int a[], int e, int n)
Well, maybe; where do I get find()?
- Time to make another wish.
I wish I had a function to tell me if e is in half of A.
- O.k. *poof* here you go.
```
extern bool 
in_half(int a[], int left, int right, int e))
```

Make A Wish

With wish in hand, we continue:

int find(int a[], int x, int n)

  left = 0
  right = n

  while left < right
    mid = (left + right)/2
    if in_half(a, left, mid, x)
      right = mid
    else
      left = mid

  return a[left] == e ? left : -1

O.k., but where do I get in_half()?
- There's an amusing assumption required. What is it?

Coding the Solution

You're communicating with other people when you write programs.
- Other people and yourself later on.
- You should write your code to make communication possible, effective and easy.
Program defensively: assume nothing and check everything.
- If you've made assumptions, make sure they're true.
- Your program should never, ever crash on any possible input.

Class Coding Standards

Every function contains at most 30 semicolons.
A function with more than 30 semicolons loses points.
- One point for every five semicolons over 30, rounded up.
- A function with 42 semicolons loses three points.
  
  ceiling((42 - 30)/5) = ceiling(12/5)
  
  = ceiling(2.2)
  
  = 3

Testing the Solution

I'll be testing your code; you probably want to test your code before I do.
You should become proficient in a scripting language, and possibly make.
- I use TCL, shell (ksh-bash), and (gnu) make, mostly.
- Any scripting language will do.
Testing works well with design by wishful thinking.
- Write new tests after every wish has been granted.
  - That is, you refine a new solution.
- Run all the tests every time.
A few simple tests usually do the trick.

A Searching Example

How can we test find()?
- Look for an element in an array; look for an element not in an array.
How about in_half()?
- Same procedure: look for something in one half, look for something in the other half, look for something in both halves, look for something in neither half.
Testing tip: when you find a mistake, write a test to exercise it before you fix it.
- This one of the ways I test your code.

Maintaining the Solution

Your assignments in this class are cumulative.
- You'll need assignment n - 1 for assignment n.
Make sure you're able to go back and easily make changes.

Class Documentation Standards

Every function should have a comment giving a brief, complete description of the function.
A comment is complete when it describes
- all the input values,
- all the output values,
- how input gets translated to output.
A brief comment describes behavior, not operation.
- Do not describe code.
Every function without a comment or with a non-brief or non-complete comment loses a point.

Example Function Comments

Good:

int find(int a[], int e, int n) {

  // Return the index of the element e 
  // in a[0..n-1], or return -1 if e 
  // isn't in a[0..n-1].

Poor:

int find(int a[], int e, int n) {

  // Look for e in a.

Terrible:
```
int find(int a[], int e, int n) {
```

This page last modified on 4 September 2003.

ceiling((42 - 30)/5)	= ceiling(12/5)
	= ceiling(2.2)
	= 3