DPR302: Asymptotes and Algorithms What You've Forgotten Since ...

DPR302: Asymptotes and Algorithms What You've Forgotten Since ...

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

Recently Viewed Presentations

  • Chromosomes and Genes - Mr. Shanks&#x27; Class

    Chromosomes and Genes - Mr. Shanks' Class

    Chromosomes and Genes Within each human somatic cell there are 46 chromosomes (23 pairs) Karyotype of metaphase chromosomes Each chromosome is made of DNA Long strands of chromatin are packed tightly together to make chromosomes A segment of DNA is...
  • How the rational use of oxygen can improve

    How the rational use of oxygen can improve

    Two faces of oxygen therapy Oxygen use in England >85,000 people receive oxygen at home It costs C £120, 000,000 (2011) (30% up on 2006, 10% total cost COPD) Historically service/cost placed in community Patients often do not understand why...
  • Le Passé-Composé with &quot;être&quot;

    Le Passé-Composé with "être"

    Here are some reflexive verbs you are familiar with: se lever, se laver, s'habiller, se coucher, se promener, se baignerands'amuser. Practice! Click. Verbs of motion: That's a bit more tricky! Understand what MOTION is (as opposed to movement). Use Mnemonic...
  • Reference Sources - University of Western Ontario

    Reference Sources - University of Western Ontario

    FIMS, UWO Other titles: Times New Roman Default Design Reference Sources Background Information PowerPoint Presentation PowerPoint Presentation From the Oxford English Dictionary Locating Facts or Specific Details Almanac PowerPoint Presentation Locating Other Sources of Information PowerPoint ...
  • The Molecular Basis of Heredity.PPT

    The Molecular Basis of Heredity.PPT

    Phosphate group attached to 5' carbon Nucleotides are linked by phosphodiester bonds to form polynucleotides. Phosphodiester bond Covalent bond between the phosphate group (attached to 5' carbon) of one nucleotide and the 3' carbon of the sugar of another nucleotide....
  • The MiTek Posi-Stud The MiTek Posi-Stud  Thermal Performance

    The MiTek Posi-Stud The MiTek Posi-Stud Thermal Performance

    The MiTek Posi X-Rafter. The Posi-Joist cassette floor provides the opportunity to guarantee a . totally accurate platform . for the spandrel panels. The MiTek Posi X-Rafter. The MiTek Posi X-Rafter. The . Posi X-Rafter system uses flat top spandrel...
  • Impact of sodium butyrate supplementation on global gene ...

    Impact of sodium butyrate supplementation on global gene ...

    The purpose of the scientific communication seminar is to ensure that participants in the 2007-2008 TQB and TQC Programs can produce quality posters of their unit plans, which is part of the final assignment for BIOL 601D and CHEM 601E.
  • The Four Natural Elements of Life Earth, Air, Fire, Water

    The Four Natural Elements of Life Earth, Air, Fire, Water

    The Four Natural Elements of Life Earth, Air, Fire, Water By: Amanda Burleson Understanding the Importance of the Four Elements of Life Ancient peoples had a deep connection with fire, earth, air, and water. "It is often said that all...