Author: technologeo

Intro to Modular Arithmetic

technologeo

We’ve already seen a bit of Modular Arithmetic in the previous lesson (Number Bases and Conversion). In this lesson we will delve a little deeper and explore Modular Arithmetic further.

When dividing two integers we can break down the parts of the division equation into several components. Those components are the Dividend, Divisor, Quotient and Remainder. If expressed as a formula they look like the following:

Dividend/Divisor = Quotient and Remainder

Modular Arithmetic in Number Theory focuses on the Remainder component or what is referred to as the Modulo Operation, Modulus or Mod for short.

Dividend mod Divisor = Remainder

Example: What is 23 mod 7 ?

  • 23/7 = 3 remainder 2
  • Since the mod operation only cares about the remainder
  • 23 mod 7 = 2

Modular Arithmetic and Clocks

What does Modular Arithmetic have to do with Clocks? A lot! In fact, one very useful way to understand Modular Arithmetic is by thinking of clocks and how we use them. A clock has the numbers 1 – 12 on its face. Once we pass 12 o’clock we start again at 1 o’clock and continue in a circular manner. Another way we tell time is with a 24-hour system commonly used by the military. In this system we have the usual hours 1 – 12, but instead of starting at hour 1 again after we pass hour 12, we count hours 13, 14, 15 and so on until 24. In this 24-hour system the 13th hour or 13 o’clock is like 1 o’clock, 14 is like 2 o’clock, 15 like 3 o’clock and so forth. Notice a pattern?

If we extend this idea past 24 hours, we can say that 25 o’clock is also like 1 o’clock or 13 o’clock because they both wrap around the clock and land on the 1 o’clock position. In this clock system we can represent where we are in relation to the numbers 1 – 12 (or 0 – 11 as illustrated). That means that 1, 13, 25, 37, 49 … fall on the same position on the clock and are thought of as the same. 2, 14, 26, 38, 50 … are also thought of as the same.

Image Source: https://mathstats.uncg.edu/

In other words, 13 = 1 + a multiple of 12. 26 = 2 + a multiple of 12. Another way to express this is by saying that 1 is the remainder when we divide 13 by 12. 2 is the remainder when we divide 26 by 12. Mathematically, we write this as 13 ≡ 1 mod 12, 26 ≡ 2 mod 12, etc… This is read as 13 is congruentHaving the difference divisible by a given modulus to 1 mod (or modulo) 12. 26 is congruent to 2 mod 12.

There are many different mods we can work in. Above, we worked in Mod-12. Whatever mod we work with, it is always helpful to think of a clock face with that many numbers. Mod-8 for example can have a clock face numbered 1 – 8 (or in a similar fashion 0 – 7, like our illustration above). Remember that when we pass our highest number, we reset to 1 again.

If we put together what we’ve learned so far, we can formulate a general concept regarding mod. Namely, if we are working in a system of Mod-N (N being a whole number), we write a ≡ b mod n if a and b result in the same remainder when you divide them by n. In other words, a ≡ b mod n if n divides a−b.

Example: What is 17 mod 5?

  • We can divide 17 by 5 and whatever the remainder is, is our answer.
  • 17/5 = 3 remainder 2.
  • 17 mod 5 = 2
  • Alternatively, we can continually subtract 5 from 17 until we are left with a number less than 5 (1, 2, 3, or 4).
  • 17 – 5 – 5 – 5 = 2

Example: What is -3 mod 4?

  • Negative or positive numbers, mods work the same way.
  • -3 + 4 = 1

A helpful thing to remember is that if we have a mod b and we increase a by a multiple of b, we get the same result.

For example, the following are all equal to the same number.

  • 3 mod 7 = 3
  • (3 + 7) mod 7 = 10 mod 7 = 3
  • (3 + 14) mod 7 = 17 mod 7 = 3
  • (3 + 21) mod 7 = 24 mod 7 = 3
  • (3 + 28) mod 7 = 31 mod 7 = 3

