0% Complete
Minds on

MINDS ON

Have you ever used the search engine called Google? Okay, you probably have. However, considering there are other search engines, have you ever thought about why most people seem to use Google? Is it quicker, more convenient, cleaner, or nicer?

The answer to those questions might lie in the fact that years ago, when several search engines were all competing to be the web’s number one choice, Google separated itself from the others by implementing a special… ALGORITHM!

That’s right.  The developers of the Google search engine, Sergei Brin and Larry Page, developed a better way of finding information online. Their algorithm, called PageRank, resulted in more relevant and accurate web pages being returned to the user.

An image of a laptop showing the google search engine.

The PageRank system was sort of like a popularity contest for websites. It ranked webpages based on how many other pages linked to it.

“PageRank works by counting the number and quality of links to a page to determine a rough estimate of how important the website is. The underlying assumption is that more important websites are likely to receive more links from other websites” (Google).

Imagine that you are searching for information about pineapples and there are 1000 pages on the topic. The PageRank system will figure out which of the 1000 webpages has the most webpages linking to it. The idea is that if a webpage has a lot of pages linking to it, then that page must be a good source of information.

The general idea of the PageRank system isn’t too complicated, but the mathematics behind it gets a little tricky. It gets into things like a “row stochastic matrix” and “eigenvector centrality.”

The point is to understand that algorithms and mathematics are at the heart of both the hardware and software that you use every day.

Further Reading

You can read more about the PageRank algorithm by accessing the following two web pages:

The PageRank algorithm set Google apart from other search engines, leading it to be the number one search engine choice, and it was essentially the basis for the company to grow into what it is today.

So what is an algorithm?

One definition of an algorithm is “a sequence of steps, that when applied to a problem, will result in a solution.”

Dr. Peter J. Denning goes one step further to say that an algorithm must be a sequence of steps that do not include human judgement.

“...an algorithm is not any sequence of steps, but a series of steps that control some abstract machine or computational model without requiring human judgement.”

~ Peter J. Denning

Imagine creating an algorithm for baking a cake.

One instruction might be:

if cake looks done and is a bit spongy on top then

  remove cake from oven

The problem with this step is that it requires human judgement. The person has to see if the cake “looks done and is a bit spongy on top” and has to use his or her judgement. A computer could never figure this out.

A better instruction might be:

if internal temperature of cake = 210°F

  remove cake from oven

A few major characteristics of an algorithm are that:

  • Each step is an isolated, small step.
  • They occur in the correct sequence.
  • They can be automated (completed by a computer, there is no human subjectivity involved).

The following two videos do a great job of explaining the concept of an algorithm, and provide some examples:

 

 
Action.

ACTION

Algorithms are one of the central components of computer science. As you create larger programs, the use of data and the processing involved in working with this data gets more and more complex. If you can get good at designing and programming algorithms, then you will be able to create some very cool stuff!

In Computer Science there are a few algorithms that you absolutely must understand.

Some people consider writing programs with these algorithms a bit of a rite of passage in computer science. A rite of passage is “an official ceremony or informal activity that marks an important stage or occasion in a person's life”  (from the Cambridge Dictionary).

As you design and program these algorithms, you are sort of stepping into a new stage in your development in computer science. It’s time to take a closer look at algorithm design!

Designing an Algorithm

Let’s look at the different components of algorithm design by stepping through a problem and designing a solution.

Problem: Express a given number of seconds in terms of hours, minutes and seconds.

Example: Your friend told you that it took them 9331 seconds to drive somewhere. Create a program that outputs the number of hours, minutes and seconds that this represents.

The following steps will take you through the development of this program:

1. Use Top-down Design:

The top-down design will outline the steps that will be involved in terms of input, processing and output.

The input for this program will be the number of seconds.

The processing will involve converting the number of given seconds into hours, minutes and seconds. It is best to determine the number of hours first, then minutes, then seconds:

This is an image of the structure chart for the program.

2. Number the steps in the order that they will need to be executed:

This is an image of the structure chart for the program with each step numbered.

3. Create pseudocode for the algorithm:

Pseudocode is sort of like a short form of writing that is between normal English and computer programming language.

Two things are important when generating pseudocode:

  • Someone with no computer programming experience should be able to read it and understand it.
  • It should be able to be translated into any programming language (so don’t use any terms that are specific to one programming language).

The pseudocode for the above top-down design would resemble the following:

  • Get the number of seconds from the user.
  • Calculate the number of hours.
  • Calculate the number of minutes.
  • Calculate the number of seconds.
  • Output the number of hours, minutes and seconds to the user.

Now the pseudocode above is pretty good, but it doesn’t provide any details related to how you calculate the number of hours, minutes, and seconds.

You need to refine this and get more precise.  To do this:

  • Get the number of seconds from the user.
  • Calculate the number of hours: total number of seconds / 3600.
  • Calculate the remaining seconds: total number of seconds % 3600.
  • Calculate the number of minutes: remaining seconds / 60.
  • Calculate the number of seconds: remaining seconds % 60.
  • Output the number of hours, minutes and seconds to the user.

