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:
- Run the Lab software and select the "C++ Compiler" option
- Cut and paste a sample program into the left hand pane.
- Select Compiler/compile.
- assuming no errors:Compiler/execute
- In the window that pops up: cluck on the run button.
//enter functions here if needed
//enter 'main' program here
Visual C++ express edition
edit the code so it looks like:
- New Project
- typer in name and select Win32
Win32 console application
// Firstprog.cpp : Defines the entry point for the console application.
to create an initial application we add the line:
using namespace std;
int _tmain(int argc, _TCHAR* argv)
// write your program here
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) :
What I want you to do:
- ASk the user for a target value (number that we are searching for). Store it in a place called "target".
- In a store which we are calling "index" place the number 1 (zero in my software).
- A Store called "found" can store the value 'false' because we haven't found it yet.
- Loop through steps 6 7 and 8 while the found variable is false
- --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
- ----Output the index value "found value at position..."
- ----Put the value "true" into the store found
- ----(Else) Increment (add one to) the value in index so next time through we look at the next position.
- If found is false
- --Output that value was not found
- Run the program 8 times searching for the value in each of the 8 positions.
- For each, count the number of times each step is executed.
- Total the steps for each case.
- Sketch a quick graph of positions VS total steps.
- Hypothesise how many steps would be involved in finding a value in the nth position.
- Suppose it was in the 1000th position.
- True or false: The time taken to search for a value depends only on the length of the list searched.
Search for Largest
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.
- Set the value of a store called "maximum" to the first value in the list.
- Set locmax (the location of the maximum found so far) to the first postion on list (1 or 0 if my program).
- Set the store "index" to the second position (2 or 1 if my program).
- Loop through steps 5,6,7 and 8 while index is not past the last position in list.
- --IF the value at the position given by the index is greater than that at position locmax do steps 6 and 7
- ----Set maximum to value at index
- ----Set locmax to index
- --increment index (add one to it
- Print out maximum (the biggest value found) and locmax (where is is stored).
- Stop? Is this a step? It wasn't on the previous one.
Home Page of RDScience
- How many different ways can we order 8 numbers? N numbers?
- 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 ?
- How many different position can the greatest value be in.
- Could the locmax take on 8 values? If so when.
- If the greatest value was in the fourth position in what ways might locmax value would go directly from the first position to fourth?
- 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?