### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 464 Class Note for CS 25100 at Purdue

### View Full Document

## 23

## 0

## Popular in Course

## Popular in Department

This 17 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Purdue University taught by a professor in Fall. Since its upload, it has received 23 views.

## Similar to Course at Purdue

## Reviews for 464 Class Note for CS 25100 at Purdue

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

ANALYSIS OF ALGORITHMS Quick Mathematical Review Running Time PseudoCode Analysis of Algorithms Asymptotic Notation Asymptotic Analysis T01 was Algorithm Output Analysis of Algorithms A Quick Math Review Logarithms and Exponents properties of logarithms 10gbXY10ng 10ng 10gbXY Z 10ng 39 10ng 10ng0 oclogbx logaX 10gba logab properties of exponentials abc abac abc abc abaC ab39c 10gb ba a be 2 a clogab Analysis of Algorithms A Quick Math Review cont Floor Lxl the largest integer S x Ceiling lxl the smallest integer x Summations general de nition fU fsfslfs2 ft is Where f is a function S is the start index and t is the end index Geometric progression i 2 at given an integer n O and a real number 0 lt61 72 l n i 2 n l an1 2alaama 1 a i0 geometric progressions exhibit exponential growth Analysis of Algorithms 3 Average Case vs Worst Case Running Time of an Algorithm An algorithm may run faster on certain data sets than on others Finding the average case can be very dif cult so typically algorithms are measured by the worstcase time complexity Also in certain application domains eg air traf c control surgery knowing the worstcase time complexity is of crucial importance 5 ms worstcase 4 ms averagecase bestcase 2 ms 1 ms A B C D E F G Input Instance Running Time U E Analysis of Algorithms 4 Measuring the Running Time How should we measure the running time of an algorithm Experimental Study Write a program that implements the algorithm Run the program with data sets of varying size and composition Use a method like SystemcurrentTimeMillis to get an accurate measure of the actual running time The resulting data set should look something like t ms 60 50 I 40 l l 30 I I I I I I I I I 20 I I I I I 10 I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I n 0 50 100 Analysis of Algorithms 5 Beyond Experimental Studies Experimental studies have several limitations It is necessary to implement and test the algorithm in order to determine its running time Experiments can be done only on a limited set of inputs and may not be indicative of the running time on other inputs not included in the experiment In order to compare two algorithms the same hardware and software environments should be used We will now develop a general methodology for analyzing the running time of algorithms that Uses a highlevel description of the algorithm instead of testing one of its implementations Takes into account all possible inputs Allows one to evaluate the ef ciency of any algorithm in a way that is independent from the hardware and software environment Analysis of Algorithms 6 PseudoCode Pseudocode is a description of an algorithm that is more structured than usual prose but less formal than a programming language Example nding the maximum element of an array Algorithm arrayMaxA 11 Input An array A storing n integers Output The maximum element in A currentMax e AO forte l ton l do if currentMax lt Al39 then currentMax e Al39 return currentAax Pseudocode is our preferred notation for describing algorithms However pseudocode hides program design issues Analysis of Algorithms 7 use lt for assignment What is PseudoCode A mixture of natural language and highlevel programming concepts that describes the main ideas behind a generic implementation of a data structure or algorithm Expressions use standard mathematical symbols to describe numeric and boolean expressions cc77 39 1n Java use for the equality relationship in Java Method Declarations Algorithm nameparam1 param2 Programming Constructs decision structures whileloops repeatloops forloop array indexing ethods calls returns if then else while do repeat until for do Ai object methodargs return value Analysis of Algorithms A Quick Math Review cont Arithmetic progressions Anexarnp1e n 2 11 11 39123 21 n 2 i1 two Visual representations n1 A Analysis of Algorithms Analysis of Algorithms Primitive Operations Lowlevel computations that are largely independent from the programming language and can be identi ed in pseudocode eg calling a method and returning from a method performing an arithmetic operation eg addition comparing two numbers etc By inspecting the pseudocode we can count the number of primitive operations executed by an algorithm Example Algorithm arrayMaxA 11 Input An array A storing n integers Output The maximum element in A currentMax e AO forte l ton l do if currentMax lt Al39 then currentMax e Al39 return currentMax Analysis of Algorithms 10 Asymptotic Notation Goal To simplify analysis by getting rid of unneeded information Like rounding 1000001 21000000 3722 z n2 The BigOh Notation given functions fn and gn we say that fn is 0gn if and only if fn S c gn for n no c and n0 are constants fn and gn are functions over nonnegative integers cgm f 74 Running Time n0 Input Size Analysis of Algorithms 11 Asymptotic Notation cont Note Even though 7n 3 is 0075 it is expected that such an approximation be of as small an order as possible Simple Rule Drop lower order terms and constant factors 7n 3 is 0n 8nzlog n 5712 n is 0nzlog n Special classes of algorithms logarithmic 0log n linear 0n quadratic 0n2 polynomial 0nk k 1 exponential 0a ngt l Relatives of the BigOh 2fn Big Omega fn Big Theta Analysis of Algorithms 12 Asymptotic Analysis of The Running Time Use the BigOh notation to express the number of primitive operations executed as a function of the input size For example we say that the arrayMax algorithm runs in 0n time Comparing the asymptotic running time an algorithm that runs in 0n time is better than one that runs in 0n2 time similarly 0log n is better than 0n hierarchy of functions 10gnltltnltltnzltltn3ltlt2n Caution Beware of very large constant factors An algorithm running in time 1000000 72 is still 0n but might be less ef cient on your data set than one running in time 2n2 which is 0n2 Analysis of Algorithms 13 Example of Asymptotic Analysis An algorithm for computing pre x averages Algorithm pre xAverages 1 X Input An nelement array X of numbers Output An nelement array A of numbers such that At is the average of elements X0 Xl Let A be an array of 11 numbers forieOtonldo a e 0 forfeOtotdo a e a X39 Ai e al 1 return array A Analysis Analysis of Algorithms 14 Example of Asymptotic Analysis A better algorithm for computing pre x averages Algorithm pre xAverages2X Input An nelement array X of numbers Output An nelement array A of numbers such that At is the average of elements X0 Xl Let A be an array of 11 numbers s e 0 forieOtonldo s e s Xt Ai e sz 1 return array A Analysis Analysis of Algorithms 15 Advanced Topics Simple Justi cation Techniques By Example Find an example Find a counter example The Contra Attack Find a contradiction in the negative statement Contrapositive Induction and LoopInvariants Induction 1 Prove the base case 2 Prove that any case n implies the next case n l is also true Loop invariants Prove initial claim SO Show that SH implies S will be true after iteration 139 Analysis of Algorithms 16 Advanced Topics Other Justi cation Techniques Proof by Excessive Waving of Hands Proof by Incomprehensible Diagram Proof by Very Large Bribes see instructor after class Proof by Violent Metaphor Don t argue with anyone who always assumes a sequence consists of hand grenades The Emperor s New Clothes Method This proof is so obvious only an idiot wouldn t be able to understand it Analysis of Algorithms 17

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.