python算法代写 FIT5211 assignment 1

数据结构算法代写代考 data structure algorithm / Python代写代考

Instructions

  • You must work on this assignment individually. We check for similarities and find collusion cases every semester. You’ve been warned!
  • This assignment contributes 20% towards your final mark in FIT5211.
  • The subjects are computational complexity, recursion, divide-and-conquer and search.
  • The exercises are roughly given by increasing difficulty. Obtaining a 100% mark may be very hard, depending on your background, and will probably take many hours. The assignment is written such that everyone can correctly complete the first exercises, but it is likely that the last ones will only be succesfully completed by few.
  • We provide tests. A program will not receive full marks if it does not pass all tests. A program which passes all tests may still be incorrect, and thus may not receive full marks either. You may write and run additional tests.
  • The expected deliverable is this Jupyter Notebook, completed with your answers.
  • For questions on this assigment, please use the Moodle forum.
  • The deadline is September 14, 23:55, submission via Moodle. If this does not work, and only in this case, send your Notebook to pierre.lebodic@monash.edu.
  • The late penalty is 10 marks (deducted from your original mark) per late day.
  • Have fun!

Exercise 1: Recursive sequence (10%)

We have previously worked on the famous Fibonacci sequence: https://en.wikipedia.org/wiki/Fibonacci_number.
In this exercise we define a similar recursive sequence: Fn=2Fn−2+Fn−3.
The initial values of the sequence are defined as:
F0=3,
F1=5,
F2=8.
We ask that you write a recursive function which computes Fn (if n is a non-negative integer) using a Python list l for memoisation. Please use exactly the prototype given below. Iterative functions and recursive functions without memoisation will not be accepted.

In [ ]:
def F(n, l = None):
    if l == None:
    #............

Here we provide some values of F in the assertions below for you to check the correctness of your code:

In [ ]:




















values = {0:3, 2:8, 5:34, 10:377, 15:4181, 20:46368, 25:514229, 30:5702887}


for i, f in values.items():


    assert F(i) == f, \


        "The function computed F({}) = {} instead of {}" \


        .format(i, F(i), f)




































Remark: if the tests above fail because the maximum recursion depth has been exceeded, your use of the list l for memoisation may be incorrect.










Exercise 2: Recursive approximation (20%)
















Write a recursive algorithm that computes an approximation of the logarithm of a real number x≥1 in a given integer base b≥2 using n steps. You can only use the operations +,−,∗,/,∗∗ (therefore not the log function). The function will recursively compute an interval [l,u] to which log(x) belongs. Please use exactly the prototype below. In this prototype,


    

  • n indicates the number of steps (or recursive calls),
    • 

  • x the number for which to compute the logarithm,
    • 

  • b the base of the logarithm,
    • 

  • l a proven lower bound of the logarithm,
    • 

  • u a proven upper bound of the logarithm.
    • 













In [ ]:


































def recursivelog(n, x, b, l=None, u=None):


    assert( n >= 0)


    assert( x >= 1)


    assert( isinstance(b, int) )


    assert( b >= 2 )


    #............




































Use the cell below for small tests:












In [ ]:


































print(recursivelog(100, 4, 2))


print(recursivelog(100, 10, 10))




































