Our first look at the algorithm

10 minute presentation:


The Advent of the Alogrithm


This is an introduction to computer science and programming in a nutshell...Explicit instructions. This way of thinking will help you for years to come.

If you understand the simple rules of logic behind the microprocessor, the infinite possibilities of the computer revolution will be clear.

Imagine every calculation reduced to a series of true/false conditions. The steps that the program run through are known as an algorithm. To easily understand how such programs work, we will be utilizing pseudocode. Learning a computer language is secondary to understanding computer science. Therefore, we will not be discussing anything in particular such as Javascript or Visual Basic. What you will find, however, is that this simple introduction will provide the framework to easily write code in any programming language. Computer science is not dependent on any particular language or physical computer even.

Remember, to a CPU everything is reduced to true/false as a bit. This bit is either (1) on or (0) off. Remember, zero is a number!

We'll start with a real world example from the classroom.

Let's say students Bill and Jose are given a test

Bill got a 70
Jose got a 80


The only way the class can receive a special prize is if each student gets better than a

65. It isn't the average score that counts-
each score must be over 65.

if Bill > 65 AND
if Jose > 65

Then
Class gets a surprise!

Else
Class gets a punishment!

Because each student got a higher score than 65, the condition immediately following is completed. The class will get a surprise. If we imagine the logic gates discussed earlier, you can make a connection between the conceptual and the physical implementation. The computer's power is not wholly evident in such an example: for that, consider thousands of students and the situation quickly changes.

Imagine the situation if only one of the students need score above 65. With the same scores, we have:

if Bill > 65 OR
if Jose > 65

Then
Class gets a surprise!

Else
Class gets a punishment!

As we substitute Bill's score of 70, we have a true statement (1). The OR only needs one aspect to be true, so Jose's score need not even be considered for the statement to be true.

Let's consider a case where one of the students didn't study hard enough.


Bill got a 20
Jose got a 90

if Bill > 65 AND
if Jose > 65

Then
Class gets a surprise!

Else
Class gets a punishment!

Obviously in this case the AND is not satisfied because all of the conditions were not true and the class is in for a stern punishment!
---

To review, our algorithm is always correct in returning whether the class is deserving of the surprise or the punishment. In this case our pseudocode has been hard coded, or given the values, before the program runs. We could just as easily have asked the user for the data and used the same conditions as before.

Grader

Ask user for first grade
Ask user for second grade

if first_grade > 65 AND
if second_grade > 65

Then
Class gets a surprise!

Else
Class gets a punishment!

Depending on the input of the user, we do not know whether the class will be commended or condemned! Such a program is dynamic.

---
Determine which is the largest.

Jill got a 55
Jose got a 80
Bill got a 70

One possibility is for the program to consider the first number to be the largest and compare it with the second number and then the third.

largest = Jill
if Jose > largest then
largest = Jose
if Bill > largest then
largest = Bill



THIS IS HOW COMPUTERS HANDLE DATA! It is not mysterious and can be understood quite easily.


----

Let us now consider a very real world example with political implications.

1. Start with the boundary outline of the state.
2. Let N=A+B where A and B are as nearly equal whole numbers as possible.
(For example, 7=4+3. More precisely, A = ?N/2?, B=?N/2?.)
3. Among all possible dividing lines that split the state into two parts with

population ratio A:B, choose the shortest. (Notes: since the Earth is round, when we say

"line" we more precisely mean "great circle." If there is an exact length-tie for

"shortest" then break that tie by using the line closest to North-South orientation, and

if it's still a tie, then use the Westernmost of the tied dividing lines. "Length" means

distance between the two furthest-apart points on the line, that both lie within the

district being split.)
4. We now have two hemi-states, each to contain a specified number (namely A and B) of

districts. Handle them recursively via the same splitting procedure.

Recursion is powerful!

http://www.rangevoting.org/GerryExamples.html

---

Often pseudocode and the underlying logic can be identified with a flow chart.



----

Consider all the different forms of algorithms:
-sorting algorithms
-cryptographic algorithms
-scheduling algorithms
-genetic algorithms
-optimization algorithms
!!!

----

Lastly let's examine a mathematical algorithm with a while statementexample with students:

x = 5
y = 10

while x < x =" x" 10="15," 10="16," 10="19." x =" 5" y =" 10"> 4
display x
x = x+2
end while

What will be displayed?

That's right 8 and 9!
----

We have seen that algorithms must have clear instructions that have a stopping point.
You can imagine following the instructions to a recipe as an algorithm.

Washing your hair? Lather, rinse, repeat. You're stuck in an infinite loop :)