DPR302 Asymptotes and Algorithms What Youve Forgotten Since University By Gary Short Developer Evangelist

Developer Express Agenda Introduction What is an Algorithm? Why Optimization is Important Optimisation is Childs Play

Why do we Use Mathematics? One Tactic for Optimizing an Algorithm But .Net Saves me from all that, Right? Questions. Introduction Gary Short

Developer Evangelist DevExpress Microsoft MVP in C# [email protected] @garyshort What is an Algorithm?

a finite list of well defined steps to complete a task or calculation. There are simple ones There are complex ones

Prove no three positive integers a, b, and c can satisfy the equation an + bn = cn for any integer value of n greater than two Why is optimization important? http://www.flickr.com/photos/mushjazzlexima-leakpaalex/2237327967/

Optimization is Childs Play Take This Algorithm Stop current task Wash hands Sit at table

Foreach item of food in MainCourse Consume food Wait for dessert Consume dessert Wait for meal completion Foreach dish in dishes

Clear dish from table Foreach dish in dishes Wash dish Return to previous task

Optimized by my 4 Year Old Daughter to Pause current game Set velocity = MAX_INT Move to table TakeSliceBread(2) Foreach item of food in MainCourse Place item on BreadSlice(1)

Place BreadSlice(2) on top Leave table Resume current game And its not a skill we lose in adulthood

Morning Algorithm Rise Shower Boil kettle Make tea Toast bread Spread butter on toast

Consume breakfast Brush teeth Commute to work Optimized for Smallville Rise Rush downstairs

Put kettle on to boil Put toast in toaster Rush back upstairs Shower Rush downstairs Make tea and spread toast Watch Smallville

Consume tea and toast The Only Thing Hard About This is 2

= =1

= ()

= 2 4 = 2

2 3 =1+ + + + , < < 1 ! 2! 3 !

) 2+ 2 = 2 (

= ) 0 = +

2 ( + ) = =0

+ sin

The language we chose to use to describe it 2+ 2 = 2 2

( ( )=0+ cos 2+ 2 = 2

() 2

= 2

= + 2 2

So Why do we use Math? http://www.flickr.com/photos/truelifeimages/2102930162/ http://www.flickr.com/photos/[email protected]/4783131736/

Our Model Has Single processor RAM Understands arithmetical instructions Add Subtract Pop

Push All instructions executed sequentially All instructions take constant time to complete. demo

Running Time is Then Sum running times for each statement Product of the cost and the time So T(n) = c1n + c2(n-1) + c3(n-1) + c4(sum of tj for 1 <= j <= n) + c5(sum of tj -1 for 1 <= j <= n) + c6(sum of tj -1 for 1 <= j <= n) + c7(n-1).

Best Case Running time When the collection is already sorted T(n) = c1n + c2(n-1) + c3(n-1) + c4(n-1) + c7(n-1-) T(n) = (c1+c2+c3+c4+c7)n (c2+c3+c4+c7) Which is a function in the form an + b Thus T(n) is a linear function of n.

Lets Quickly Prove That Worst Case Running Time Reverse sorted order T(n) = c1n + c2(n-1) + c3(n-1) + c4(n(n+1)/2 -1) + c5(n(n-1)/2) + c6(n(n-1)/2) + c7(n-1)

T(n) = (c4/2 + c5/2 + c6/2)n^2 + (c1 + c2 + c3 + c4/2 c5/2 c6/2 + c7)n (c2 + c3 + c4 + c7) Which is a function in the form an^2 + bn + c Thus T(n) is a quadratic function of n. Again Lets Quickly Prove That

So Now We Can Prove Speed an + b Is faster than an^2 + bn + c Can we Make The Notation More Readable?

Asymptotic Notation Big O Notation For the functions an + b an^2 + bn + c If n is sufficiently large

Then the largest term of n dominates the function So T(n) = an + b = O(n) T(n) = an^2 + bn + c + O(n^2). So Now we Can Say

Insertion Sort is Best Case O(n) Worst Case O(n^2)

But we only care about the worst case Lets Optimize Our Search Algorithm Lets do What we Did When we Were Kids Divide the problem up into smaller parts and conquer each

of those smaller parts before combining the solutions. Demo Okay, so How Fast is That Algorithm? Merge Sort in 3 Easy Parts

Divide Computes the middle of the array Constant time D(n) = O(1) Conquer Recursively solve two n/2 sized sub problems

Each contribute 2T(n/2) Combine Combine step is linear C(n) = O(n) So worst case

2T(n/2) + O(n) Use The Master Method to Solve This Recursion What is The Master Method? Recipe for solving recurrences in the form T(n) = aT(n/b) + f(n)

Where The constants a >= 1 and b > 1 And f(n) is asymptotically positive Our function 2T(n/2) + O(n) is in this form How Does it Work?

Recall it works with function of the form aT(n/b) + f(n) We compare f(n) with n log ba The larger of the two determines the solution If n log ba is larger then T(n) = O(nlogba)

If f(n) is larger then T(n) = O(f(n)) If they are equal then we multiply by log factor T(n) = O(f(n) log n)

So in Our Example Were in case three Worst case Merge Sort is O(n log n) Which is much better than Insertion Sort O(n^2)

But .net Handles all this for me List - Add List - Growing

List - EnsureCapacity List - Capacity List - AddRange List - AddRange

List - InsertRange So What are the Performance Implications? Data Provider

Tester Results Performance: Add Versus AddRange 30000 Number of Ticks

25000 20000 Add AddRange 15000

10000 5000 0 10 100

1000 10000 Number of Elements Added 100000

1000000 What Weve Learned Performance is important Optimization comes naturally to us Divide and conquer

Running time is the sum of product of cost and execution Maths syntax makes this all seem scary Asymptotic notation simplifies language This stuff matters, even in the age of .net. Questions? [email protected]

@garyshort DPR Track Resources http://www.microsoft.com/visualstudio http://www.microsoft.com/visualstudio/en-us/lightswitch http://www.microsoft.com/expression/ http://blogs.msdn.com/b/somasegar/

http://blogs.msdn.com/b/bharry/ http://www.microsoft.com/sqlserver/en/us/default.aspx http://www.facebook.com/visualstudio Resources Connect. Share. Discuss.

http://northamerica.msteched.com Sessions On-Demand & Community Learnin g Microsoft Certification & Training Resources

www.microsoft.com/teched www.microsoft.com/learning Resources for IT Professionals

Resources for Developers http://microsoft.com/technet http://microsoft.com/msdn Complete an

evaluation on CommNet and enter to win! Scan the Tag to evaluate this session now

on myTechEd Mobile Click icon to add picture