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.
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.”
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:
The following two videos do a great job of explaining the concept of an algorithm, and provide some examples:
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!
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:
2. Number the steps in the order that they will need to be executed:
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:
The pseudocode for the above top-down design would resemble the following:
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:
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:
5. Program!!!!!
Now that the flowchart has been made, the programming part of the task should go quite smoothly!
Planet Zirboin is a planet very far away (perhaps that’s why you’ve never heard of it).
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:
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:
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.
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?
5! = 5 x 4 x 3 x 2 x 1
5! = 120
8! = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1
8! = 40320
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:
The following flowchart could be used to write a program that calculates 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:
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?
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:
“
Written as a rule, the fibonacci sequence is xn = xn-1 + xn-2
The Fibonacci sequence is sometimes drawn as a spiral:
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
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.
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
Create a program that
Your program should use a GUI that resembles the following:
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.