Building Blocks ,Analysis of Algorithms & Rates of Growth

I thought it would be prudent to split this tutorial into 2 parts, in order to avoid bombarding the reading with too much information.

The most important accept of analyzing algorithms is to figure which features in the algorithm ultimately define its efficiency, therefore ignoring the minute features. This is the only way we can describe the performance of algorithms across different platform & implementations.  

Not all computers have the same specification or architecture ; some computers are PC’s others are Apple Macintosh, some are 32bit and other are 64bit, and we go on forever providing differences but you get the picture…

Will begin with introducing some building blocks, and finally in the 2^nd part of this tutorial I will present the reader with tools (notations) that will help describe an algorithm regardless of the technologies used.

Let’s look at a simple while loop statement and describe it mathematically:

 

Figure 1, simple while loop that prints 99, “Whats up” statements
Ok, here is our complexity analysis of Figure 1, step by step:

1)      There is a variable declaration is int counter therefore, 1 constant operation

2)      “int counte”r is initialized to 0, 1 constant operation

3)      A logical operation is being performed 100 times, “while (counter<100)” , 100 operations

4)      System.out.println(“Whats up”), is printed 99 times, 99 operations

5)      “Counter” increase Counter by 1, 100 operations

6)       “Counter” is assigned new value or iterated, 100 operations

More or less according the steps above the code in figure 1 has complexity:

1 constant operation + 1 constant operation + 100 operations + 99 operations + 100 operations + 100 operations = 401 operations

Now if we thought of the expression “while (counter<100)” as “while (counter<n)”, in order to make a more general case, then:

1 constant operation + 1 constant operation + n operations + (n-1) operations + n operations + n operations = 3n+(n-1)+2  operations

You see the constants stay the same, and the while loop actually defines this algorithm

Therefore the above algorithms functions is f(n)=3n+(n-1)+2, this is a linear function

We are going to further simplify by using the following simple rules (Dasgupta, , and et al )):

1)      Multiplicative constants can be omitted,

Example 50n² simplifies to n²

2)      n^a dominates n^b if a>b

Example n³ dominates n², so n³ + n² + n ,simplifies to n³

3)      Any exponential dominates any polynomial

Example 3ⁿ dominates n⁵

Example 2ⁿ dominates 5n+100

4)      Any polynomial dominates any logarithm

Example n dominates  (log n)³

So if we applied rule #1 “Multiplicative constants can be omitted ” our analysis of Figure #1 , the function f(n)=3n+(n+1)+2, would simplify to f(n)=n.  This means the code in Figure #1 , behaves linearly.

Questions & Answers

Look at the following functions, what is the dominating feature or term in each function
(Hint: use the rules defined above)

1)      f(x)=x²+4x+30  

Answer = X²       , Using rules 1 & 2

2)      f(x)= x log x + 100x

Answer = X         ,Using rule 4

3)      f(x) = x⁵+x³+ log x + 30x

Answer = x⁵        ,Using rule 2 & 3

4)      f(x) = x²/30x      

Answer = X²           ,Using rule 3

5)      f(x) = x^3/2+x^1/3+x

Answer = x^3/2,    ,Using rule 3

Now 2 more examples and part 1 is finished.

 

Figure 2, For loop that iterates 10 times, and prints i’s value 10 times

Now that we know a “While loops” number of operations can be described as linear, we can apply that to any loop such as a “For” loop. Figure #2  is f(n)=n , or linear number if operations.

Figure 3, Inner loop is nested in outer loop , printing k’s value 10 times per each i’s iteration, therefore 100 print statements.

Nesting loops is just like multiplying the loops operations ,therefore one loop nested in another loop, performs n*n or n² operations, of course ignoring the minute constants.

Now let’s look at rates of growth before ending Part 1.

Rates of growth in order

Log₂ n < n < n log₂ n < n² < n³ < 2ⁿ

^{The above chained expressions summarize from the least to greatest, the mathematical features that most algorithms exhibit in terms of the runtime and input "n".}

^{Below is the graphical representation of the above expressions.}

(http://blog.philenotfound.com/2011/12/brief-intro-to-algorithmic-time.html)

By now we have learned very simple yet powerful simplification rules, for analyzing an algorithm’s time complexity, but in order to be more precise we need some formal notations

References

1.       2000 Solved Problems In Discrete Mathematics. 1st. New York: McGraw-Hill, 1992. 101-110. Print.

2.       Dasgupta, Sanjoy, First , et al. Algorithms. 1. Crawfordsville, IN: McGraw-Hill, 2008. Print.

3.    http://blog.philenotfound.com/2011/12/brief-intro-to-algorithmic-time.html

Basics: Factorial, Fibonacci, Algorithm, and Recursion

Basics: Factorial, Fibonacci, Algorithm, and Recursion

Our 1^st tutorial will focus on introductory mathematical functions in computer science & implementations.

J So let’s begin learning and don’t look back…

I’m sure everyone has heard of the factorial function by now which is denoted by,  n!

Definition # 1:

n! read “n factorial ,which in means “The product of the positive integers from 1 to N, inclusive…”  

("2000 Solved Problems In Discrete Mathematics" 101-110).

Side note: I copied this nice mathematical representation from Wikipedia. If I can’t find a nice graphical representation online than I will write in myself.

Examples & Questions:

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

10! = 10 * 9* 8* ….. * 1 = 3,628,800

The above definition states that for n=0 , the factorial function will return 1.

Therefore 0! =1.

And for n > 0 , then n multiplied by (n-1), recursively.

We will describe recursion soon in detail, it’s a very simple concept.

Definition # 2

Recursion is a function that calls or refers to itself.

Definition #3

Algorithm is a procedure for solving a mathematical problem (www.merriam-webster.com).

The word Algorithm is Latin name for Persian Arab mathematician Al-Khuwarizmi, who lived in ancient Persia, precisely modern day Iraq, he is also the founding father of Algebra. Algebra is also another Arabic word.

(http://www.encyclopedia.com/doc/1G2-2830902300.html).

Applications

Common use of factorials are in combinatorial analysis , such as combinations, permutations, binomial probability, etc.

Implementations in Java

The above implementation of the factorial function is based on the recursive definition, it is correct however naive, recursive functions tend to inefficient because they require previous recursive steps to be kept in memory and recalculated.  

The above implementation is an attempt at a more efficient “Algorithm”,however it is still recursive in nature because its needs to keep in “current memory” the previous step in order to compute current step.

This implementation is actually more efficient than previous recursive implementations. This time the previous factorial steps (j-1) are stored in array, and the current factorial is calculated by just accessing the results [j] = results[j-1] * j.

Now let’s go ahead and formally give definition for recursion.

Formal Definition of Recursion

A function is said to be recursive

1)      If there are certain base values, for which the function does not refer to itself.

2)      Every time the function refers to itself, the argument of the function must be closer to base value.

