Python代写：ANLY550ArithmeticProblem

代写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.

1. 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.
2. 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.
3. 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).
4. 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.
5. 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.
6. 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.
7. We found that a recurrence describing the number of comparison operations for a mergesort is T(n) = 2T(n/2) + n - 1 in 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 is T(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?
8. 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.