“It ain’t no good if it ain’t snappy enough.”(Efficient Computations) COS 116: 2/19/2008Sanjeev AroraAdministrative stuffReadings avail. from course web pageFeedback form on course web page; fully anonymous.HW1 due Thurs.Reminder for this week’s lab: Make sure you understand pseudocode. Come to lab with questions.Preview of upcoming topics: Cool lecture on computer music + labLab: Getting creative with Scribbler: art/music/danceLecture + Lab: Computer graphics…In what ways (according to Brian Hayes) is the universe like a cellular automaton?Discussion TimeQuestion: How do we measure the “speed” of an algorithm?Ideally, should be independent of:machinetechnology“Running time” of an algorithmDefinition: the number of “elementary operations” performed by the algorithmElementary operations: +, -, *, /, assignment, evaluation of conditionals(discussed also in pseudocode handout)“Speed” of computer: number of elementary steps it can perform per second (Simplified definition)Do not consider this in “running time” of algorithm; technology-dependent.Example: Find Minn items, stored in array AVariables are i, bestbest 1Do for i = 2 to n{if (A[ i ] < A[best]) then{ best i }}Example: Find Minn items, stored in array AVariables are i, bestbest 1Do for i = 2 to n {if (A[ i ] < A[best]) then{ best i }}How many operations executed before the loop?A: 0 B: 1 C: 2 D: 3Example: Find Minn items, stored in array AVariables are i, bestbest 1Do for i = 2 to n {if (A[ i ] < A[best]) then{ best i }}How many operations per iteration of the loop?A: 0 B: 1 C: 2 D: 3Example: Find Minn items, stored in array AVariables are i, bestbest 1Do for i = 2 to n {if (A[ i ] < A[best]) then{ best i }}How many times does the loop run?A: n B: n+1 C: n-1 D: 2nExample: Find Minn items, stored in array AVariables are i, bestbest 1Do for i = 2 to n {if (A[ i ] < A[best]) then{ best i }}Uses at most 2(n – 1) + 1 operationsInitializationNumber of iterations1 assignment & 1 comparison= 2 operations per loop iteration}(roughly = 2n)Discussion Time“20 Questions”: I have a number between 1 and a million in mind. Guess it by asking me yes/no questions, and keep the number of questions small.Question 1: “Is the number bigger than half a million?” NoQuestion 2: “Is the number bigger than a quarter million?”Strategy: Each question halves the range of possible answers.NoPseudocode: Guessing number from1 to nLower 1; Upper n; Found 0;Do while (Found=0) { Guess (Lower + Upper)/2; If (Guess = True Number){Found 1; Print(Guess);} If (Guess < True Number){ Lower Guess;} else {Upper Guess;}} BinarySearchHow many times doesthe loop run??Brief detour: Logarithms (CS view)log2 n = K means 2K-1 < n ≤ 2KIn words: K is the number of times you need to divide n by 2 in order to get a number ≤ 1John Napier2320104 log2 n83886081048576102416n“There are only 10 types of people in the world; those whoknow binary and those who don’t.”Next….Binary search and binary representation of numbersSay we know 0 ≤ number < 2KIs 2K / 2 ≤ number < 2K?No YesIs 2K / 4 ≤ number < 2K / 2?NoYesIs 2K × 3/8 ≤ number < 2K / 2?No Yes… … 0 2KBinary representations (cont’d)In general, each number can be uniquely identified by a sequence of yes/no answers to these questions.Correspond to paths down this “tree”:Is 2K / 2 ≤ number < 2K?NoYesIs 2K / 4 ≤ number < 2K / 2?NoYesIs 2K / 8 ≤ number < 2K / 4?No Yes… … Is 2K × 3/8 ≤ number < 2K / 2?No Yes… … …Binary representation of n(the more standard definition)n = 2k bk + 2k-1 bk-1 + … + 2 b2 + b1where the b’s are either 0 or 1)The binary representation of n is: n2 = bk bk – 1 … b2 b1Efficiency of Selection SortDo for i = 1 to n – 1 {Find cheapest bottle among those numbered i to nSwap that bottle and the i’th bottle.}For the i’th round, takes at most 2(n – i ) + 3To figure out running time, need to figure out how to sum (n – i) for i = 1 to n – 1 …and then double the result.About 2(n – i) steps3 stepsGauss’s trick : Sum of (n – i) for i = 1 to n – 1S = 1 + 2 + … + (n – 2) + (n – 1) + S = (n – 1) + (n – 2) + … + 2 + 12S = n + n + … + n + n2S = n(n – 1)So total time for selection sort is ≤ n(n – 1) + 3nn – 1 times(for large n, roughly = n2)Efficiency of Effort: A lens on the world“UPS Truck Driver’s Problem” (a.k.a. Traveling Salesman Problem or TSP)Handwriting Recognition andother forms of machine“intelligence”CAPTCHA’s[Jim Loy]Running times encountered in this lecturen=8388608n= 1048576n= 1024n= 8703687441776641099511627776104857664n28388608104857610248n2320103log2 nEfficiency really makes a difference!Can n particles do 2n “operations” in a single step?Or is Quantum Mechanics not quite correct?SIAM J. Computing26(5) 1997Computational efficiency has a bearing on physical
View Full Document
Unlocking...