Monthly Archives: August 2011

Blog, Examples

The Euclidean Algorithm

4 Comments

I remember being in school and learning about fractions. In particular, I remember the problems we had when trying to add and subtract fractions. This problem also presented itself when we tried to multiply fractions, although we still received partial credit if we couldn’t reduce fractions to their lowest terms.

What I’m referring to is the problem of finding the Greatest Common Divisor (GCD) of two numbers. The GCD of two numbers is the largest number that divides into both numbers with a remainder of zero each time. This problem has many applications, but for most of us we can relate to it because of our frustrations with fractions.

The algorithm that I’m writing about and have written a script for is called the Euclidean Algorithm, which solves precisely this problem. To be more precise, the Euclidean Algorithm finds the greatest common divisor between two integer numbers.

There are different versions of the algorithm, but the one I have implemented finds the GCD by subtracting the smaller number from the larger number, and if the result is greater than 0, the procedure repeats itself with the two lower numbers. Otherwise, the result (the GCD) is the final number that was greater than 0.

Lets see an example:
Consider the number 9 and 21.
21 – 9 = 12. 12 is greater than 0, so we repeat the procedure with 9 and 12.
12 – 9 = 3. 3 is greater than 0, so we repeat the procedure with 3 and 9.
9 – 3 = 6. 6 is greater than 0, so we repeat the procedure with 3 and 6.
6 – 3 = 3. 3 is greater than 0, so we repeat the procedure with 3 and 3.
3 – 3 = 0. 0 is not greater than 0, so can exit the loop portion of the algorithm.
Since 3 was the last positive number that we arrived at in this procedure, we see that the GCD of 9 and 12 is 3.

To learn more and see more examples, check out My Script on The Euclidean Algorithm.

Examples

Sieve of Eratosthenes

Leave a comment

Prime numbers are an important concept in Number Theory and Cryptography which often uses the difficulty of finding prime numbers as a basis for building encryption systems that are difficult to break without going through all (or a very large number of) possible choices.

Remember that a prime number is a number greater than 1 whose only divisors are 1 and that number itself. One of the most famous algorithms for searching for prime numbers is the Sieve of Eratosthenes. I added a script which implements the Sieve of Eratosthenes to my Examples page.

This algorithm prints out all prime numbers less than a given number by first canceling out all multiples of 2 (the smallest prime), then all multiples of 3 (the second smallest prime), then all multiples of 5 (the third smallest prime – multiples of 4 do not need to be considered because they are also multiples of 2), etc until we have reached a number which cannot be a divisor of this maximum number.

So if we are given a number, n, the first step of the algorithm is write out a table that lists all the numbers that are less than n. For example lets run this Sieve on 50. So all numbers less than 50 are

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.

So since 1 is not a prime number (by the definition of prime numbers), we cancel that number out.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.

Next, we look at the list and the first number that is not crossed out is a prime. That number is 2. We will put a mark by 2 and cancel out all of 2’s multiples.

1, 2*, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.

Again, we look at the list and the first number that is not marked or crossed out is 3, so that number is prime. We will put a mark by 3 and cancel out all of 3’s multiples.

1, 2*, 3*, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.

Once again, we look at the list and the first number that is not marked or crossed out is 5, so that number is prime. We will put a mark by 5 and cancel out all of 5’s multiples.

1, 2*, 3*, 4, 5*, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.

We look at the list and the first number that is not marked or crossed out is 7, so that number is prime. We will put a mark by 7 and cancel out all of 7’s multiples.

1, 2*, 3*, 4, 5*, 6, 7*, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50.

Now, we look and the first number that is not crossed out is 11. However, since 11 is greater than sqrt(50) we know that each of 11’s multiples that are less than 50 will have been cancelled out by a previous prime number. So we have finished the algorithm.

Check out my script which implements the Sieve of Eratosthenes for more examples.

Blog

The Cost of Learning

2 Comments

I often hear phrases like “the value of a college education” or “the importance of a college education”. These are phrases that I grew up on. These and many similar others have been a part of my life for as long as I can remember. What was not ingrained in my head was the cost of this education. Unfortunately, the concept of students or recent graduates struggling with debt due to student loans is not uncommon in this day and age. Generally, there are things like scholarships and fellowships available to a select few who prove themselves the cream of the crop in a matter of speaking. For the rest, though, the concept of education seems heavily related to the size of one’s pocket books.

With this in mind, I created this site to use as a resource to those who are interested in learning. I truly believe in the power of education. This belief originates from a concept that education equals empowerment. There are several examples of people throughout history using education as an asset that is only available to a select few. To those whom education was not available, neither was power.

This site is meant to empower those who wish to learn. This site is not meant to stand in place of any course covering any topic listed here. Instead, it is meant to grant exposure to those who do not have a chance to learn the fundamentals of these courses in an academic setting. This site is meant to empower workers looking to increase their skills when applying for a new job. This site is meant to serve as a refresher to those who may have learned these concepts long ago, or those students who do not understand their professor’s lectures.

I will go through a variety of topics, updating and adding to them regularly. I will cover these topics by introducing different software that I have written.

Blog, Examples

Examples Page

1 Comment

Sometimes, the most effective way to understand a new concept is to actually see it in action. On My Examples Page, I have implemented a variety of scripts to help teach many different concepts.This is the page that is the easiest for me to update, so you will regularly see changes to this page along with an accompanying blog entry at My Blog Page.

This page is focused on teaching individual concepts and/or algorithms. In particular, with the HTML5 Canvas element, I’ve been able to visualize many of these concepts. Generally I try to provide a script that executes the given algorithm (or concept) and allows for users to view these concepts on random instances. When possible, I provide a button labeled “New Problem” (or something similar) which will allow the user to view a different instance of the algorithm.

Blog, Flash Cards

Flash Cards Page

1 Comment

One of the most effective ways I remember studying for vocabulary quizzes in high school was through flash cards. During my time in college, I wondered why a similar method was not used to help study for other things, particularly in math and math-like classes where new definitions and concepts are introduced everyday. As a result of this, I wrote an initial flash cards script to help me with my advanced calculus class. Because of my success in this class, I continued developing flash cards to help study many other concepts. Here,  I have decided to share some of those concepts with you.

The general concept behind how I develop the flash cards is simple. Each flash card consists of a question on one side and the answer to that question on the other. For definitions, the question is generally of the form “What is the definition of _____” and the answer will generally go “The definition of _____ is _____”. This may vary a bit, but I try to keep it in this context to allow for searching easier. The other things I generally put onto flash cards are Lemmas/Theorems/Corollaries. These are a bit more difficult to put on flash cards though. The flash cards are still in a question and answer format, but I tried to make the question center around what the question being asked that led to the development of the Lemma/Theorem/Corollary was. Sometimes I may be off-base with these questions, and I’ve had to go back and re-do these questions a number of times. However, I hope they can be helpful.

For algorithms, which are a large part of this site, I generally asked to include the pseudocode for the given algorithm. However since pseudocode is far from formal, this can lead to a bit of a debate among whether you feel that your answer is the same as mine.

The AMS Graduate Student Blog lists some other sites where you can get math generated flash cards.