Data Structures. Algorithm Performance and Big O Analysis


 Evan Carpenter
 5 years ago
 Views:
Transcription
1 Data Structures Algorithm Performance and Big O Analysis
2 What s an Algorithm? a clearly specified set of instructions to be followed to solve a problem. In essence: A computer program. In detail: Defined mathematically in a course on Theory of Computation (Turing).
3 What s Big O do? Measures the growth rate of an algorithm as the size of its input grows. Huh? O is a math function that helps estimate how much longer it takes to run n inputs versus n+1 inputs (or n+2, 2n, 3n ). Doesn t care what language you use! Only cares about the underlying algorithm.
4 What Doesn t O do? Doesn t tell you that algorithm A is faster than algorithm B for a particular input. Why not? Only tells you if one grows faster than another in a general sense for all inputs. Usually concerned with very large data inputs. Called asymptotic algorithm analysis.
5 Example: Doesn t Care About Particular Input public void algorithm1(object xinput) 16 million lines of code public void algorithm2(object xinput) if (xinput.size() == 2074) return; else 16 million different lines Which one is faster? Always? We only care about the average behavior of the 16 million lines.
6 How Calculate Run Time? 1. Each basic operation in the code counts for 1 time unit. A basic operation executes in the same time no matter what values it is supplied. Examples: Adding two integers is a basic operation. Reading a[1] is a basic operation (independent of array size). Summing the values in an array is NOT a basic operation (why?). 2. Ignore actual time units (seconds, days, etc.). Could be 1 ns for a fast computer or 1 day for a really slow computer. But for large inputs, won t matter. 3. Ignore time for method calls, returns, and declarations. Doesn t matter in the long run.
7 Run Time Example 1 Calculating N i 1 i 3 How long to run this code? public int sum(int num) int partialsum = 0; for(int i=1; i<= num; i++) partialsum += i * i * i; return partialsum;
8 Run Time Example 1 (cont.) Calculating i 1 public int sum(int num) int partialsum = 0; for(int i=1; i<= num; i++) partialsum += i * i * i; N i 3 How long to run this code? no cost costs 1 (to init/store in memory) costs 1 (to init/store in memory) costs N+1 (once for each test of <=) (and +1 because of last time through, when it fails) costs 2 N (once for each + and = recall i++ is just i = i + 1) total cost of 4N (costs 4 per execution 1 addition, 2 multiplications, 1 assignment) return partialsum; no cost Final tally: 1+1+(N+1)+2N+4N = 7N+3
9 Run Time Example 2 public int sum(int num) int partialsum = 0; for(int i=1; i<= num; i++) for(int j=1; j<= num; j++) partialsum += i * j; no cost costs 1 costs 1 costs N+1 costs 2N costs N*1 costs N*(N+1) costs N*2N costs N*N*3 return partialsum; no cost Final tally: 1+1+(N+1)+2N+N*1+N*(N+1) +N*2N+N*N*3 = 6N 2 +5N+3
10 But This is Overkill! public int sum(int num) int partialsum = 0; for(int i=1; i<= num; i++) for(int j=1; j<= num; j++) partialsum += i * j; return partialsum; Really only one operation, and it happens N 2 times So we say order of N 2, or O(N 2 )
11 Likewise, More Overkill Calculating N i 1 i 3 public int sum(int num) int partialsum = 0; for(int i=1; i<= num; i++) partialsum += i * i * i; return partialsum; Really only one operation, and it happens N times So we say order of N, or O(N)
12 Another Order Of Example public void cool(int n) for(int i=2; i<=n; i++) int j = (1 + i * i % 3 % i) / (i + 2); The heart of the code is this line. And it happens N times. So order of N. Or say O(N). Also, run time, T(N) = 10N  8. Can you show me?
13 Ah, Back to the BigO Call T(N) the run time. (Definition) Definition: T(N) = O(f(N)) if there are positive constants c and n 0 such that T(N) c f(n) when N > n 0. What s it mean? The run time is always less than f(n) for big enough N. (Only the highest order term matters!) (And constants don t matter.) Note: f(n) should be the smallest such function such that c and n 0 exist.
14 Example Using BigO Definition In last example, T(N) = 10N  8 So, let s guess T(N) = 10N  8 = O(N 3 ) To show that, must show 10N+1 c N 3 for some big enough N. Let c=1. Then 10N  8 c N 3 is true for all N > 10. In fact, true for all N > 4.» i.e., in definition, let n 0 = 4 So by definition, 10N  8 = O(N 3 ). But that s not as good as we can do! Let s try O(N).
15 Another Example Using Definition Let s guess T(N) = 10N8 = O(N) To show that, must show 10N8 c N for some big enough N. Let c=10. Then 10N8 c N is true for all N > 0.» i.e., in definition, let n 0 = 1 So by definition, 10N8 = O(N). No matter how hard you try, that s the smallest exponent on N that will work. i.e., O(N) is the best we can do. And O(N) matches our intuition from the example code!
16 Example: O Constants If T(N) = 23N Then T(N) = O(N 2 ) Which means: We guarantee that T(N) grows at a rate no faster than N 2. We say c N 2 is an upper bound on T(N). for c >23
17 Wait, you say Ok, T(N) = 23N = O(N 2 ). But 23N 2 grows faster than N 2. What s up with that? Shouldn t it be O(23N 2 )? NO! We are concerned with the rate of growth as N increases.
18 Wait, you say (Part 2) Consider 23N 2 and N 2. If N doubles in size, how much longer does it take to run? 23 (2N) 2 = 4 * (23 N 2 ) and (2N) 2 = 4 * (N 2 ) In both cases, takes 4 times as long. The rate of growth is just N 2. The constant didn t matter!!!
19 Another Example Consider T(N) = 5 N 3 versus N 3 If we triple the number of inputs, how much longer does it take to run? 5 (3N) 3 = 27 * (5 N 3 ) and (3N) 3 = 27 * (N 3 ) In both cases, takes 27 times as long. The rate of growth is just N 3. The constant didn t matter!!!
20 Yet Another Example If T(N) = 7N 3 N + 56 Then T(N) = O(N 3 ) Which means: We guarantee that T(N) grows at a rate no faster than N 3.
21 Wait a cotton, pickin T(N) = 7N 3 N + 56= O(N 3 ) You mean to say the N doesn t matter? Yup! We are concerned with the asymptotic behavior for big N. (Remember those limits in calculus?)
22 Wait a cotton, pickin (Part 2) As N gets huge, N 3 dwarfs N. N 3 = = 1,000,000,000 which is a lot bigger than N = (1 part in a million!) For even bigger values, it s quickly 1 part in a billion billion. (Then 1 part in a billion billion billion yada, yada, yada.) Only the biggest exponent matters. (Called asymptotic analysis.)
23 Wait a cotton, pickin (Part 3) Consider T(N) = 7N 3 N + 56 versus N 3 If we take 1000 times the number of inputs, how much longer does it take to run? 7 (1000N) N + 56= 1,000,000,000 * (7 N 3 ) 1000 N + 56 and (1000N) 3 = 1,000,000,000 * (N 3 ) The first term is MUCH bigger than the other terms. For any value of N, like 10, the smaller terms subtract an insignificant amount from the total. Smaller terms don t matter
24 Review: The Difference Between T(N) and O(N) T(N) is total run time. O(N) is the approximation to the run time where we ignore constants and lower order terms. We call it the growth rate. Also called asymptotic approximation. Example: if T(N) = 3 N 2 + N + 1 then T(N) = O(N 2 ) if T(N) = 3 N log(n) + 2 then T(N) = O(N log(n))
25 Review: The Difference Between T(N) and O(N) What do we mean by the equal sign? T(N) = O(N 2 ) Says the growth rate for T(N) is N 2. T(N) = O(N log(n)) Says T(N) has a growth rate of N log(n).
26 BigO Is Worst Case Remember, BigO says nothing about specific inputs, or specific input sizes. Suppose I give Bubble Sort the list 1, 2, 3, 4, 5» Stops right away. Fast! Suppose I give Bubble Sort the list 5, 4, 3, 2, 1» Worst case scenario! Slow. So need to calculate the max number of times code goes through a loop. e.g., if use a while loop, then the number of times code iterates should be calculated for the worst case.» By the way, a while loop is just like a for loop when calculating run time and growth rates.
27 Predicting How Long To Run: A Cool Application of BigO Can predict how long it will take to run a program with a very large data set. Do a test with a small practice data set. Then use bigo to predict how long it will take with a real (large) data set. Cool! Suppose we are using a program that is O(N 2 ). That s the growth rate! inputs per minute. Our test shows that it takes 1 minute to run 100 inputs. How long will it take to run 1000 inputs? Set it up this way: 2 100inputs 1000inputs takes 1min takes x min 2
28 Predicting How Much Data Will Run: A Cool Application of BigO Can predict how much data can be processed in a fixed amount of time. Do a test with a small data set. Then predict with bigo. Suppose we are using a program that is O(N 2 ). Our test shows that it takes 1 minute to run 100 inputs. How many inputs will run in 60 minutes? Set it up this way: 2 100inputs N inputs takes 1min takes 60min 2
29 General O Rules: Rule 1 Rule 1 if T 1 (N) = O(f(N)) and T 2 (N) = O(g(N)) then (a) T 1 (N) + T 2 (N) = max( O(f(N)), O(g(N)) ). (b) T 1 (N) * T 2 (N) = O( f(n)*g(n) ). These are bigo rules, not runtime rules. They apply equally well to any other math class!
30 Example for(int i=1; i<= nnum; i++) npartialsum += i * i * i; for(int i=1; i<= nnum; i++) for(int j=1; j<= nnum; j++) npartialsum += i * j; T 1 (N) = O(N) T 2 (N) = O(N 2 ) So the total run time is T 1 (N) + T 2 (N) = max(o(n), O(N 2 )) = O(N 2 )
31 General O Rules: Rule 2 Rule 2 (logn) k = O(N) for any constant k. What? Remember: T(N) = O(f(N)) when T(N) cf(n). So, we re just saying that (logn) k grows more slowly than N. In other words: logarithms grow VERY slowly.
32 run time T(N) Comparison of Growth Rates bad good LogN (LogN)^2 N NLogN N^2 N^3 2^N 0 N (number of inputs)
33 Rules For Programs Previous rules were general math rules. The following rules apply to computer programs. will still need to use the math rules!
34 Rules For Calculating Growth Rate: Rule 0 Rule 0: declarations, method calls, returns Zero cost. Example int myvariable; return 0; No cost. O(1). Constant growth rate. In other words, if we double the # of inputs, takes the same amount of time to run. We describe growth rates in terms of N. So, T(N) = 0 = 0 * N 0 = O(N 0 ) = O(1).
35 Rules For Calculating Growth Rule 1: for loops Rate: Rule 1 The growth rate of a for loop is at most the growth rate of the statements inside the for loop times the number of iterations. Example: O(N) for(i=0; i<n; i++) i++; One addition and one assignment operation Happens N/2 times! (i++ is happening two places sneaky)
36 Rules For Calculating Growth Rate: Rule 2 Rule 2: Nested Loops Analyze inside out. Growth rate of a statement inside nested loops is the growth rate of the statement multiplied by the product of the sizes of the loops. Example: for(int i=1; i<= num1; i++) for(int j=1; j<= num2; j++) a[i] = i * a[j]; 4 num2 num1 So total runtime = 4 * num2 * num1 = O(N 2 )
37 Rules For Calculating Growth Rate: Rule 3 Rule 3: Consecutive statements These just add (which means the maximum one counts). Example: for(int i=1; i<3; i++) a[i] = i; for(int i=1; i<n; i++) a[i] = i; 2 n1 T(n) = 2+(n1) = O(n) (just a bigo math rule!)
38 Rules For Calculating Growth Rate: Rule 4 Rule 4: if/else Growth rate is never more than the longest of the if or the else statements. Example if(happydog) print( bowwow ); else if(happycat) for(int i=1; i<35; i++) print( meow ); Assume print runs in 1 time unit T(N) = 34 = 34 N 0 = O(N 0 ) = O(1)
39 Example With Recursion public long factorial(long n) if(n<=1) else return 1; return n*factorial(n1); T(n) = 2 + Cost(factorial(n1))  or  T(n) = 2 + T(n1) 0 1 for multiplication, plus 1 for subtraction, plus the cost of the evaluation of factorial(n1) (roughly we are ignoring the n<=1 in the run time)
40 Example With Recursion 2 T(n) (n 1) O(n) Cost(factorial(n 1)) (2 Cost(factorial(n  2))) (2 (2 Cost(factorial(n 3)))) Last case of factorial(1) doesn t cost anything. Just returns.
41 Example With Recursion 3 Same thing, but different notation. T(n) T(n 1) (2 T(n  2)) (2 (2 T(n 3))) (n 1) O(n) 0
42 Example With Recursion 4 (in fact, was just a for loop in disguise) public long factorial(long n) if(n<=1) return 1; else return n*factorial(n1); public long factorial(long n) 1 long factorial = 1; for(int i=1; i<=n; i++) factorial = i*factorial; return factorial; N 0 O(N) T(N) = 1+N+0 = O(N)
43 Another Recursion Example (Fibonacci numbers) public long fib(int n) if(n<=1) return 1; else return fib(n1) + fib(n2); 0 3 for, + and, and also the cost of fib(n1)and the cost of fib(n2) T(n) = 3 + Cost(fib(n1)) + Cost(fib(n2))  or  T(n) = 3 + T(n1) + T(n2) (Job interviewer once asked me if this was a good way to program Fibonacci # s!)
44 Another Recursion Example 2 T(n) = 3 + T(n1) + T(n2) 3 + T(n2) + T(n3) 3 + T(n3) + T(n4) 3 + T(n3) + T(n4) etc. etc. etc. The cost keeps doubling in size!!! Exponential: O(2 n ) bad, bad, bad, bad, bad, bad
45 Tree Doubling Called a binary tree. Keeps doubling. Exponential (2 n ) growth. Bad growth rate! But we ll do some problems that traverse the tree in the other direction. Keeps halving. Opposite of exponential. And what s the inverse ( opposite ) of exponential? Logs! Logarithmic log(n) growth. Great growth rate! Stay tuned for logarithmic growth
46 Recursion NOT Always a For Loop in Disguise The Fibonacci recursion is O(2 N ). bad! Most for loops are O(N). But not all Stay tuned good!
CSE373: Data Structures and Algorithms Lecture 3: Math Review; Algorithm Analysis. Linda Shapiro Winter 2015
CSE373: Data Structures and Algorithms Lecture 3: Math Review; Algorithm Analysis Linda Shapiro Today Registration should be done. Homework 1 due 11:59 pm next Wednesday, January 14 Review math essential
More informationCSC 180 H1F Algorithm Runtime Analysis Lecture Notes Fall 2015
1 Introduction These notes introduce basic runtime analysis of algorithms. We would like to be able to tell if a given algorithm is timeefficient, and to be able to compare different algorithms. 2 Linear
More informationCSC148 Lecture 8. Algorithm Analysis Binary Search Sorting
CSC148 Lecture 8 Algorithm Analysis Binary Search Sorting Algorithm Analysis Recall definition of Big Oh: We say a function f(n) is O(g(n)) if there exists positive constants c,b such that f(n)
More informationAnalysis of Binary Search algorithm and Selection Sort algorithm
Analysis of Binary Search algorithm and Selection Sort algorithm In this section we shall take up two representative problems in computer science, work out the algorithms based on the best strategy to
More informationWhat Is Recursion? Recursion. Binary search example postponed to end of lecture
Recursion Binary search example postponed to end of lecture What Is Recursion? Recursive call A method call in which the method being called is the same as the one making the call Direct recursion Recursion
More informationWhy Use Binary Trees?
Binary Search Trees Why Use Binary Trees? Searches are an important application. What other searches have we considered? brute force search (with array or linked list) O(N) binarysearch with a presorted
More informationEfficiency of algorithms. Algorithms. Efficiency of algorithms. Binary search and linear search. Best, worst and average case.
Algorithms Efficiency of algorithms Computational resources: time and space Best, worst and average case performance How to compare algorithms: machineindependent measure of efficiency Growth rate Complexity
More informationIn mathematics, it is often important to get a handle on the error term of an approximation. For instance, people will write
Big O notation (with a capital letter O, not a zero), also called Landau's symbol, is a symbolism used in complexity theory, computer science, and mathematics to describe the asymptotic behavior of functions.
More informationThe UnionFind Problem Kruskal s algorithm for finding an MST presented us with a problem in datastructure design. As we looked at each edge,
The UnionFind Problem Kruskal s algorithm for finding an MST presented us with a problem in datastructure design. As we looked at each edge, cheapest first, we had to determine whether its two endpoints
More informationWhy? A central concept in Computer Science. Algorithms are ubiquitous.
Analysis of Algorithms: A Brief Introduction Why? A central concept in Computer Science. Algorithms are ubiquitous. Using the Internet (sending email, transferring files, use of search engines, online
More informationClass Overview. CSE 326: Data Structures. Goals. Goals. Data Structures. Goals. Introduction
Class Overview CSE 326: Data Structures Introduction Introduction to many of the basic data structures used in computer software Understand the data structures Analyze the algorithms that use them Know
More informationAlgorithms. Margaret M. Fleck. 18 October 2010
Algorithms Margaret M. Fleck 18 October 2010 These notes cover how to analyze the running time of algorithms (sections 3.1, 3.3, 4.4, and 7.1 of Rosen). 1 Introduction The main reason for studying bigo
More informationThe Running Time of Programs
CHAPTER 3 The Running Time of Programs In Chapter 2, we saw two radically different algorithms for sorting: selection sort and merge sort. There are, in fact, scores of algorithms for sorting. This situation
More informationSIMS 255 Foundations of Software Design. Complexity and NPcompleteness
SIMS 255 Foundations of Software Design Complexity and NPcompleteness Matt Welsh November 29, 2001 mdw@cs.berkeley.edu 1 Outline Complexity of algorithms Space and time complexity ``Big O'' notation Complexity
More informationrecursion, O(n), linked lists 6/14
recursion, O(n), linked lists 6/14 recursion reducing the amount of data to process and processing a smaller amount of data example: process one item in a list, recursively process the rest of the list
More informationMany algorithms, particularly divide and conquer algorithms, have time complexities which are naturally
Recurrence Relations Many algorithms, particularly divide and conquer algorithms, have time complexities which are naturally modeled by recurrence relations. A recurrence relation is an equation which
More informationCost Model: Work, Span and Parallelism. 1 The RAM model for sequential computation:
CSE341T 08/31/2015 Lecture 3 Cost Model: Work, Span and Parallelism In this lecture, we will look at how one analyze a parallel program written using Cilk Plus. When we analyze the cost of an algorithm
More informationSorting revisited. Build the binary search tree: O(n^2) Traverse the binary tree: O(n) Total: O(n^2) + O(n) = O(n^2)
Sorting revisited How did we use a binary search tree to sort an array of elements? Tree Sort Algorithm Given: An array of elements to sort 1. Build a binary search tree out of the elements 2. Traverse
More information16. Recursion. COMP 110 Prasun Dewan 1. Developing a Recursive Solution
16. Recursion COMP 110 Prasun Dewan 1 Loops are one mechanism for making a program execute a statement a variable number of times. Recursion offers an alternative mechanism, considered by many to be more
More informationRecursive Algorithms. Recursion. Motivating Example Factorial Recall the factorial function. { 1 if n = 1 n! = n (n 1)! if n > 1
Recursion Slides by Christopher M Bourke Instructor: Berthe Y Choueiry Fall 007 Computer Science & Engineering 35 Introduction to Discrete Mathematics Sections 717 of Rosen cse35@cseunledu Recursive Algorithms
More informationCS/COE 1501 http://cs.pitt.edu/~bill/1501/
CS/COE 1501 http://cs.pitt.edu/~bill/1501/ Lecture 01 Course Introduction Metanotes These notes are intended for use by students in CS1501 at the University of Pittsburgh. They are provided free of charge
More informationBinary Heaps * * * * * * * / / \ / \ / \ / \ / \ * * * * * * * * * * * / / \ / \ / / \ / \ * * * * * * * * * *
Binary Heaps A binary heap is another data structure. It implements a priority queue. Priority Queue has the following operations: isempty add (with priority) remove (highest priority) peek (at highest
More information6. Standard Algorithms
6. Standard Algorithms The algorithms we will examine perform Searching and Sorting. 6.1 Searching Algorithms Two algorithms will be studied. These are: 6.1.1. inear Search The inear Search The Binary
More informationBinary search algorithm
Binary search algorithm Definition Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than
More informationSection IV.1: Recursive Algorithms and Recursion Trees
Section IV.1: Recursive Algorithms and Recursion Trees Definition IV.1.1: A recursive algorithm is an algorithm that solves a problem by (1) reducing it to an instance of the same problem with smaller
More informationAlgorithm Design and Recursion
Chapter 13 Algorithm Design and Recursion Objectives To understand basic techniques for analyzing the efficiency of algorithms. To know what searching is and understand the algorithms for linear and binary
More informationAnalysis of Computer Algorithms. Algorithm. Algorithm, Data Structure, Program
Analysis of Computer Algorithms Hiroaki Kobayashi Input Algorithm Output 12/13/02 Algorithm Theory 1 Algorithm, Data Structure, Program Algorithm Welldefined, a finite stepbystep computational procedure
More informationCS473  Algorithms I
CS473  Algorithms I Lecture 9 Sorting in Linear Time View in slideshow mode 1 How Fast Can We Sort? The algorithms we have seen so far: Based on comparison of elements We only care about the relative
More informationThe Tower of Hanoi. Recursion Solution. Recursive Function. Time Complexity. Recursive Thinking. Why Recursion? n! = n* (n1)!
The Tower of Hanoi Recursion Solution recursion recursion recursion Recursive Thinking: ignore everything but the bottom disk. 1 2 Recursive Function Time Complexity Hanoi (n, src, dest, temp): If (n >
More informationBinary Heap Algorithms
CS Data Structures and Algorithms Lecture Slides Wednesday, April 5, 2009 Glenn G. Chappell Department of Computer Science University of Alaska Fairbanks CHAPPELLG@member.ams.org 2005 2009 Glenn G. Chappell
More informationZabin Visram Room CS115 CS126 Searching. Binary Search
Zabin Visram Room CS115 CS126 Searching Binary Search Binary Search Sequential search is not efficient for large lists as it searches half the list, on average Another search algorithm Binary search Very
More informationAlgorithm Analysis [2]: ifelse statements, recursive algorithms. COSC 2011, Winter 2004, Section N Instructor: N. Vlajic
1 Algorithm Analysis []: ifelse statements, recursive algorithms COSC 011, Winter 004, Section N Instructor: N. Vlajic Algorithm Analysis forloop Running Time The running time of a simple loop for (int
More informationNotes on Factoring. MA 206 Kurt Bryan
The General Approach Notes on Factoring MA 26 Kurt Bryan Suppose I hand you n, a 2 digit integer and tell you that n is composite, with smallest prime factor around 5 digits. Finding a nontrivial factor
More informationSolving Problems Recursively
Solving Problems Recursively Recursion is an indispensable tool in a programmer s toolkit Allows many complex problems to be solved simply Elegance and understanding in code often leads to better programs:
More informationUNIT AUTHOR: Elizabeth Hume, Colonial Heights High School, Colonial Heights City Schools
Money & Finance I. UNIT OVERVIEW & PURPOSE: The purpose of this unit is for students to learn how savings accounts, annuities, loans, and credit cards work. All students need a basic understanding of how
More informationCOLLEGE ALGEBRA. Paul Dawkins
COLLEGE ALGEBRA Paul Dawkins Table of Contents Preface... iii Outline... iv Preliminaries... Introduction... Integer Exponents... Rational Exponents... 9 Real Exponents...5 Radicals...6 Polynomials...5
More informationDay 1. This is CS50 for MBAs. Harvard Busines School. Spring 2015. Cheng Gong
This is CS50 for MBAs. Harvard Busines School. Spring 2015. Cheng Gong Table of Contents Gangnam Style... 1 Internet Issues... 2 Course info... 6 Day 0, recap... 7 Peanut butter jelly time... 8 Sorting...
More informationAttention: This material is copyright 19951997 Chris Hecker. All rights reserved.
Attention: This material is copyright 19951997 Chris Hecker. All rights reserved. You have permission to read this article for your own education. You do not have permission to put it on your website
More informationFunctions Recursion. C++ functions. Declare/prototype. Define. Call. int myfunction (int ); int myfunction (int x){ int y = x*x; return y; }
Functions Recursion C++ functions Declare/prototype int myfunction (int ); Define int myfunction (int x){ int y = x*x; return y; Call int a; a = myfunction (7); function call flow types type of function
More information4.2 Sorting and Searching
Sequential Search: Java Implementation 4.2 Sorting and Searching Scan through array, looking for key. search hit: return array index search miss: return 1 public static int search(string key, String[]
More informationBinary Heaps. CSE 373 Data Structures
Binary Heaps CSE Data Structures Readings Chapter Section. Binary Heaps BST implementation of a Priority Queue Worst case (degenerate tree) FindMin, DeleteMin and Insert (k) are all O(n) Best case (completely
More informationChapter 7: Additional Topics
Chapter 7: Additional Topics In this chapter we ll briefly cover selected advanced topics in fortran programming. All the topics come in handy to add extra functionality to programs, but the feature you
More informationExternal Sorting. Chapter 13. Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 1
External Sorting Chapter 13 Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 1 Why Sort? A classic problem in computer science! Data requested in sorted order e.g., find students in increasing
More informationAP Computer Science AB Syllabus 1
AP Computer Science AB Syllabus 1 Course Resources Java Software Solutions for AP Computer Science, J. Lewis, W. Loftus, and C. Cocking, First Edition, 2004, Prentice Hall. Video: Sorting Out Sorting,
More informationIntroduction to SQL for Data Scientists
Introduction to SQL for Data Scientists Ben O. Smith College of Business Administration University of Nebraska at Omaha Learning Objectives By the end of this document you will learn: 1. How to perform
More informationSection 4.1 Rules of Exponents
Section 4.1 Rules of Exponents THE MEANING OF THE EXPONENT The exponent is an abbreviation for repeated multiplication. The repeated number is called a factor. x n means n factors of x. The exponent tells
More information14:440:127 Introduction to Computers for Engineers. Notes for Lecture 06
14:440:127 Introduction to Computers for Engineers Notes for Lecture 06 Rutgers University, Spring 2010 Instructor Blase E. Ur 1 Loop Examples 1.1 Example Sum Primes Let s say we wanted to sum all 1,
More informationData Structures and Algorithms Written Examination
Data Structures and Algorithms Written Examination 22 February 2013 FIRST NAME STUDENT NUMBER LAST NAME SIGNATURE Instructions for students: Write First Name, Last Name, Student Number and Signature where
More informationSearching Algorithms
Searching Algorithms The Search Problem Problem Statement: Given a set of data e.g., int [] arr = {10, 2, 7, 9, 7, 4}; and a particular value, e.g., int val = 7; Find the first index of the value in the
More informationClub Accounts. 2011 Question 6.
Club Accounts. 2011 Question 6. Anyone familiar with Farm Accounts or Service Firms (notes for both topics are back on the webpage you found this on), will have no trouble with Club Accounts. Essentially
More informationBoolean Expressions, Conditions, Loops, and Enumerations. Precedence Rules (from highest to lowest priority)
Boolean Expressions, Conditions, Loops, and Enumerations Relational Operators == // true if two values are equivalent!= // true if two values are not equivalent < // true if left value is less than the
More informationCS104: Data Structures and ObjectOriented Design (Fall 2013) October 24, 2013: Priority Queues Scribes: CS 104 Teaching Team
CS104: Data Structures and ObjectOriented Design (Fall 2013) October 24, 2013: Priority Queues Scribes: CS 104 Teaching Team Lecture Summary In this lecture, we learned about the ADT Priority Queue. A
More informationBattleships Searching Algorithms
Activity 6 Battleships Searching Algorithms Summary Computers are often required to find information in large collections of data. They need to develop quick and efficient ways of doing this. This activity
More informationRandom Fibonaccitype Sequences in Online Gambling
Random Fibonaccitype Sequences in Online Gambling Adam Biello, CJ Cacciatore, Logan Thomas Department of Mathematics CSUMS Advisor: Alfa Heryudono Department of Mathematics University of Massachusetts
More informationClassification  Examples
Lecture 2 Scheduling 1 Classification  Examples 1 r j C max given: n jobs with processing times p 1,...,p n and release dates r 1,...,r n jobs have to be scheduled without preemption on one machine taking
More informationComputer Science 210: Data Structures. Searching
Computer Science 210: Data Structures Searching Searching Given a sequence of elements, and a target element, find whether the target occurs in the sequence Variations: find first occurence; find all occurences
More information6.080 / 6.089 Great Ideas in Theoretical Computer Science Spring 2008
MIT OpenCourseWare http://ocw.mit.edu 6.080 / 6.089 Great Ideas in Theoretical Computer Science Spring 2008 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.
More informationSection 1.5 Exponents, Square Roots, and the Order of Operations
Section 1.5 Exponents, Square Roots, and the Order of Operations Objectives In this section, you will learn to: To successfully complete this section, you need to understand: Identify perfect squares.
More informationPersistent Data Structures
6.854 Advanced Algorithms Lecture 2: September 9, 2005 Scribes: Sommer Gentry, Eddie Kohler Lecturer: David Karger Persistent Data Structures 2.1 Introduction and motivation So far, we ve seen only ephemeral
More informationThe Taxman Game. Robert K. Moniot September 5, 2003
The Taxman Game Robert K. Moniot September 5, 2003 1 Introduction Want to know how to beat the taxman? Legally, that is? Read on, and we will explore this cute little mathematical game. The taxman game
More information8 Square matrices continued: Determinants
8 Square matrices continued: Determinants 8. Introduction Determinants give us important information about square matrices, and, as we ll soon see, are essential for the computation of eigenvalues. You
More informationThis Unit: Floating Point Arithmetic. CIS 371 Computer Organization and Design. Readings. Floating Point (FP) Numbers
This Unit: Floating Point Arithmetic CIS 371 Computer Organization and Design Unit 7: Floating Point App App App System software Mem CPU I/O Formats Precision and range IEEE 754 standard Operations Addition
More informationKapitel 1 Multiplication of Long Integers (Faster than Long Multiplication)
Kapitel 1 Multiplication of Long Integers (Faster than Long Multiplication) Arno Eigenwillig und Kurt Mehlhorn An algorithm for multiplication of integers is taught already in primary school: To multiply
More informationNumeracy Preparation Guide. for the. VETASSESS Test for Certificate IV in Nursing (Enrolled / Division 2 Nursing) course
Numeracy Preparation Guide for the VETASSESS Test for Certificate IV in Nursing (Enrolled / Division Nursing) course Introduction The Nursing course selection (or entrance) test used by various Registered
More informationNumerical Matrix Analysis
Numerical Matrix Analysis Lecture Notes #10 Conditioning and / Peter Blomgren, blomgren.peter@gmail.com Department of Mathematics and Statistics Dynamical Systems Group Computational Sciences Research
More informationMultiplying and Dividing Fractions
Multiplying and Dividing Fractions 1 Overview Fractions and Mixed Numbers Factors and Prime Factorization Simplest Form of a Fraction Multiplying Fractions and Mixed Numbers Dividing Fractions and Mixed
More informationPseudo code Tutorial and Exercises Teacher s Version
Pseudo code Tutorial and Exercises Teacher s Version Pseudocode is an informal way to express the design of a computer program or an algorithm in 1.45. The aim is to get the idea quickly and also easy
More informationCORDIC: How Hand Calculators Calculate
Integre Technical Publishing Co., Inc. College Mathematics Journal 40: December 7, 008 :49 p.m. sultan.tex page 87 CORDIC: How Hand Calculators Calculate Alan Sultan Alan Sultan is a professor of mathematics
More informationReturn on Investment (ROI)
ROI 1 Return on Investment (ROI) Prepared by Sarah Major What is ROI? Return on investment (ROI) is a measure that investigates the amount of additional profits produced due to a certain investment. Businesses
More informationAn example of a computable
An example of a computable absolutely normal number Verónica Becher Santiago Figueira Abstract The first example of an absolutely normal number was given by Sierpinski in 96, twenty years before the concept
More informationHydraulics Prof. A. K. Sarma Department of Civil Engineering Indian Institute of Technology, Guwahati. Module No. # 02 Uniform Flow Lecture No.
Hydraulics Prof. A. K. Sarma Department of Civil Engineering Indian Institute of Technology, Guwahati Module No. # 02 Uniform Flow Lecture No. # 04 Computation of Uniform Flow (Part 02) Welcome to this
More informationChapter 3. if 2 a i then location: = i. Page 40
Chapter 3 1. Describe an algorithm that takes a list of n integers a 1,a 2,,a n and finds the number of integers each greater than five in the list. Ans: procedure greaterthanfive(a 1,,a n : integers)
More informationMITI Coding: Transcript 5
1 MITI Coding: Transcript 5 T: Randy, thanks for coming in today. I wonder if it would be ok if I shared just a few facts with you that I ve gotten from the intake worker. And then we can go on to talk
More information5.2 The Master Theorem
170 CHAPTER 5. RECURSION AND RECURRENCES 5.2 The Master Theorem Master Theorem In the last setion, we saw three different kinds of behavior for reurrenes of the form at (n/2) + n These behaviors depended
More informationHow to Study Mathematics Written by Paul Dawkins
How to Study Mathematics Written by Paul Dawkins Before I get into the tips for how to study math let me first say that everyone studies differently and there is no one right way to study for a math class.
More informationLecture Notes on Linear Search
Lecture Notes on Linear Search 15122: Principles of Imperative Computation Frank Pfenning Lecture 5 January 29, 2013 1 Introduction One of the fundamental and recurring problems in computer science is
More informationData Structures and Algorithms
Data Structures and Algorithms Computational Complexity Escola Politècnica Superior d Alcoi Universitat Politècnica de València Contents Introduction Resources consumptions: spatial and temporal cost Costs
More informationChapter 5 Functions. Introducing Functions
Chapter 5 Functions 1 Introducing Functions A function is a collection of statements that are grouped together to perform an operation Define a function Invoke a funciton return value type method name
More informationLecture 4 Online and streaming algorithms for clustering
CSE 291: Geometric algorithms Spring 2013 Lecture 4 Online and streaming algorithms for clustering 4.1 Online kclustering To the extent that clustering takes place in the brain, it happens in an online
More informationPolynomials. Dr. philippe B. laval Kennesaw State University. April 3, 2005
Polynomials Dr. philippe B. laval Kennesaw State University April 3, 2005 Abstract Handout on polynomials. The following topics are covered: Polynomial Functions End behavior Extrema Polynomial Division
More informationIMPROVING PERFORMANCE OF RANDOMIZED SIGNATURE SORT USING HASHING AND BITWISE OPERATORS
Volume 2, No. 3, March 2011 Journal of Global Research in Computer Science RESEARCH PAPER Available Online at www.jgrcs.info IMPROVING PERFORMANCE OF RANDOMIZED SIGNATURE SORT USING HASHING AND BITWISE
More informationLecture 10 UnionFind The unionnd data structure is motivated by Kruskal's minimum spanning tree algorithm (Algorithm 2.6), in which we needed two operations on disjoint sets of vertices: determine whether
More informationA binary heap is a complete binary tree, where each node has a higher priority than its children. This is called heaporder property
CmSc 250 Intro to Algorithms Chapter 6. Transform and Conquer Binary Heaps 1. Definition A binary heap is a complete binary tree, where each node has a higher priority than its children. This is called
More informationExternal Sorting. Why Sort? 2Way Sort: Requires 3 Buffers. Chapter 13
External Sorting Chapter 13 Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 1 Why Sort? A classic problem in computer science! Data requested in sorted order e.g., find students in increasing
More information3.2 LOGARITHMIC FUNCTIONS AND THEIR GRAPHS. Copyright Cengage Learning. All rights reserved.
3.2 LOGARITHMIC FUNCTIONS AND THEIR GRAPHS Copyright Cengage Learning. All rights reserved. What You Should Learn Recognize and evaluate logarithmic functions with base a. Graph logarithmic functions.
More informationREVIEW EXERCISES DAVID J LOWRY
REVIEW EXERCISES DAVID J LOWRY Contents 1. Introduction 1 2. Elementary Functions 1 2.1. Factoring and Solving Quadratics 1 2.2. Polynomial Inequalities 3 2.3. Rational Functions 4 2.4. Exponentials and
More informationIntroduction to Python
WEEK ONE Introduction to Python Python is such a simple language to learn that we can throw away the manual and start with an example. Traditionally, the first program to write in any programming language
More informationParallel Scalable Algorithms Performance Parameters
www.bsc.es Parallel Scalable Algorithms Performance Parameters Vassil Alexandrov, ICREA  Barcelona Supercomputing Center, Spain Overview Sources of Overhead in Parallel Programs Performance Metrics for
More informationChapter 1. NP Completeness I. 1.1. Introduction. By Sariel HarPeled, December 30, 2014 1 Version: 1.05
Chapter 1 NP Completeness I By Sariel HarPeled, December 30, 2014 1 Version: 1.05 "Then you must begin a reading program immediately so that you man understand the crises of our age," Ignatius said solemnly.
More informationLoop Invariants and Binary Search
Loop Invariants and Binary Search Chapter 4.3.3 and 9.3.11  Outline Ø Iterative Algorithms, Assertions and Proofs of Correctness Ø Binary Search: A Case Study  2  Outline Ø Iterative Algorithms, Assertions
More informationDistributed Computing over Communication Networks: Maximal Independent Set
Distributed Computing over Communication Networks: Maximal Independent Set What is a MIS? MIS An independent set (IS) of an undirected graph is a subset U of nodes such that no two nodes in U are adjacent.
More informationFactoring Numbers. Factoring numbers means that we break numbers down into the other whole numbers that multiply
Factoring Numbers Author/Creation: Pamela Dorr, September 2010. Summary: Describes two methods to help students determine the factors of a number. Learning Objectives: To define prime number and composite
More informationTo My Parents Laxmi and Modaiah. To My Family Members. To My Friends. To IIT Bombay. To All Hard Workers
To My Parents Laxmi and Modaiah To My Family Members To My Friends To IIT Bombay To All Hard Workers Copyright 2010 by CareerMonk.com All rights reserved. Designed by Narasimha Karumanchi Printed in
More informationBinary Multiplication
Binary Multiplication Q: How do we multiply two numbers? eg. 12, 345 6, 789 111105 987600 8641500 + 74070000 83, 810, 205 10111 10101 10111 00000 1011100 0000000 + 101110000 111100011 Pad, multiply and
More informationWith the Tan function, you can calculate the angle of a triangle with one corner of 90 degrees, when the smallest sides of the triangle are given:
Page 1 In game development, there are a lot of situations where you need to use the trigonometric functions. The functions are used to calculate an angle of a triangle with one corner of 90 degrees. By
More informationDynamic Programming. Lecture 11. 11.1 Overview. 11.2 Introduction
Lecture 11 Dynamic Programming 11.1 Overview Dynamic Programming is a powerful technique that allows one to solve many different types of problems in time O(n 2 ) or O(n 3 ) for which a naive approach
More informationFactoring ax 2 + bx + c  Teacher Notes
Southern Nevada Regional Professi onal D evel opment Program VOLUME 1, ISSUE 8 MAY 009 A N ewsletter from the Sec ondary Mathematic s Team Factoring ax + bx + c  Teacher Notes Here we look at sample teacher
More informationCS473  Algorithms I
CS473  Algorithms I Lecture 4 The DivideandConquer Design Paradigm View in slideshow mode 1 Reminder: Merge Sort Input array A sort this half sort this half Divide Conquer merge two sorted halves Combine
More information