4. Create a Flowchart:

Now that you have created your algorithm, you can create your flowchart, where you will use small snippets of actual Java code:

This is an image of a flowchart for the program.

5. Program!!!!!

Now that the flowchart has been made, the programming part of the task should go quite smoothly!

This is an image of the program's source code.

This is the dropbox icon. Developing Software for Planet Zirboin

Planet Zirboin is a planet very far away (perhaps that’s why you’ve never heard of it).

This is an image of outer space with an arrow pointing to the imaginary planet Zirboin.

The planet uses money, much like you do on Earth, but their system is a little different in that they only have 6 different coins. The lowest valued coin is a vrobit.

The values for each of the other coins on Planet Zirboin are as follows:

  • 1 drobzit coin is equal to 100,000 vrobits
  • 1 clickwick coin is equal to 50,000 vrobits
  • 1 gazoontight coin is equal to 10,000 vrobits
  • 1 frazoint coin is equal to 1,000 vrobits
  • 1 blointoint coin is equal to 500 vrobits

Margaret is an alien living on Planet Zirboin who runs a travel agency that has had moderate success over the years. To supplement her travel agency income, she also collects vrobits that fall in between the cushions of alien couches. (Yes, that happens everywhere, even in other galaxies!)

She is on her way to ZirboinFinancial (it’s an alien bank) where she is going to exchange the vrobits that she has been saving over the last few years. She wants to exchange her vrobits in a way that leaves her with the fewest number of coins.

Margaret hands over 542,854 vrobits to the alien bank cashier, but there is a problem. The bank staff can’t figure out how to calculate the number of different coins they should give to Margaret. It’s alien anarchy!

Your task is to design and develop financial software for ZirboinFinancial. The software you develop should be designed with a graphical user interface and should allow the bank tellers to input the number of vrobits being exchanged.

The program should then output the number of drobzits, clickwicks, gazoontights, frazoints, blointoints and leftover vrobits that are required.

Before starting the program, you should create:

  • a top-down design
  • a flowchart
  • a pseudocode algorithm

When these are complete, you can start coding. Make sure to use a GUI for this program.

 

Did You Know?

The problems above, that use division and modulus, are sort of famous computer science problems. If you go on to take more courses in computer science, then there is a good chance you will encounter problems like these ones again. The problems won’t be related to Planet Zirboin, but they will use the same concepts.


The following are a few other computer science problems, and associated algorithms, that you need to understand.

Determining Factorials

A factorial is the product of multiplying every number together, from 1 to a given number. It’s denoted by writing n!

Does that make sense? Let’s look at an example.

The factorial of 6 would be:

6! = 6 x 5 x 4 x 3 x 2 x 1
6! = 720

Cool, eh?

This is the question/answer icon. Questions

 

  1. What is the factorial of 5?
    Answer

    5! = 5 x 4 x 3 x 2 x 1
    5! = 120

 

  1. What is the factorial of 8?
    Answer

    8! = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1
    8! = 40320

 

  1. What is the factorial of 12?
    Answer

    12! = 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1
    12! = 479001600


Now that you have been studying computer programming and computer science for a while, can you think of any concepts or ideas that could be used to write a program to calculate the factorial of a number? Notice how the numbers repeat, but decrease by 1 each time. Or, notice that when starting from 1 the numbers increase by 1 each time until the given number is reached. How would you program this in an efficient way?

Before you consider writing a program to determine the factorial of any number, maybe it would be smart to design a flowchart that shows how to calculate the factorial of one number, then you can see if you can generalize it to work with any value.

Go back to the small factorial problems above and think carefully about how your brain solves the problem.

One way to solve 5! is to follow these steps:

  1. You’re trying to find 5!, so let’s remember 5 for the first calculation.
  2. 5 x 4 = 20… remember 20 for the next calculation
  3. 20 x 3 = 60… remember 60 for the next calculation
  4. 60 x 2 = 120… remember 120 for the next calculation
  5. 120 x 1 = 120… DONE!

The following flowchart could be used to write a program that calculates 5!:

This is an image of a flowchart for determining the factorial of 5.

As you look at the flowchart above, you might notice that there is a bit of repetition when it comes to the equations being performed. You multiply the stored value by one less, each time! That is a very important discovery, because you know a way, in computer programming, to repeat a step several times and decrease by 1 each time… it’s called a for loop!

Let’s rewrite the flowchart, this time using a for loop:

This is an image of a flowchart for determining the factorial of a number.

Prime Numbers

Prime numbers are numbers that are only divisible by themselves and 1.

A number is divisible by another number if you can divide it without being left with any remainders.

12 is divisible by 6 because 12 % 6 = 0.

But 23 is not divisible by 6 because 23 % 6 = 5.

