Design and Analysis of Algorithm- Practical Example

Most common used algorithms are sorting algorithm.
We can analyze space and time complexity. By space complexity we mean ammont of memory consumed by algorithm and Time Complexity tells time taken by algorithm to accomplish task. From Complexity analysis using BigO Notation. We know Like for
Sorting Algorithm             Complexity in BigO notation
Bubble Sort                          n^2
Quick Sort                            nlogn
Merge Sort                           nlogn
————————————————————————-
if we want to write simple logic of bubble sort
for (i=0; i<totalSizeOfArray;i++)
{
for (j=i+1; j<totalSizeOfArray-1;j++)
{
//Compare array to be sorted and Swap numbers if found lesser number
if ( a[i] > a[j]) )
{
temp=a[i];
a[i]=a[j];
a[j]=a[i];
}
}
}
you can easily Understand why complexity is n^2. There are two loops.
First take each number compare with other other ‘n’ numbers. (n times to be done) Done with first number then take second number and so on upto n.
Then Each of ‘n’ numbers this is repeated (nXn= n^2).
This is one of least efficient sorting algorithm.
————————————————————————
Merge Sort complexity (n X log(n))
breaks whole numbers into two lists and further smaller lists. then sorted lists are joined with log(n) complexity time/effort to have sorted list.
Example/scenario:
Suppose a on-line lottery programme running first sorting from province level results then moving to state level results and finally national winner is selected.
suppose 1 country has 25 states each state has 10 province. and approx each province sold 1000 tickets.
So while running sorting algorithm then randomly pick ticket.
How many iterations: 25 X 10 X 1000 is the N
bubble sort means (2,50,000)^2.
Using Merge Sort here within province if we have sorted list. which can joined quickly to other sorted province list with log(n) complexity lots of comparisons are reduced like
province 1: 2, 5, 7
province 2: 8,9
Here we compare rightmost digit of province 1 with leftmost province 2
We get if (7 < 8) right just merge list = 2,5,7,8,9.
so 5X5=25 comparisons of bubble sort are reduced by just using Merge sort.
off-course there will be scenario where list have to sorted within but comlexity remain
n log(n).
Now We we are running this lottery winner finder programme what happens in bubble sort huge load will (2,50,000)^2 comes to server (in actual situation it much more).
while merge sort we may be merging minimum 250 lists to nlogn ccomparisons. saving huge server resources of RAM and CPU cycles.
Thus Server Capacity requirements can be lesser hence less cost and faster results.
second better utilisation of capacity.
There are many sorting algorithm which are developed to take advantage of this fact over the years. Sorting is fundamental to any system.
If we need to find a file within system if is faster if list is sorted. Most algorithm first sort then search look OS tries to find any file within also optimizes its search similar way.

MAP REDUCE ALGORITHM: commonly used in Cloud computing /Big data has two phase Map Phase and Reduce Phase. Systems like Hadoop are built over map reduce algorithm.
Map Phase maps the task to ‘n’ small task and reduce help in combining the result back to a single result set like aggregation.
MapReduce
Diagram source: http://kickstarthadoop.blogspot.ie/2011/04/word-count-hadoop-map-reduce-example.html
READ:
1. https://sandyclassic.wordpress.com/2011/10/26/big-data-and-data-integration/
2. https://sandyclassic.wordpress.com/2013/10/01/internet-of-things/
3. https://sandyclassic.wordpress.com/2013/09/22/approach-to-best-collaboration-management-system/
4.https://sandyclassic.wordpress.com/2013/06/18/bigdatacloud-business-intelligence-and-analytics/

Generalize problem solving through design pattern

When we start solving a problem: first step to to get logic so we can program it.
Like is some where repetition which happens so we can put in loop or we can repeat data structures like stack and array.
Data Structure to generalize 
Then we take storage about which data structure to Use let us suppose we are building a program whose maximum capacity to store a number is 10^12 but we want to add
10^12 +  10 ^12 how to achieve this when max capacity is 10^12?
Then we have to use storage through data structure like Stack…
We can create 2 stacks of each number with digit arranged in LIFO.
How will we add: take simple example : we take two 3 digit numbers
123 + 456
Stack 1             Stack 2
1              |        4                                                                                                                                    2              |        5                                                                                                                                     3              |        6
————————- We can not add these no by poping() stack pointer at top
and multiplying with its position in Stack 1: Like 123= 3 X 1+2 X 10+1 X 100.
and                                                        Stack2:         456=6 X 1+ 5 X10 +6 X 100.
=——————————————————————————                      So We pop  out 1 from (Stack 1) and 6 from (Stack 2) and Add take any carry to next element of stack. We can use array we can create linked list of Equation or we can use Stack (since number are added in LIFO from left to right) Stack are best match.
As we can see How the above is added:
pop unit position from stack 1 + pop unit position from stack 2 = store in stack 3 unit position
Stack 1             Stack 2        =  StackSum
3              |        6              =      9                                                                                                            2              |        5               =      7                                                                                                        1              |        4               =     5                                                                                                            Now Stacksum will contain Numbers in sequence push(9), push(7),push(5).