You may come across notation that states: a ≡ b mod c. This simply means that a is the same as b when taken mod c.

For example, 3, 10, 17, 24, and 31 are all equal to 3 when taking mod 7. See the examples above. Therefore, we can say:

  • 3 ≡ 10 mod 7
  • 10 ≡ 31 mod 7
  • 24 ≡ 17 mod 7
  • … and so on

Number Bases and Conversion

technologeo

Human beings are most comfortable or familiar with counting using the numbers 0 – 9. This is also referred to as the Base-10 system. We call it the Base-10 system because there are exactly 10 symbols or numbers/digits represented.

From an early age we are taught to use these numbers and after some time it becomes second nature. This is why Base-10 feels so natural to us. Base-10 systems have existed for a very long time too. Many civilizations throughout history have used a Base-10 numbering system. In fact, it is widely accepted that the reason we use Base-10 and not some other arbitrary number system is because humans have 10 fingers!

What is a Number Base (Radix)?

A number base, radix, or “base” for short is a system of counting that describes numbers using symbols (such as numbers and letters) to represent values. The base of a number system also tells us how many unique number notations exist.

For example, Base-2 or the binary numbering system has exactly 2 unique numbers used to express different values (0 and 1). Binary is used in programming and this makes sense because computers “think” in binary. This isn’t the only number base that we often see in programming.

Another example of a programming-friendly number base is Hexadecimal or Base-16. As you may have already figured out, in this number base we have 16 unique symbols to represent different values. They are the digits 0 – 9 and the letters A – F.

Example: How many symbols/digits exist in Base-8 (Octal)?

  • 8 – The numbers 0 – 7

When working with numbers in different bases we need to be clear about which base we are representing. One way we do this is by using a simple subscript next to the number we are working with. For example, 1002 is in Base-2 or the number 410 in decimal. 10010 is in Base-10 or the number “One Hundred”. 10016 is in Base-16 or the number 25610 in decimal. Each value very different from the others. If no base is specified, we generally assume Base-10 as the default.

Counting in Different Number Bases

Counting in another number base is very similar to counting in our more familiar Base-10. In decimal or Base-10 we can count 0, 1, 2, … 7, 8, 9, and then 10. Notice how in Base-10 there is no unique symbol/digit for the value “10”. Instead, ten is made up of the digits 1 and 0. This is also true for all other bases.

For example, Base-2 doesn’t contain the symbol “2” but rather the idea of “2” is represented by “10” (1 and 0. Not the number 10, or ten).

Another thing to note is how when we reach the last digit in our number system, we reset, and shift/carry. For example, in decimal 9 + 1 = 10. Adding 1 to the last symbol/digit (9) in our number system (Base-10) resets the “One’s” place to 0. We also shift or carry a 1 over to the left in what we call the “Ten’s” place. This gives us 1 – Ten and 0 – Ones, or Ten. If we continue to shift left we get to the “Hundred’s” place, then the “Thousand’s” place and so on.

Every time we shift to the left the value of our number is effectively multiplied by the base we are operating in. In Computer Science, this operation actually has a name. We call it an Arithmetic Shift (to the left). Arithmetic Left Shifts are equivalent to multiplication by the radix or base we are operating in.

Following this logic what happens when we add or count in Base-2 (binary)? Since binary only has the symbols 0 and 1, we will need to reset, shift/carry after “1”. In binary, 1 + 1 = 10 (One Zero. Not to be confused with the number Ten in decimal). As we do in decimal-land, adding 1 to the last symbol/digit (1) in our number system (Base-2) resets the “One’s” place to a 0 and we shift or carry a 1 over to the left which we call the “Two’s” place. Why the “Two’s” place? Well, because we are counting in Base-2. Every shift or carry over to the left is a power of that base. So in binary, we have the 1’s (20), 2’s (21), 4’s (22), 8’s (23) place and so on. Remember that every time we shift to the left we are effectively multiplying by the base or radix which we are operating in.