We test the results below using the function “isclose” (see https://docs.python.org/3/library/math.html#math.isclose ).












In [ ]:


































import math


import random


random.seed(0)


n = 100


ntest = 10


​


for b in range(2, 11):


    for _ in range(ntest):


        x = random.uniform(1, 10^6)


        mylog = recursivelog(n, x, b)


        mathlog = math.log(x, b)


assert math.isclose(mylog, mathlog, abs_tol=0.00001), "for x={0} and b={1}, mylog={2} is not close enough to mathlog={3}".format(x, b, mylog, mathlog)











Exercise 3: Search for a pair of integers in a list (25%)
















You are given a list L=[(a1,b1),…,(an,bn)] of n pairs of integers. For any two pairs (ai,bi)∈L and (aj,bj)∈L such that 1≤i≤j≤n, we have (at least) one of three cases:


    

  • ai=aj and bi=bj
    • 

  • ai<aj
    • 

  • bi<bj
    • 



For example, the list L=[(1,2),(1,1)] would not be valid. An example of a valid list is












In [ ]:


































L = [(0,1), (1, 0), (0, 1), (1, 1), (1, 2), (3, 1), (3, 1), (2, 2), (2, 3), (3, 2), (2, 3), (4, 3), (3, 4), (4, 4), (4, 5), (5, 5)]










Question 3.1 (5%):


Suppose I know the middle pair (a,b) of the non-empty list L, and I am looking for the pair (x,y).


In what case(s), if any, can I stop the search?
















(type your answer here)
















In what case(s), if any, can I determine that (x,y) cannot be found in some part of L? Can this speed-up the search?
















(type your answer here)
















Question 3.2 (15%)


Write a recursive function that applies the divide-and-conquer paradigm to search if a given pair of values (x,y) is in L. The prototype of the function should be exactly as follows:












In [ ]:


































def pair_search(l, p):


    found = False


    calls = 1


    #............


    return found, calls




































The function returns a boolean to indicate whether the pair p was found in l, and an integer calls to indicate the number of calls that were made to pair_search to obtain the answer.
















Test your function with the code below.












In [ ]:


































for item in L + [(0, 0), (2, 1), (3, 3), (5, 4)]:


    found, calls = pair_search(L, item)


    iteminl = item in L


    assert found == iteminl, "Found item {} {} time(s) instead of {}".format(item, int(found), int(iteminl))


    print("Found {} {} time(s) in {} calls".format(item, int(iteminl), calls))




































Question 3.3 (5%)


What is the worst-case O() complexity of the function you wrote? Prove your answer.
















(type your answer here)






















Exercise 4: Maximising sublist (25%)
















Given a list L=[x1,…,xn] of n non-negative integers, we are interested in sublists S of L that satisfy


    

  • for all i∈{1,…,n−1},xi∈S implies xi+1∉S,
    • 

  • for all i∈{2,…,n},xi∈S implies xi−1∉S.
    • 



In other words, two items that are adjacent in the list cannot both be picked in the sublist S.
















For simplicity, we suppose that the input list L does not contain repeated values, i.e. ∀i,j∈{1,…,n},i≠j,xi≠xj.
















Question 4.1 (20%)


Write a divide-and-conquer program that outputs a sublist S that maximises ∑x∈Sx, the sum of its elements. For instance, if












In [ ]:


































L = [1, 0, 5, 3, 2, 7, 9, 15, 6, 4, 13]




































then a sublist with maximum sum is












In [ ]:


































 S = [1, 5, 7, 15, 13]




































Write the function below using exactly this prototype:












In [ ]:


































def bestsublist(l):


    sublist = []


    #..............


    return sublist




































Test your code below:












In [ ]:


































assert sum(bestsublist([])) == 0
































In [ ]:












Question 4.2 (5%)


Give the O() complexity of the function you wrote.
















(type your answer here)
















Is there an algorithm that does not use the divide-and-conquer paradigm to answer Question 1 and that has a better O() complexity? Prove your answer.
















(type your answer here)
















Exercise 5: Dominant primes (20%)
















Given a positive integer x and its decimal notation dndn−1…d1d0 (di corresponds to a digit), we say x is a dominant prime if and only if:


    

  • x is prime,
    • 

  • for any index k∈{0,…,n},dk…d0 is prime,
    • 

  • for any digit dn+1∈{1,…,9}, dn+1dn…d0 is not prime.
    • 



For example:


    

  • 2 is a dominant prime, as it is prime, and any number ending by 2 is divisible by 2, and therefore not prime.
    • 

  • 3 is not a dominant prime, since 13 is prime.
    • 

  • 7937 is also a dominant prime, as 7937, 937, 37 and 7 are prime, and 17937, 27937, 37937, 47937, 57937, 67937, 77937, 87937, 97937 are not prime.
    • 

















Question 5.1 (15%)


Write a recursive algorithm which enumerates dominant primes. Your algorithm should print dominant primes as it finds them (rather than at the end).


We provide a simple function to test prime numbers. You may choose not to use it.












Write your algorithm below. By default we limit the dominant primes we are looking for to a maximum value of 1012. Note that it means that you may not be able to determine if some numbers are dominant primes. In this case, don’t print them. With maxprime=1012, the expected run time should be around or less than a minute. Performance will be taken into account in the mark. Furthermore, your function (or any part of your code) should:


    

  • not store hard-coded/precomputed primes,
    • 

  • not use more than constant-size memory (i.e. it should be independent of the input),
    • 

  • not necessarily print the numbers in any particular order.
    • 













In [ ]:


































def dominant_prime_finder(maxprime=10**12):


    #TODO




































Question 5.2 (5%)


Find and write below a dominant prime with exactly 20 digit.
















(type your answer here)












































































		
		
			




	




	        
 
 Related Posts