Prime numbers are important in computer science, as they are used to generate random numbers and to encrypt data.

The following video does a great job of explaining prime numbers and their importance in keeping data safe and secure:

 

Imagine you had to determine whether or not 13 was a prime number.

Your brain might do something like this:

Is 13 divisible by 2? No.
Is 13 divisible by 3? No.
Is 13 divisible by 4? No.
Is 13 divisible by 5? No.
Is 13 divisible by 6? No.
Is 13 divisible by 7? No.
Is 13 divisible by 8? No.
Is 13 divisible by 9? No.
Is 13 divisible by 10? No.
Is 13 divisible by 11? No.
Is 13 divisible by 12? No.

So, 13 is a prime number. Hooray!!

The repeated process above can be used by you to create a program to determine whether or not a number is prime. If you notice, there are some calculations in the above list that aren’t necessary to perform. The reason is that you don’t have to divide 13 by 7, 8, 9, 10, 11, or 12.

In order to determine if a number is prime, you only have to divide it by the numbers up to half of it’s value.

The following program outputs a message identifying whether or not a number entered by the user is prime.  Pay close attention to the steps involved in determining whether or not a number is prime. See how valuable the % arithmetic operators can be in programming?

An image of the source code for a prime number program.

Fibonacci Sequence

The Fibonacci sequence of numbers is a sequence that begins with 0 and 1.

0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  …

The next number in the sequence is always the two previous numbers, added together:

An image of the fibonacci sequence showing how the next number in the sequence is always the two previous numbers, added together.

Written as a rule, the fibonacci sequence is xn = xn-1 + xn-2

~ LiveScience

The Fibonacci sequence is sometimes drawn as a spiral:

This is an image of the spiraling pattern of the Fibonacci sequence.
Image from Wikimedia Commons.

The following short video does a great job of explaining how scientists and mathematicians have found the Fibonacci sequence, or spiral, represented in nature:

 

Did You Know?

When you look at any two successive numbers in the Fibonacci sequence, their ratio gets closer and closer to what is known as the golden ratio, which is approximately 1.618.

Let’s take a look:

2/1 = 1

3/2 = 1.33333

5/3 = 1.666666

8/5 = 1.6

13/8 = 1.625

21/13 = 1.61538461538

34/21 = 1.61904761905

55/34 = 1.61764705882

89/54 = 1.61818181818

The golden ratio is an important concept in design, art, and, as you’ve already seen, in nature.

You can read more about the golden ratio and the Fibonacci sequence here:

Think About It...

The Fibonacci sequence obviously progresses as a pattern. The next Fibonacci number is found by adding up the two numbers that come before it.

In other words, the number you are searching for = the number that comes before it + the number that comes before that.

Remember:

“Written as a rule, the expression is xn = xn-1 + xn-2 (from LiveScience).

Can you think about an algorithm that could be used in a computer program to output the Fibonacci sequence?

Seems like a for loop might be useful, and maybe three variables that could hold

  • the number you are looking for (xn).
  • the number that comes before it (xn-1).
  • the number that comes before that (xn-2).

Another option is to create a recursive algorithm. Recursion is "the process of defining a problem in terms of itself." (From the School Of Computing - University of Utah). It's sort of like creating a method that would call itself continously, until it reaches a base case. Sounds weird, but it's actually quite interesting, and it's a very important computer science concept. You can read more about it at the Khan Academy.

 

Consolidation

CONSOLIDATION

It’s now time to put all of your algorithm design skills to the test. Your task is to create, design and test a program that involves factorials, prime numbers and Fibonacci sequences. It should all be laid out using a beautiful GUI!

If you’re worried about it all, just remember to

  • break everything up into small steps.
  • review past activities for code, commands and debugging tips.
  • take the time to properly design the algorithms beforehand.
  • program in small steps (get one part working first, then add the next part).
  • think carefully about your test plan.

This is the dropbox icon. Algorithm Design

Create a program that

  • prompts the user for a number and finds the factorial of the number (e.g., User enters 7 and program outputs 5040).
  • prompts the user for a number and determine whether or not the number is prime (e.g., User enters 471 and program outputs “No”, user enters 751 and program outputs “Yes”.)
  • prompts the user for a number and outputs the Fibonacci number at that location (e.g., User enters 16 and program outputs 610).

Your program should use a GUI that resembles the following:

This is an image of the GUI form for the program.

Each of the three tasks (factorial, prime and Fibonacci) should be implemented in your program as a subroutine. When the user clicks the appropriate button, the correct subroutine should be called.

Before beginning the program, create a flowchart for each of the subroutines. Once that is done, combine your subroutine flowcharts into one large flowchart for the entire program.

Create a test spreadsheet for your program and list appropriate test inputs and expected outputs. Complete your test plan, indicating actual outputs and any fixes that were required. Your test plan can be created with word processing or spreadsheet software. You can use this one as a template.

 

 

test text.