So far we’ve seen what counting in a base lower than 10 looks like. What does counting in a base greater than 10 look like? Something like Hexadecimal or Base-16?

Let’s start and see where it takes us. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, … What comes after “F”? If counting in hexadecimal is anything like counting in binary or decimal then F + 1 should be similar to 1 + 1 in binary or 9 + 1 in decimal. Indeed it is! Again, adding 1 to the last symbol/digit (F) in our number system (Base-16) resets the “One’s” place to a 0 and we shift or carry a 1 over to the left which we call the “16’s” place.

Converting between Number Bases

We already have some good clues that will help us in converting between number bases. Namely, we now know that whenever we reach the highest single digit/value in a column or place, we reset and shift or carry to the left, which we determined was equivalent to a multiplication by that base. Depending on the base we are operating in, that number column or place will be some power of that base. This little nugget of information will help us convert a number in ANY base to its equivalent value in Base-10. What follows are a few examples.

Base 2:

  • From right to left we have the 1’s column, the 2’s column, the 4’s column, the 8’s column, the 16’s column, etc… Notice how each column is 1 power greater than the column before it. The “X’s” represent the symbol/digit of the number.
  • (x5 * 24) + (x4 * 23) + (x3 * 22) + (x2 * 21) + (x1 * 20)
  • (x5 * 16) + (x4 * 8) + (x3 * 4) + (x2 * 2) + (x1 * 1)
  • For example, 11001 would be expressed:
    • (1 * 24) + (1 * 23) + (0 * 22) + (0 * 21) + (1 * 20)
    • (1 * 16) + (1 * 8) + (0 * 4) + (0 * 2) + (1 * 1)
    • 110012 = 1610 + 810 + 110 = 2510

Base 10:

  • Similarly, in the decimal system from right to left we have the 1’s column, the 10’s column, the 100’s column, the 1000’s column, the 10000’s column, etc… Each column 10 times greater than the column before it.
  • (x5 * 104) + (x4 * 103) + (x3 * 102) + (x2 * 101) + (x1 * 100)
  • (x5 * 10000) + (x4 * 1000) + (x3 * 100) + (x2 * 10) + (x1 * 1)
  • For example, 12705 would be expressed:
    • (1 * 104) + (2 * 103) + (7 * 102) + (0 * 101) + (5 * 100)
    • (1 * 10000) + (2 * 1000) + (7 * 100) + (0 * 10) + (5 * 1)
    • 1270510 = 1000010 + 200010 + 70010 + 010 + 510 = 1270510

Base 16:

  • Following the same formula in Base-16; starting from the right and going to the left, we have the 1’s column, the 16’s column, the 256’s column, the 4096’s column and the 65536’s column and so on … ever increasing 16 times whenever we shift left.
  • (x5 * 164) + (x4 * 163) + (x3 * 162) + (x2 * 161) + (x1 * 160)
  • (x5 * 65536) + (x4 * 4096) + (x3 * 256) + (x2 * 16) + (x1 * 1)
  • For example, E117E would be expressed:
    • (E * 164) + (1 * 163) + (1 * 162) + (7 * 161) + (E * 160)
    • (E * 65536) + (1 * 4096) + (1 * 256) + (7 * 16) + (E * 1)
    • Remember the hexadecimal symbols A – F represent the decimal numbers 10 – 15.
    • (14 * 65536) + (1 * 4096) + (1 * 256) + (7 * 16) + (14 * 1)
    • E117E16 = 91750410 + 409610 + 25610 + 11210 + 1410 = 92198210

We can more generally express this as the following:

Converting a Number from Base-X to Base-10

  • Let’s say we have a number – 123XYZB (Base-B)
  • Generally, we take the symbol/digit and multiply by the base (B) raised to the power of the column or place that symbol/digit is in. The columns/places start from 0 and the rightmost symbol/digit of the number. Finally, we add all of our products together and get our decimal equivalent number.
  • (1 * B5) + (2 * B4) + (3 * B3) + (X * B2) + (Y * B1) + (Z * B0)