("2000 Solved Problems In Discrete Mathematics" 101-110).

You can easily see that the factorial function in definition # 1 , conforms to the formal definition above.

Now, run any of the implementations above for n!=5,n!=10,n!=50, you can see that factorial functions grows very fast , exponentially.

Now let’s look at another popular function, the Fibonnaci Sequence

0,1,1,2,3,5,8,13,21,34,55,89,…

Definition #4 , Fibonnaci Sequence

If n =0  or n =1, then F_n = n.

If  n> 1, then F_n = F_n-2 + F_n-1

("2000 Solved Problems In Discrete Mathematics" 101-110).

Applications

Fibonacci sequence is witnessed in the natural world, such as braches of a tree and petals of some flowers, it used to model some biological growth.

Examples & Questions:

1)      What is 10^th number in the Fibonacci sequence ?  fib(10) = 34

2)      What is the 20^th Fibonacci sequence , or fib(20)? Well don’t tell you are going add 20 numbers together by hand, let’s solve this by implementing the Fibonacci sequences definition.

Solution & Implementation in Java

The above Java code is recursive method that computes the Fibonacci sequence.

The above code is the loop that controls term we want the computation to terminate. The variable “n” below determines what Fibonacci term you want calculated.

Fibonacci 20, is computed as 6765 by above method called fib().

3)      What is the 200^th Fibonacci sequence?  Plug in 200 in the implementation from Question 2 and see what happens? It looks like recursive implementation was “Algorithmically inefficient”, so let’s re-implement Fibonacci using iterative approach.

Solution & Implementation in Java

J I’ll bet you any amount, that with above implementation you will not be able to calculate even Fibonacci 50.

So what’s happening? Isn’t the Java code the correct implementation of the Fibonacci definition? YES, but it’s “not an efficient implementation”, many mathematical formulas although correct, maybe inefficient if implemented directly based on their definition alone.

This is where the field of Algorithm Analysis & Computer Science becomes paramount, by providing alternative Algorithms/formulas that can be used in compute real world problems.

I have mentioned the word “efficient” several times, however so far I have not defined the “efficiency” formally, we will do so shortly.

For now just think of inefficient Algorithms, as functions that don’t have enough power to return desired answers in reasonable amounts of time.

A more efficient Implementation Fibonacci implementation

Fibonacci 200 is returned a this huge number 4,845,216,997,073,187,469 in under 1 second!!!.

J Can we do even better?  YES, we will visit this problem later when, we have built more mathematical & computational muscle.

Side note: Don’t dismiss recursion as inefficient technique; recursion is a powerful mathematical tool; many problems are solved recursively.

So far we learned about some functions, learned al little about recursion, and implemented our Algorithms.

However, to proceed we need to provide more formal definitions “efficiency”, and mathematical techniques to compare Algorithms.

Our next tutorial will be about, “Rate of growth…”.

 Further self-practice

1)      Implement a recursive method/function that doubles its input k, n times

2)      Implement a method/function that graphically prints out Khawrazmi’s Triangle (a.ka. Pascal’s Triangle)

3)      Implement Ackermann function recursively

References

1.       2000 Solved Problems In Discrete Mathematics. 1st. New York: McGraw-Hill, 1992. 101-110. Print.

2.       A Primer on Recursion. http://amitksaha.wordpress.com.

3.       Cormen, Thomas, et al. Introduction To Algorithms. 2nd. MIT press, 2001.

Computer Science: Algorithms & Data Science Blog

Dear All,

This blog is meant to be friendly place to provide tutorials on popular algorithms in Computer Science.  I have learned many of these algorithms and methods of analysis by either attending courses or by implementing them as professional software developer.

Algorithms, data structures, and computation are very important for any person interested in developing their knowledge in Computer Science, or any field that requires efficient modeling of real world situations.

My goal is to describe each problem in as many ways as possible, since individuals learn differently.  

All solutions will be referenced in order to provide extra resources, to give credit to original authors, build the credibility of this blog.

 I also highly encourage different solutions, corrections, suggestions on future topics.

Regards,

Aryan Naim

Topics & Scope:

1)      Common algorithms encountered in Computer Science, Computation, Data Mining

2)      Analysis of algorithms & algorithmic complexity via

·         Formal mathematical notation

·         Visual analysis via graphs & 2-D simulation

3)      Applications in real world situations

4)      Implementations in Java or popular languages such as Python or C/C++

Prerequisites

I’m going to keep things as simple as possible even when topics get more advanced, without getting hate mail from mathematicians and computer scientists, however you need to have a good/solid background in programming, that’s it.