Algorithms



CS 302Elaine RichAlgorithmsConsider the problem of making a peanut butter and jelly sandwich.Write an algorithm to accomplish the task.Mark the places where nontrivial knowledge is required and indicate what it is.In class, we showed the circuitry for binary addition. Of course, in real computers, we need to perform other arithmetic operations as well. Let’s consider multiplication. Notice the relationship between multiplication and addition:5 * 3 = 3 + 3 + 3 + 3 + 3Imagine that you have a machine with an addition circuit but you now want to do multiplication. You can do it in software. Fill in the required code in the following Python function. (Hint: actually type this up and run it. That way you can be sure you submit a correct answer.)def mult(n, m): """ Multiplies n by m, using only addition. Precondition: n and m are positive integers. """ # code to compute n * m and make it the value of the variable ans return(ans)Consider the following chunk of code that we used as an example of the if/elif/else construct:if x < 10:print("small")elif x > 100:print("big")else:print("so-so")This code won’t work in all situations. What must be true before it starts in order for it not to produce an error? In other words, what is its precondition? (Hint: Run it on various inputs. Think about things it isn’t meant for.)Recall this program that we looked at when we were learning Python. def vowels(st): new = "" for i in range(len(st)): if st[i]=="a" or st[i]=="e" or st[i]=="i" or st[i]=="o" or st[i]=="u" or st[i]=="y": new = new + "*" else: new = new + st[i] return(new)Describe in English what it does. Use big-O notation to describe how many steps it executes as a function of |st| (the length of the input string st). What is the sum of the integers from 1 to 9876?The prime factorization of a positive integer n is the bag (think of a bag as a set but duplicates are allowed) of positive integers with two properties:The product of the integers in the bag is n.All the integers in the bag are prime. (1 is not a prime number, so cannot be in the bag.)So, for example, the prime factorization of 612 is {2, 2, 3, 3, 17}. The prime factorization of 17 is {17}. What is the prime factorization of 714? Recall the code we wrote to implement Euclid’s method for determining the greatest common divisor (gcd) of two integers:def gcd_euclid(n,m):if m == 0: return(n) else: return gcd_euclid(m, n%m)Compute gcd(87, 6). Use gcd_euclid and show each of the calls to it starting with gcd_euclid(87,6).In class, I presented the function newton that computes square root using Newton’s method:def newton(n): guess = 1 while abs(guess**2 - n) > .00000001: guess = (guess + n/guess)/2 return(guess)Use it to find sqrt(1287658).Suppose that you are given the following sorted list of numbers:3, 7, 21, 26, 35, 41, 43, 45, 54, 58, 62, 67, 71, 77, 80, 82, 91, 95Show the order in which you will check the elements of this list if you are using sequential search to look for 80.Show the order in which you will check the elements of this list if you are using binary search to look for 80.Give an example of a number that you would find faster if you used sequential search. Show the steps that bubble sort will perform if given the input list [21, 2, 4, 98, 5].Give two examples of everyday heuristics that you use.Facebook uses a heuristic search algorithm to find the things to show on your home page. Just from watching what you get, can you think of factors that contribute to the objective function that it uses? (If you’ve never gotten on Facebook, as some friends to help you on this.)Take your slider puzzle. Randomly make at least 20 moves so that you have the tiles mixed up. Show the puzzle at this point. You can take a picture of it or sketch it.Now solve it. How many moves did it take you to do so?In class I presented the following program for computing the 3n+1 function:def threen(value): # compute 3n+1 while value != 1: if value % 2 == 0: value = value//2 else: value = 3 * value + 1 print(int(value))Run it on 87. How many steps did it take to converge? Consider the following nim game:58102538100????????????????????????????????????????????????????????????????????????????????????????????????????????????????????Assume that you are to play next. Show at least one move that will guarantee a win for you (assuming you don’t blow it later). Answer: Take 2 from the rightmost pile. Consider the following graph. Does it contain an Eulerian circuit? Justify your answer. 342709540322546894753543303028950454215534734504552950342582544564303004820241935030511754916805847725447040023126705448302289175603250200787012128502263775112903053022502865755305117524193504235450104775047752002865755476377017513305432425173990030397453803650216027037674553298825523240030162504940300216027045180251797050451802584772545180258128003194050115252517640301058545185737511061702301875207962520320003201670544195025920701960880200787017272002876550129413028987751270000343852563817529349706496052312670590550124587054483011525256146808604253263900555625118935511283953146425440182037484054179570204470020015201784350309372020447002090420226695059690060960043129203783330585597027876501722120511175052463703694430470535027876502090420443865010426703086100422402051562002978150487870541795709779003265170369443030048202349500788670443865020015202222500537972016510004090670195580020015203175000195707016954502852420119380010871201784350335407056515050800011049002242820520700117602052070047720253810000534670014287553911507620000425767538100004200525161925005143507620000417195013335000433197053975639445158750006953252857500413385019050002057400104775004391025142875002085975171450002417445165100514350015240000509079515875043053006667500257175057150002492375114300233362528575002333625857250022574255080Consider the following instance of the Post Correspondence problem. Does it have a solution? If so, show one. iXY1aba2abba3aabaaCan the following tile set tile an arbitrary surface on the plane (following the rules described in class)?19424651257300035934651352550040830514478000 1 2 3In class I presented my simple, not very robust version of the average program:def average(numbers): sum = 0 for num in numbers: sum = sum + num return(sum/len(numbers))Type it in to IDLE. Play with it. Give an example of an input that caused an error. ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download