Converting a Number from Base-10 to Base-X

What about going the other way around? That is, taking a number we have in Base-10 and converting it to another base? Let’s take the number 35 and convert it into Binary (Base-2), Octal (Base-8) and Hexadecimal (Base-16).

As is true with many things in math, there are multiple ways to approach this task. One common and simple method involves using Modulo Division. Unlike regular division, Modulo Division or Modulus gives us just the remainder of a division operation rather than the quotient and remainder. For example, 10/3 = 3r1 or 3 remainder 1. However, 10%3 = 1. Also expressed as 10 mod 3 = 1. Using this method of Modulo Division we can convert any number from Base-10 to whatever other Base-X we choose. The idea behind this method is somewhat the reverse of what we did when converting a number of Base-X to Base-10. We are going to find how many times our original number can be divided into by our desired Base (X) and use that result as the number we divide into (dividend) in the following step. We also determine what the remainder of that division (Modulus) is while keeping track of our results. We repeat these steps until we reach a dividend of 0 at which point we calculate the Modulus one last time. We then piece together the results of our Modulo Division operations in reverse order (starting from our last result to our first result) to get our converted number.

Example: What is 35 in Binary?

  • Binary is Base-2 so we will be dividing by 2.
  • 35/2 = 17 and 35%2 = 1
  • Repeat until the dividend is 0.
  • 17/2 = 8 and 17%2 = 1
  • 8/2 = 4 and 8%2 = 0
  • 4/2 = 2 and 4%2 = 0
  • 2/2 = 1 and 2%2 = 0
  • 1/2 = 0 and 1%2 = 1
  • In the following step our dividend is 0 so we stop.
  • Putting the results of our Modulus Division operations all together in reverse order we get:
  • 1000112 = 3510

Example: What is 35 in Octal?

  • Octal is Base-8 so we will be dividing by 8.
  • 35/8 = 4 and 35%8 = 3
  • Repeat until the dividend is 0.
  • 4/8 = 0 and 4%8 = 4
  • In the following step our dividend is 0 so we stop.
  • Putting the results of our Modulus Division operations all together in reverse order we get:
  • 438 = 3510

Example: What is 35 in Hexadecimal?

  • Hexadecimal is Base-16 so our divisor will be 16.
  • 35/16 = 2 and 35%16 = 3
  • Repeat until the dividend is 0.
  • 2/16 = 0 and 2%16 = 2
  • In the following step our dividend is 0 so we stop.
  • Putting the results of our Modulus Division operations all together in reverse order we get:
  • 2316 = 3510

Example: What is 672 in Hexadecimal?

  • Hexadecimal is Base-16 so our divisor will be 16.
  • 672/16 = 42 and 672%16 = 0
  • Repeat until the dividend is 0.
  • 42/16 = 2 and 42%16 = 1010 or A16 (Remember that in Base-16 we use the symbols A – F to represent the numbers 10 – 15)
  • 2/16 = 0 and 2%16 = 2
  • In the following step our dividend is 0 so we stop.
  • Putting the results of our Modulus Division operations all together in reverse order we get:
  • 2A016 = 67210

Converting a Number from Base-X to Base-Y

Now that we’re comfortable converting a number to and from Base-10 it will be easy for us to convert a number from any base to any other base. All that is required is for us to convert our original number into Base-10 and then from Base-10 to the desired base.

