Write python function that get's a list as an input and the median of its values. Median is the middle number when you sort the list. If the list has even number of elements, median will be the average of the two numbers in the middle

Example: median of [5, 4, 8, 2, 9, 1, 3] is 4 and median of [4, 5, 2, 1, 8, 9]is (4+5)/2 or 4.5.
can use python's own sorting algorithm.

def find_median(lst):

Q2.

Write python function that gets n and returns the nth value in the Pell sequence. Pell sequence is defined by
P(n) = 2*P(n-1) + P(n-2) while P(0) = 0 and P(1) = 1. Use your code to generate and provide the first 10 values of Pell sequence.

def pell(n):
 

Section 2 - function Analysis (30 marks)

Q3.

Run an analysis of the function developed in Q2 and find its T(n) and big O perforamance. Is finding the nth element of Pell sequence faster than bubble sort? Is it faster than finding the nth element of the Fibonacci series?

Q4.

What is the T(n) and big O performance of the following function? This function gets a value as an input and prints all prime numbers between 1 and the input number. Math.sqrt takes the square root of a number

import math

def print_all_primes(n):

   for num in range(1,n + 1):

       isPrime = True

       for i in range(2,int(1+math.sqrt(num))):

           if num % i ==0 :

               isPrime = False

               break

       if isPrime:

           print(num)

 

Which one is faster? sorting a list of size n or to printing all prime numbers up to n? Answer based on both bubble sort and merge sort.

 

Q5.

Assume that that after analysizng a recursive function to find it's T(n) you find that

T(n) = 1 + 2 * T(n/4)

What is the big O performance of this function? Is it faster or slower than binay search? Is it faster or slowe than merge sort?

Hint: a ^ ( log x in base a^k) = x^(1/k)

 

Section 3 - Linked Lists (30 marks)

Q6.

What are advantages and disadvantages of using singly linked lists vs. doubly linked lists? Please elaborate

 

Q7.

Assume that a linked list is declared as follows:

class LList:
   class Node:
       def __init__(self, data, next=None):
           self.data = data
           self.next = next

   def __init__(self):
       self.front = None
       self.back = None

 

Develop a two cloning function:

   def clone_range_index(self, myLList, i , j):
   def clone_range (self, myLList, min , max):
 

that gets a linked list myLList and builds the linked list based on the given myLList by:

clone_range_index: copying over the ith, (i+1)th, (i+2)th , ..., jth element of myLList into the new list (starting at index 1). If i=1, and j=len(myLList) the new linked list will be identical to myLList.

clone_range : copying over all elements of myLlist that are larger or equal to min and smaller or equal to max

Hint: You can first implement a simple insert function for your linked list that gets a node (or data) and insets it in the list. Then in the clone_rangefunction, iterate the given myLList and one by one insert the qualified data into

 

Section 4 - Tables (20 marks) 

Q8. Implementing a double hashed table

 

Consider the following double hash function:

hash1(key) = key % 11
hash2(key) = 7 - (key % 7)

Assume that the table of length 11 is already partially populated as

Index	Key	Value
0	11	Apple
1
2	13	Banana
3	25	Cherry
4
5
6	22	Date
7
8
9	39	Elderberry
10	21	Fig

 

Using the double hash functions above, do the following two insertions

Insert(Key = 0, value = Plum)
Insert(Key = 9, value = Strawberry)