Lab 3

A look Ahead to programming

In a few weeks we will start programming. I would like to give you the opportunity to get ahead of the game. I am not touching the subject of programming, but I want you to be able, should you wish, to download programming software that is uperior to that given away in the book.

Using the textbook's software

Cut and paste the following program:
#include <iostream.h>

//enter functions here if needed

void main()
{
//enter 'main' program here
cout<<"Hello cheeky!"<<endl;

}

Visual C++ express edition

edit the code so it looks like:
// Firstprog.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
//void tmain()
{
// write your program here

return 0;
}
to create an initial application we add the line:
cout<<"hello cheeky!"<<endl;
after the line "write your program here".

Lab 2 from the Book

Today I want to do 'Experiences' 2 and 3 from the book. If you don't have a book I have written simple implementation of the algorithms that will get you by.
You may submit answers either on the tear out from the book or on regular paper

Search For Value

Searching for a single value, as we do here is straightforward. However, Searching is not trivial. Consider the geneticist who has a file that represent the bases (C,A,G or T) on a strand of DNA. They want to look for a sequence (gene or partof gene?) within the overall file. To make matters worse, parts might be missing or added or changed or repeated or put in backwards.... its not trivial. DNA sequences are often very long.
Here we are looking for a target number in a list of numbers. This algorithm includes an initial set up, a loop (while) and a decision ("if"). The algorithm requires that we have places where we can store data. We have a list ("array") of numbers that we are searching. We have a store called `target` which contains the number that we are looking for in the main list, and we have a store called `found` that remembers whether we have found our target value in the main list. Stores (which we usually called `variable if we want to be able to change their contents, know the type of data that they store. All of these stores are of type `integer` except for the on called `found` which is a true/false variable. We call these "bools". Often there is a compromise with algorithms -a faster algorithm uses more storage space. Note that the book counts positions starting at position 1. My software starts in position 0. This is confusing but I have my reasons.My Pseudocode (with Step numbers is) :
  1. ASk the user for a target value (number that we are searching for). Store it in a place called "target".
  2. In a store which we are calling "index" place the number 1 (zero in my software).
  3. A Store called "found" can store the value 'false' because we haven't found it yet.
  4. Loop through steps 6 7 and 8 while the found variable is false
  5. --If the value in the array at the position given by the index store is equal to our target value do 6 and 7 else do 8
  6. ----Output the index value "found value at position..."
  7. ----Put the value "true" into the store found
  8. ----(Else) Increment (add one to) the value in index so next time through we look at the next position.
  9. If found is false
  10. --Output that value was not found
What I want you to do:
  1. Run the program 8 times searching for the value in each of the 8 positions.
  2. For each, count the number of times each step is executed.
  3. Total the steps for each case.
  4. Sketch a quick graph of positions VS total steps.
  5. Hypothesise how many steps would be involved in finding a value in the nth position.
  6. Suppose it was in the 1000th position.
  7. True or false: The time taken to search for a value depends only on the length of the list searched.

Search for Largest

  1. Set the value of a store called "maximum" to the first value in the list.
  2. Set locmax (the location of the maximum found so far) to the first postion on list (1 or 0 if my program).
  3. Set the store "index" to the second position (2 or 1 if my program).
  4. Loop through steps 5,6,7 and 8 while index is not past the last position in list.
  5. --IF the value at the position given by the index is greater than that at position locmax do steps 6 and 7
  6. ----Set maximum to value at index
  7. ----Set locmax to index
  8. --increment index (add one to it
  9. Print out maximum (the biggest value found) and locmax (where is is stored).
  10. Stop? Is this a step? It wasn't on the previous one.
The exercise is to do this experiment at least 10 times and to see how many times the locmax changes in each. Then plot this as a function of the position of the maximum. Questions:
  1. How many different ways can we order 8 numbers? N numbers?
  2. Describe how you can look at a dataset and see the positions (values) that locmax can take. Without using the program, what values would it take for 5,3,8,1,11,10,9,12 ?
  3. How many different position can the greatest value be in.
  4. Could the locmax take on 8 values? If so when.
  5. If the greatest value was in the fourth position in what ways might locmax value would go directly from the first position to fourth?
  6. Suppose that the time taken by the algorithm was entirely determined by changing locmax. If the number of values to be searched increased from 8 to 8 million. Would the time taken increase by exactly a million? More than a million? Slightly less? Much Less than a million?
Home Page of RDScience