Example: What is 7358 (Base-8) in Base-5?

  • First we convert 7358 (Base-8) to Base-10:
    • 7358 is expressed:
    • (7 * 82) + (3 * 81) + (5 * 80)
    • (7 * 64) + (3 * 8) + (5 * 1)
    • 7358 = 44810 + 2410 + 510 = 47710
  • Next, we convert our result from step 1 (47710) into our desired base (Base-5).
    • Our desired base is Base-5 so we will be dividing by 5.
    • 477/5 = 95 and 477%5 = 2
    • Repeat until the dividend is 0.
    • 95/5 = 19 and 95%5 = 0
    • 19/5 = 3 and 19%5 = 4
    • 3/5 = 0 and 3%5 = 3
    • In the following step our dividend is 0 so we stop.
    • Putting the results of our Modulus Division operations all together in reverse order we get:
    • 34025 = 47710

Finally, we arrive at our solution:

  • 7358 = 34025

Calculating Number of Factors

technologeo

When referring to the factors of a number, we typically mean the positive factors. How do we calculate the number of factors a specific number has?

  • As usual, we start by finding the prime factorization of the number
  • We then list the exponent of each prime factor and add 1 to each exponent
  • Finally, we multiply each sum together

Example: How many factors does the number 90 have?

  • 90 = 21 * 32 * 51
  • The exponent of each prime factor is 1, 2, and 1. Adding one to each we get (1 + 1), (2 + 1), and (1 + 1)
  • Multiplying the sums together we get (1 + 1) * (2 + 1) * (1 + 1) = (2) * (3) * (2) = 12
  • 90 has 12 positive factors

Example: How many factors does the number 1932 have?

  • 1932 = 22 * 31 * 71 * 231
  • (2 + 1) * (1 + 1) * (1 + 1) * (1 + 1) = (3) * (2) * (2) * (2) = 24
  • 1932 has 24 positive factors

* Example: What is the smallest positive integer that has 10 factors?

  • We can observe that 10 = 2 * 5, meaning that the number in question has just two prime factors in its decomposition – one with the exponent of α = 1, the other of β = 4: N = (p1)(q4). To make N as small as possible, we have to choose the smallest available primes, 2 and 3. The answer then must be N = (31)(24) = 48
  • The smallest positive integer that has 10 factors is the number 48
* Source: https://thepuzzlr.com/quizzes/can-you-find-the-number-of-factors/

Greatest Common Factor (GCF)

technologeo

The greatest common factor of a set of numbers such as a and b is the largest positive integer that divides both a and b. The GCF can be thought of like the inverse of LCM.

GCF(a, b) * LCM(a, b) = a * b

To find the GCF of a set of numbers:

  • List the prime factors of each number
  • Multiply the factors that all numbers have in common
  • If there are no common prime factors, then the GCF is 1.

Example: What is the Greatest Common Factor (GCF) of 42, 56 and 84?

  • 42 = 2 * 3 * 7, 56 = 23 * 7, 84 = 22 * 3 * 7
  • The common prime factors among the set of numbers are: 2 and 7
  • 2 * 7 = 14. GCF(42, 56, 84) = 14.

Least Common Multiple (LCM)

technologeo

The least common multiple of a set of numbers such as a and b is the smallest positive integer that is divisible by both a and b. Least Common Multiple is often referred to as LCM.

Example: What are the common multiples of 3 and 5?

Both 3 and 5 have an infinite number of multiples, therefore they also have an infinite number of common multiples.

The first 5 multiples of 3 are: 3, 6, 9, 12, 15

The first 5 multiples of 5 are: 5, 10, 15, 20, 25

The following are the first 5 common multiples of 3 and 5. In other words, the multiples of each that they have in common: 15, 30, 45, 60, 75

To find the next common multiple we add 15 to the previous multiple in the list. Therefore, we can say that the common multiples of both 3 and 5 can be expressed as 15m, where m is an integer.

So what is the Least Common Multiple? Well, it’s just the smallest common multiple between the set of numbers. In the case of 3 and 5, the LCM is 15.

The method described above for finding the LCM of a set of numbers works but can quickly become very tedious and inefficient.