But Stack pops out in LIFO so Last inserted pop(9) X 1 + pop(7) X 10 + pop(5) X 100=579.
This example used only 3 digit but actually limits of System We can Enhance using data Structure like here..
——————————————————————————————
There can be multiple practical example for menus liked through Linked List or 2 Phase commit is Oracle Using Queue of multiple user request at multiple server.  We can fit in structure based on requirement. (Lowest level of generalisation)
—————————————————————————————

More higher level (top level) from 100 feet above earth we are now coming to 1000 feet We move towards Algorithms to decide which we have used one above.. but
We analyse 2 complexity .. time complexity and space complexity suing popular BigO notation to analyse performance of Algorithm.  This performance evaluation is also generalized using BigO and using popular Algorithms..
Like we want to see segmentation of market but we do not know what are different possibility of Buckets or segments.
Then We use like popular Market Basket Algorithm….
————————————————————————————–

10,000 feet level generalisation: Design Pattern ..

In GoF (Gang of four pattern) we have There are 3 category of design pattern Behavioural, Structural and creational
more read:http://en.wikipedia.org/wiki/Design_Patterns                                                   more general read:http://en.wikipedia.org/wiki/Software_design_pattern

Example:
So We see every time we create a web site we need user login, we need to maintain session hence session level objects,
So in Design pattern We search What pattern matches this design requirements Like (Visitor pattern) fits in here.
Integration Design pattern———————————————————-
Or In general during Integration we use Bridge pattern or Adapter pattern which is used in most integration tools like Webmethods (www.webmethods.com) and TIBCO (www.tibco.com)
We have many Integration design patterns only for integration….
http://en.wikipedia.org/wiki/Enterprise_Integration_Patterns
Nowadays We have more course grain integration using Web services.
With Everything Exposed as web service is interoperable across programming languages like Java and .net and with data in XML we have data portability.
This strategy is used in like enterprise service bus or in design of many BI / BPM tools read:
https://sandyclassic.wordpress.com/2013/10/05/enterprise-service-bus-esb-bpm-orchestration-and-process-re-engineering/
————————————————————————————–
20,000 feet level generalisation: Enterprise Design pattern
Depending on requirement we will mix and match.
There are various design pattern which exist today there are thousands of algorithm which can be chosen inside each mixture of pattern chosen
Let suppose we want to mix data set of two server session user information pattern in used in Observer pattern + Merge Sort (list) and create new list.. and sink in unified database.

Read this Discussion: http://www.sitepoint.com/understanding-the-observer-pattern/

There are at Tool or development level Frameworks which exist to create already known programming structure Like Spring Framework uses Aspect Oriented Programing,
Declarative programming style is generalized with annotation @web service making a POJO exposed as Web service… Then we need to think we want restful web serices

Analysis Of Online Education My senario

Last 8 months:
University Exam :
term end 10 cleared 10
Mid term : 10 cleared 10.
Other University Exam: 12X15= 180 Exams
Cleared = 120/180.
Other University course cleared: 12.
Exam per month: (180+20)= 200/8= 25 Exams per month.cleared 15 per mnth
25/4= 6.25 Exam per week: cleared 4 per week.
+ 180 plus courses video lecture (120 exam cleared).
hours spent on Online lecture: (6.25 X 3 hrs)=20 hours per week.
hours spent on live lecture: 10/20 hrs per week.

Time spent on exam: online per week: 4 X 2= 8 hrs.
Time spent offline University Exam : 12 X 3= 36 hours /8 month = 4.5 hrs/mnth
= 1 hr per wk
Total time spent on Education
Online Lecture+ Exam: 20+8= 28 hrs / week
Offline Lecture+ Exam: 15+1= 16 hrs /week
Revision 20% time = 9 hrs / week
——————————————————————————————-
Total : 53 hrs/week.
 238 hrs/ month
      1908 hrs/ 8 month.

Mathematical Model Thinking-MichiganScore



Skill data point generated: 180 X 20= 3,600 data points.

Elaborate more in next article how to Analyze more deeply this about categorization using Market basket and profiling:
https://sandyclassic.wordpress.com/2013/02/17/countries-adopting-e-learning-will-win-next-war-of-education-and-competitiveness/
——————————————————————————

Extras: personal Schedule this year:

  1. 53 hrs per week Online+ offline education
  2. 10 hrs/week  per week travelling, other city and college
  3. 10 hrs/week housework cooking+washing etc..
  4. 10 hrs/week traveling
  5. 10 hrs/week Certification exam travel to dublin, CISA, CFA, CISM, CISSP, PMP
  6. 15 hrs/week Wasted hours walking around city, at house,facebook etc…

——————————————————————————————-
95 hrs/week : or 95/7 =13 hrs per day (including weekend)
95/5 =19 hrs per day (excluding Weekend)