代写Python的算术作业，实现表达式，比较各自的时间复杂度。
Requirement
Homework will be due at the BEGINNING of class on the date due. Your answers should be written legibly if handwritten and your name should be clearly written on your homework assignment. Try to make your answers as clear and concise as possible; style will count in your overall mark. Be sure to read and know the collaboration policy in the course syllabus.
Assignments are expected to be turned in electronically. A single zip file should be submitted containing a) a writeup in pdf format and b) any Python programs that you are asked to provide. If you do assignments by hand, you will need to scan in your results to turn them in. Instructions for how to electronically submit assignments will be given in class and on the class website.
For all homework problems where you are asked to give an algorithm, you must prove the correctness of your algorithm and establish the best upper bound that you can give for the running time. You should always write a clear informal description of your algorithm in English. You may also write pseudocode if you feel your informal explanation requires more precision and detail, but keep in mind pseudocode does NOT substitute for an explanation. Again, try to make your answers as clear and concise as possible.
- In Python, implement the three different methods (recursive, iterative, and matrix) for computing the Fibonacci numbers discussed in lecture (see Mitzenmacher’s lecture notes linked to on the course website for reference). Please call these programs recursive.py, iterative.py, and matrix.py respectively.
Make sure you are computing the numbers exactly (no floating point arithmetic). How far does each process get after one minute of machine time? You will need to figure out how to time processes on the system you are using, if you do not already know.
To help ascertain how much of the runtime is due to the complexity of multiplying large integers, modify your programs so that they return the Fibonacci numbers modulo 65536 = 216 . (In other words, make all of your arithmetic modulo 216 ). For each method, what is the largest Fibonacci number you can compute in one minute of machine time?
Submit your source code with your assignment. Please give a reasonable English explanation of your experience with your programs. - Indicate for each pair of expressions (A, B) in the table below the relationship between A and B.
Your answer should be in the form of a table with a “yes” or “no” written in each box. For example, if A is O(B), then you should put a “yes” in the first box. - For all of the problems below, when asked to give an example, you should give a function mapping positive integers to positive integers. (No cheating with 0’s!)
- Find (with proof) a function f1 such that f1(2n) is O(f1(n)).
- Find (with proof) a function f2 such that f2(2n) is not O(f2(n)).
- Prove that if f(n) is O(g(n)), and g(n) is O(h(n)), then f(n) is O(h(n)).
- Give a proof or a counterexample: if f is not O(g), then g is O(f).
- Give a proof or a counterexample: if f is O(g), then f is O(g).
- Buffy and Willow are facing an evil demon named Stooge, living inside Willow’s computer. In an effort to slow the Scooby Gang’s computing power to a crawl, the demon has replaced Willow’s hand-designed super-fast sorting routine with the following recursive sorting algorithm, known as StoogeSort. For simplicity, we think of Stoogesort as running on a list of distinct numbers. StoogeSort runs in three phases. In the first phase, the first 2/3 of the list is (recursively) sorted. In the second phase, the final 2/3 of the list is (recursively) sorted. Finally, in the third phase, the first 2/3 of the list is (recursively) sorted again.
Willow notices some sluggishness in her system, but doesn’t notice any errors from the sorting routine. This is because StoogeSort correctly sorts. For the first part of your problem, prove rigorously that StoogeSort correctly sorts. (Note: in your proof you should also explain clearly and carefully what the algorithm should do and why it works even if the number of items to be sorted is not divisible by 3. You may assume all numbers to be sorted are distinct.) But StoogeSort can be slow. Derive a recurrence describing its running time, and use the recurrence to bound the asymptotic running time of Stoogesort. - Solve the following recurrences exactly, and then prove your solutions are correct by induction. (Hint: Graph values and guess the form of a solution: then prove that your guess is correct.)
- T(1) = 1, T(n) = T(n - 1) + 3n - 3.
- T(1) = 1, T(n) = 2T(n - 1) + 2n - 1.
- Give asymptotic bounds for T (n) in each of the following recurrences. Hint: You may have to change variables somehow in the last one.
- T(n) = 4T(n/2) + n^3.
- T(n) = 17T(n/4) + n^2.
- T(n) = 9T(n/3) + n^2.
- T(n) = T(sqrt(n)) + 1.
- We found that a recurrence describing the number of comparison operations for a mergesort is
T(n) = 2T(n/2) + n - 1in the case where n is a power of 2. (Here T(1) = 0 and T(2) = 1.) When n is not a power of 2, the correct recurrence isT(n) = T([n/2]) + T([n/2]) + n - 1.
Exactly solve for T(n) in this case, and prove your solution is true by induction. Hint: plot the first several values of T(n), graphically. What do you find? - Implement Merge Sort in Python and turn in your source code (please call your program mergesort.py). The implementation should read a comma-separated list of numbers from stdin, sort the list, and print out the result. You may assume the length of the list is a power of two.