There is a better way of finding the LCM of any set of numbers.

  • First, we list the prime factors of each number
  • Then we multiply the prime factor that occurs the greatest amount of times in any of the numbers
  • Finally, we check that all numbers evenly divide our result.

Example: What is the Least Common Multiple (LCM) of 8, 105, and 72?

  • 8 = 23, 105 = 3 * 5 * 7, 72 = 23 * 32
  • 2 occurs the most 3 times so we take 23. 3 occurs the most 2 times so we take 32. 5 and 7 occur the most 1 time so we take 5, and 7. All together we end up with 23, 32, 5, and 7. Multiplying these altogether we get 23 * 32 * 5 * 7 = 2520. LCM(8, 105, 72) = 2520
  • 2520/8 = 315, 2520/105 = 24, 2520/72 = 35

Prime Factorization

technologeo

Perhaps one of the most important and fundamental concepts when learning Number Theory is Prime Factorization. Prime numbers are the building blocks of Number Theory because all of the Natural numbers can be expressed as a unique product of prime factors. This is what is called Prime Factorization. Knowing the prime factors of a number also gives us insight into other properties of that number as we shall see when working with Least Common Multiples (LCM) and Greatest Common Factors (GCF) in the following chapters.

A formal definition of Prime Factorization is the decomposition of a composite number into a product of prime numbers. In other words, we can ask ourselves, “which prime numbers can we multiply together to get our original number?”

Example: What is the Prime Factorization of 72?

  • We can start finding the prime factors by dividing our original number (72) by the first prime number (2). 72/2 = 36.
  • We continue dividing by 2 until we no longer can and move on to the next prime (3) if necessary repeating this process until our dividend is a prime number. 36/2 = 18, 18/2 = 9, 9/3 = 3.
  • Putting it all together we see the prime factors of 72 are 2, 2, 2, 3, 3. Another way to express this is: 23 * 32.

Example: What are the prime factors of 31?

  • 31 is prime so it does not have any prime factors other than itself.

Factors, Divisors, and Multiples

technologeo

A factor of an integer n, also known as a divisor of n is an integer m that when multiplied by another integer produces n. This can also be worded that n is a multiple of m. An integer n is (evenly) divisible by another integer m if m is a divisor of n. This means that dividing n by m results in no remainder.

A multiple is the product of any quantity of an integer. For example, 35 is a multiple of 7 because 35 = 7 * 5.

There are many ways one can describe the relationship between factors, divisors and multiples. For example, the following three statements are the same:

  • n/m is an integer
  • m divides n
  • m is a factor of n

Example: What are the factors of 8?

  • 1, 2, 4, 8

Is this all? No. We must remember the negative factors as well.

  • -8, -4, -2, -1

For a total of 8 factors:

  • -8, -4, -2, -1, 1, 2, 4, 8

Knowing that we have both negative and positive factors, it is important to remember that the minimum number of factors a number can have is 2!

Example: What are the factors of 1?

  • -1, 1

Example: How many multiples does the number 7 have?

  • An infinite amount

Example: What are the first 5 multiples of 9?

  • 9, 18, 27, 36, 45

Number Classifications

technologeo

Numbers can be categorized into different sets or groups. Some sets of numbers are subsets of others.

By HB – Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=34938003

Natural Numbers

Natural numbers are your common counting numbers. These are all the positive numbers from 1 and on.

{1, 2, 3, 4, 5, … n}

Among the Natural numbers are the Prime and Composite numbers.

  • Prime Numbers: A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A prime number has exactly 2 factors.
  • Composite Numbers: A composite number is any number that is not a prime number. Composite numbers contain more than 2 positive factors.

Whole Numbers

Whole numbers are all of the Natural numbers and Zero (0).

{0, 1, 2, 3, 4, 5, … n}

Integer Numbers

Integers are the positive and negative Natural numbers and Zero (0).

{-n, … -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, … n}

Rational Numbers

Rational numbers are all numbers that can be expressed as the ratio of two Integers.

