Tutor profile: Athanasios G.

Write a function which takes in an input n and generates a diamond pattern composed of numbers ranging from 1 to n ex: diamonds(1) -> 1 1 ex: diamonds(5) -> 1 2 2 3 3 4 4 5 5 5 5 4 4 3 3 2 2 1

def diamonds(n): newnum = n j = 0 if newnum == 1: print(1) else: print((newnum - 1)*" "+str(1)) for i in range(2, newnum+1): print(((newnum - 2)*" ")+str(i)+(2 * i - 3)*" "+str(i)) newnum -= 1 if n == 1: print(1) else: for i in range(n, 1,-1): print(j*" "+str(i)+(2 * i - 3)*" "+str(i)) j += 1 print((n - 1)*" "+str(1)) return

Given below is a partially implemented program for a HashMap class with a quadratic probing collision resolution strategy. Without importing any libraries, creating new instance variables (local variables are allowed), or writing any helper methods, implement the remove() method which removes an entry from the hashmap. Since quadratic probing is an open addressing scheme, removed entries should not be set to null; removed entries should be flagged using their removed field. The code to be implemented must be as efficient as possible. public class HashMap<K, V> { private class MapEntry<K, V> { K key; V value; boolean removed; public MapEntry(K key, V value) { this.key = key; this.value = value; } } private MapEntry<K, V>[] table; private int size; public HashMap(int initialCapacity) { table = (MapEntry<K, V>[]) new MapEntry[initialCapacity]; size = 0; } // Implementation omitted public V remove(K key) { // TODO Auto-generated method stub } }

/** * Remove a MapEntry from the backing table with the given key * * @param key the key to be removed * @throws java.util.NoSuchElementException if the key does not exist or has been removed * @throws java.util.IllegalArgumentException if the key is null * @return value the value previously associated with the key */ public V remove(K key) { if (key == null) { throw new java.util.IllegalArgumentException("Key is null"); } int index = Math.abs(key.hashCode() % table.length); boolean terminate = false; for (int i = 0; i < table.length && !terminate; i++) { int curr = (index + (int) (Math.pow(i, 2))) % table.length; if (table[curr] == null || (table[curr].key.equals(key) && table[curr].removed) { terminate = true; } else if (!table[curr].removed && table[curr].key.equals(key)) { size--; table[curr].removed = true; return table[curr].value; } } throw new java.util.NoSuchElementException("Key is not in hashmap"); }

The Fibonacci sequence frequently occurs in areas such as mathematics, computer science and finance. It is defined by the linear homogenous recurrence equation: Fn = Fn-1 + Fn-2 where F0 = 0, F1 = 1 Suppose that T(n) represents the time complexity to calculate the n-th element of the sequence. Prove that Fn is 𝚯(2n).

Start with T(n) = T(n - 1) + T(n - 2) Rearrange to obtain: T(n) - T(n - 1) - T(n - 2) = 0 Substitute rn for T(n) to obtain the characteristic polynomial: rn- rn-1-rn-2=0 Divide both sides by rn-2: r2 - r - 1 = 0 Use the quadratic formula to solve for the roots: r1 = (1 + √(5))/2, r2= (1 - √(5))/2 Represent the sequence as a linear combination: T(n) = C1 * r1n + C2 * r2n Solve for C1 and C2: T(0)=0=C *r 0+C *r 0=C +C 112212 Therefore C1 = -C2 T(1) = 1 = C1 * r11 + C2 * r21 = C1 * r1 + C2 * r2 Substitute the two roots into the linear combination for T(1): 1 = -C2 * (1 + √(5))/2 + C2 * (1 - √(5))/2 Solve for C1 and C2: C1 = -1/√(5), C2 = 1/√(5) Therefore T(n) = -1/√(5) * ((1 + √(5))/2)n + 1/√(5) * ((1 - √(5))/2)n This factors as (1/√(5))(-((1 + √(5))/2)n + ((1 - √(5))/2)n) A function f(n) is defined as 𝚯(g(n)) iff: limn—>+∞ f(n) / g(n) = c ∈ R Compute limn—>+∞ T(n) / 2n: limn—>+∞ T(n) / 2n = limn—>+∞ (1/√(5))(-((1 + √(5))/2)n + ((1 - √(5))/2)n) / 2n = (1/√(5)) limn—>+∞ (-((1 + √(5))/2)n + ((1 - √(5))/2)n) / 2n = (1/√(5)) (limn—>+∞ -((1 + √(5))/2)n / 2n + limn—>+∞ ((1 - √(5))/2)n) / 2n) = (1/√(5)) ((-1) limn—>+∞ ((1 + √(5))/2)n / 2n + limn—>+∞ (-1)n((√(5) - 1)/2)n) / 2n) Continue; use the series convergence definition for limit involving the term (-1)n: = (1/√(5)) ((-1) * 0 + 0) = 0 Since limn—>+∞ T(n) / 2n = c ∈R ⇒ T(n) = 𝚯(2n), and 0 ∈R, then T(n) must be 𝚯(2n) Therefore Fn is shown to be 𝚯(2n). ■