Algorithms and Algorithm Analysis

Algorithms and Algorithm Analysis

Algorithms and Algorithm Analysis The fun stuff Algorithms What is an algorithm? A finite set of steps that specify a sequence of operations to be carried out in order to solve a specific problem. Properties of Algorithms 1.

2. 3. 4. 5. 6. Finiteness Absence of Ambiguity Definition of Sequence Feasibility Input Output

What is Programming? Phases of Programming 1. 2. 3. 4. Design Implementation Testing Repeating

Algorithm vs. Programs A computer program is one concrete implementation of an algorithm using a particular computer language The design phase should produce an algorithm The implementation phase should produce a program The design phase is typically much longer than the programming phase

Algorithm Performance It would be great if you could code up an algorithm and then run it with a bunch of input. Take a look at the clock and decide how well it ran There are many problems with this approach and it suffices to say that this is bad A better way

What is often done is to approximate or estimate the performance of an algorithm Estimation is an important skill to learn and to use Question: How many hotdogs tall is the Empire State Building? Example Question: How many hotdogs tall is the Empire State

Building? Answer: The ESB is 1250 feet tall. Assuming that a hotdog is 6 inches from end to end, you would need, 1250 * 2 = 2500 hotdogs. Complexity Analysis An objective way to evaluate the cost of an

algorithm or code section. The cost is computed in terms of space or time, usually The goal is to have a meaningful way to compare algorithms based on a common measure. Complexity analysis has two phases, Algorithm analysis Complexity analysis Algorithm Analysis Algorithm analysis requires a set of rules to

determine how operations are to be counted. There is no generally accepted set of rules for algorithm analysis. In some cases, an exact count of operations is desired; in other cases, a general approximation is sufficient. The rules presented that follow are typical of those intended to produce an exact count of operations. Rules

1.We assume an arbitrary time unit. 2.Execution of one of the following operations takes time 1: 1. assignment operation 2. single I/O operations 3. single Boolean operations, numeric comparisons 4. single arithmetic operations 5. function return 6. array index operations, pointer dereferences More Rules 3. Running time of a selection statement (if, switch) is the

time for the condition evaluation + the maximum of the running times for the individual clauses in the selection. 4. Loop execution time is the sum, over the number of times the loop is executed, of the body time + time for the loop check and update operations, + time for the loop setup. Always assume that the loop executes the maximum number of iterations possible 5. Running time of a function call is 1 for setup + the time for any parameter calculations + the time required for

the execution of the function body. Example Sum = 0; In >> Value; while ( In ) { if ( Value < 0 ) { Sum = -Sum; Sum = Sum + Value;

}else { Sum = Sum + Value; } In >> Value; }

Recently Viewed Presentations

  • Lab 8: Types of and Study Designs - San Jose State University

    Lab 8: Types of and Study Designs - San Jose State University

    Lab 8: Types of Studies and Study Designs Lab Workbook (pp. 37 - 40) A fish or being taught to fish? Lab based on study by Jolson et al. (1992) Concepts and techniques remain valid for all disciplines all populations...
  • Mi visita a Nicargua Leccin de Espaol #2

    Mi visita a Nicargua Leccin de Espaol #2

    Conjugation of Verbs Verbs have different forms for different subjects/pronouns I am a boy. Yo SOY un chico. Conjugation of Verbs You are a girl. Tú ____ una chica. Conjugation of Verbs You are a girl. Tú ERES una chica....
  • CHAPTER - 07 Urinary System - Mackay Education

    CHAPTER - 07 Urinary System - Mackay Education

    URIC ACID (Ū-rĭk ĂS-ĭd) Nitrogenous waste formed when proteins are used in cells; it is excreted by the kidneys in urine. URINARY BLADDER (ŪR-ĭ-năr-ē BLĂ-dĕr) Hollow, muscular walls sacthat holds and stores urine until it is discharged from the body.
  • The Shoulder Joint

    The Shoulder Joint

    Neer's impingement sign:manoeuvreif positive : 1- Supraspinatus tendinitis 2-long head tendinitis. If the previous manoeuvre is positive, it may be repeated after injecting 10 mL of 1% lidocaine (local anesthetic)into the subacromial space; if the pain is abolished (or significantly...
  • Morbidity and Mortality in the HAART era Andrew

    Morbidity and Mortality in the HAART era Andrew

    This slide shows how many of these events: major cardiovascular events, kidney failure, liver cirrhosis, non-AIDS malignancy and non-AIDS deaths there were in the two trial arms. For serious non-AIDS as a whole, the hazard ratio of 1.6, with a...
  • New View of Gas and Dust in the Solar Nebula

    New View of Gas and Dust in the Solar Nebula

    New View of Gas and Dust in the Solar Nebula Measuring Oxygen in the Sun: Genesis Mission Results New View of Gas and Dust in the Solar Nebula Refractory inclusions (left) condensed from gas of solar composition with O-isotopes similar...
  • Polycom Solutions for Lync (NDA)

    Polycom Solutions for Lync (NDA)

    Full featured IP Phone with large color display and Polycom HD Voice™ technology. CX700. Standalone executive IP phone with color touch screen display and high definition audio. CX3000. Conference room device with multiple directional microphones. Optimized for Microsoft Lync -...
  • United States Map Work

    United States Map Work

    The West Largest & most sparsely populated region of the United States Includes the Great Plains, Rocky Mountains, and inter-mountain region. Western Region was mostly unsettled until early 1900s with aqueducts & irrigations systems being implemented in the region. The...