Examples of Rationals are:

{-5/3, 3/7, 0, 2}

Irrational Numbers

Irrational numbers on the other hand, cannot be expressed as the ratio of two Integers.

Examples of Irrationals are:

{pi, e, phi, sqrt(2)}

Real Numbers

Real numbers are all numbers that can be found on a number line, positive, negative or Zero.

Examples of Real numbers:

{-3.12341, -3.10, -1, 0, 0.235, sqrt(2), 1.95832, 2/3, 3}

Imaginary Numbers

Imaginary numbers are equal the product of a real number and the square root of −1 or i.

Examples of Imaginary numbers:

{-2i, 0, sqrt(-1)}

Complex Numbers

Complex numbers include all real numbers, imaginary numbers, and sums and differences of real and imaginary numbers.

Examples of Complex numbers:

{-1 + 3i, 0, 1}

Breadth-First Search (BFS)

technologeo

Programming Language:

Javascript (JS)

Solution:

/* A Queue object for queue-like functionality over JavaScript arrays. */
var Queue = function() {
    this.items = [];
};
Queue.prototype.enqueue = function(obj) {
    this.items.push(obj);
};
Queue.prototype.dequeue = function() {
    return this.items.shift();
};
Queue.prototype.isEmpty = function() {
    return this.items.length === 0;
};

/*
 * Performs a breadth-first search on a graph
 * @param {array} graph - Graph, represented as adjacency lists.
 * @param {number} source - The index of the source vertex.
 * @returns {array} Array of objects describing each vertex, like
 *     [{distance: _, predecessor: _ }]
 */
var doBFS = function(graph, source) {
    var bfsInfo = [];

    for (var i = 0; i < graph.length; i++) {
	    bfsInfo[i] = {
	        distance: null,
	        predecessor: null };
    }

    bfsInfo[source].distance = 0;

    var queue = new Queue();
    queue.enqueue(source);

    // Traverse the graph
    
    // As long as the queue is not empty:
    while (!queue.isEmpty()) {
    //  Repeatedly dequeue a vertex u from the queue.
        var currentVertex = queue.dequeue();
    //  For each neighbor v of u that has not been visited:
    //     Set distance to 1 greater than u's distance
    //     Set predecessor to u
    //     Enqueue v
    //     v = currentNeighbor
    //     u = currentVertex
        for (var i = 0; i < graph[currentVertex].length; i++) {
            var currentNeighbor = graph[currentVertex][i];
            
            if (bfsInfo[currentNeighbor].distance === null) {
                bfsInfo[currentNeighbor].distance = bfsInfo[currentVertex].distance + 1;
                bfsInfo[currentNeighbor].predecessor = currentVertex;
                queue.enqueue(currentNeighbor);
            }
        }
    }    
    return bfsInfo;
};


var adjList = [
    [1],
    [0, 4, 5],
    [3, 4, 5],
    [2, 6],
    [1, 2],
    [1, 2, 6],
    [3, 5],
    []
    ];
var bfsInfo = doBFS(adjList, 3);
for (var i = 0; i < adjList.length; i++) {
    println("vertex " + i + ": distance = " + bfsInfo[i].distance + ", predecessor = " + bfsInfo[i].predecessor);
}


Program.assertEqual(bfsInfo[0], {distance: 4, predecessor: 1});
Program.assertEqual(bfsInfo[1], {distance: 3, predecessor: 4});
Program.assertEqual(bfsInfo[2], {distance: 1, predecessor: 3});
Program.assertEqual(bfsInfo[3], {distance: 0, predecessor: null});
Program.assertEqual(bfsInfo[4], {distance: 2, predecessor: 2});
Program.assertEqual(bfsInfo[5], {distance: 2, predecessor: 2});
Program.assertEqual(bfsInfo[6], {distance: 1, predecessor: 3});
Program.assertEqual(bfsInfo[7], {distance: null, predecessor: null});