In this question, your function will take in a list of integers L
. Some of the integers may appear in the list more than once. The function should return a list of all the integers that appear in the list L
more than once. The returned list should be sorted in increasing order, and must not contain duplicate integers: all integers in the returned list must be unique.
def get_repeating_ints1(L):
'''Return a list of the integers that repeat in L, sorted in
increasing order, with no duplicates.
>>> get_repeating_ints([6, 7, 6, 5, 1, 5, 6])
[5, 6]
>>> get_repeating_ints([1, 2, 3])
[]
'''
res = []
for i in range(len(L)):
if L[i] in L[:i] + L[(i+1):]:
if L[i] not in res:
res.append(L[i])
return sorted(res)
def get_repeating_ints2(L):
'''Return a list of the integers that repeat in L, sorted in
increasing order, with no duplicates.
>>> get_repeating_ints([6, 7, 6, 5, 1, 5, 6])
[5, 6]
>>> get_repeating_ints([1, 2, 3])
[]
'''
counts = {}
for e in L:
if e not in counts:
counts[e] = 1
else:
counts[e] += 1
res = []
for e in counts:
if counts[e] > 1:
res.append(e)
return sorted(res)
Without using Python's sorted
or list.sort
functions, write a function that finds the median of a list of an odd number of float
s. The median of a list L
of length $n$ is a number such that at least $(n+1)/2$ elements of L
are smaller or equal to it, and at least $(n+1)/2$ elements of L
are larger or equal to it. For example, my_median([5.0, 2.0, 4.0, 1.0, 3.0])}
should return 3.0
. There are no restrictions on the runtime complexity of this function.
What is the tight asymptotic bound on the worst-case runtime complexity of the function you wrote in Part (a)? Use Big O notation. You do not need to justify your answer.
def my_median1(L):
for i in range(len(L)):
for j in range(len(L)-1):
if L[j] > L[j+1]:
L[j], L[j+1] = L[j+1], L[j]
return L[len(L)//2]
def my_median2(L):
for e in L:
count_le = 0
count_ge = 0
for e1 in L:
if e1 == e:
count_le += 1
count_ge += 1
elif e1 < e:
count_le += 1
else:
count_ge += 1
if count_le >= (len(L)+1)//2 and count_ge >= (len(L)+1)//2:
return e
Complexity: $\mathcal{O}(n^2)$, where $n = $len(L)
(conceivably could be different for different solutions)
Marking scheme (a)
or
Marking scheme (b)
Santa received a list of gift requests, in the format of a Python list. An example list looks like
requests = ["socks", "calculus textbook", "calculator", "A+ in ESC180", "socks", ...]
Write a function that takes in a list like requests
and returns the 10 most-requested items (i.e., the top 10 items that appear the most often in the list). You can assume that there are no ties in the numbers of times that items are requested. You can assume there are at least 10 different items in the list. The return list should be alphabetically sorted.
def top10requests(requests):
counts = {}
for item in requests:
if item in counts:
counts[item] += 1
else:
counts[item] = 1
items2 = []
for item, count in counts.items():
items2.append((count, item))
items2.sort()
res = []
for i in range(-1, -11, -1):
res.append(items2[i][1])
return sorted(res)
requests = ["socks", "calculus textbook", "calculator", "A+ in ESC180", "socks", "socks", "calculator", "a", "b", "c", "d", "e", "f"]
top10requests(requests)
['A+ in ESC180', 'a', 'b', 'c', 'calculator', 'calculus textbook', 'd', 'e', 'f', 'socks']
Write a function that takes in a list L
, and returns a list that consists of every third element of L
. For example, every_third([5, 6, 7, 12, 0, 4, 6])
should return [7, 4]
. You must use recursion. You must not use global variables, for-loops, while-loops, or list comprehensions.
def every_third1(L):
if len(L) < 2:
return []
return [L[2]] + every_third1(L[3:])
def every_third2(L, i = 0):
if i == len(L):
return []
if i % 3 == 2:
return [L[i]] + every_third2(L, i + 1)
else:
return every_third2(L, i + 1)
def every_third3(L, i = 2):
if i >= len(L):
return []
else:
return [L[i]] + every_third3(L, i + 3)
def every_third4_helper(L, i):
if i >= len(L):
return []
else:
return [L[i]] + every_third4_helper(L, i + 3)
def every_third4(L):
return every_third4_helper(L, 2)
def f(L):
L = ["holidays"]
L = ["happy"]
f(L)
print(L)
['happy']
L = [[[1, 2], 3], [4]]
L1 = []
for sublist in L:
L1.append(sublist[:])
L[0][0][0] = 5
L[0][1] = 5
L[1][0] = 5
print(L)
print(L1)
[[[5, 2], 5], [5]] [[[5, 2], 3], [4]]
def doubler(L):
dL = L
for index in range(len(dL)):
dL[index] = dL[index] * 2
L = [1, 2, 3]
doubler(L)
print(L)
[2, 4, 6]
s1 = "HO HO HO"
s2 = s1
s1 = "Happy Holidays!"
print(s2)
HO HO HO
Marking scheme: usually 0 or 3, with small exceptions.
def power2(n):
if n == 1:
return 2
else:
temp = power2(n-1)
return temp + temp
The call tree looks like
1
|
...
|
n-2
|
n-1
|
n
Each call takes the same amount of time, so the complexity is $\mathcal{O}(n)$.
def f(n):
i, j, sum = 0, 0, 0
while i < n:
while j < i:
sum = sum + j
j += 1
i *= 2
#f(n)
For positive n's, the outer loop runs forever since i starts at 0, and i *= 2
keeps it at 0 forever. If instead i = 1
, we'd observe that the inner loop runs only once, since j is never reset to 0. So we'd be only concerned with the outer loop, which would run for i = 1, 2, 4, 8, ..., n, i.e., about $\log_2{n}$ times.
Possible answer 1: Undefined. Also acceptable: infinite loop, $\mathcal{O}(\infty)$ (which is not strictly speaking defined).
Possible answer 2: $\mathcal{O}(\log{n})$
def g(n):
if n == 0:
return 1
return g(n//2) + g(n//2) + g(n//2)
# g(n)
Here is the call tree:
0 0 0 0 ... ...0
.......
\ | / \ | / \ | /
g(n/2) g(n/2) g(n/2)
\ | /
g(n)
Counting by level, we have 1 call, 3 calls, 9 calls, 27 calls, ....,
In total, we have $\log_2{n}+2$ levels since we go n->n/2->....->0, i.e., $2^{\log_2 (n)}, 2^{\log_2 (n - 1)}, ..., 2^{1}, 2^{0}, 0$
So the total number of calls is $3^0 + 3^1 + 3^2 + ....3^{\log_2(n)+1} = \frac{3^{\log_2(n)+2}-1}{2}$
Now $\frac{3^{\log_2(n)+2}-1}{2} = \frac{3^2 \times 3^{\log_2(n)}-1}{2}$, so the runtime is proportional to $3^{\log_2(n)}$ (note that here we cannot omit the base 2, since raising 3 to a larger power is not just a constant factor).
$y = 3^{\log_2(n)}$
$\log_2(y) = \log_2(n) \log_2 (3)$
$y = 2^{(\log_2(n)\log_2 (3))} = (2^{\log_2 (n)})^{\log_2 (3)} = n^{\log_2 3} \approx n^{1.59}$
Answer: $\mathcal{O}(3^{\log_2(n)})$ or $\mathcal{O}(n^{\log_2(3)})$ or $\mathcal{O}(n^{1.59})$
def h(n):
total = 0.0
for i in range(n):
for j in range(n):
if i == j:
break
#h(n)
The inner loop runs for 1, 2, 3, ..., n times.
$1 + 2 + 3 + ...+ n = \frac{n(n+1)}{2}$, which is $\mathcal{O}(n^2)$
We can use a dictionary to record who is friends with whom by recording the lists of friends in a dictionary. For example:
friends = {"Carl Gauss": ["Isaac Newton", "Gottfried Leibniz", "Charles Babbage"],
"Gottfried Leibniz": ["Carl Gauss"],
"Isaac Newton": ["Carl Gauss", "Charles Babbage"],
"Ada Lovelace": ["Charles Babbage", "Michael Faraday"],
"Charles Babbage": ["Isaac Newton", "Carl Gauss", "Ada Lovelace"],
"Michael Faraday": ["Ada Lovelace"] }
Here, Carl Gauss is friends with Isaac Newton, Gottfried Leibniz, and Charles Babbage. Assume that friendships are symmetric, so that if X is friends with Y, then it's guaranteed that Y is friends with X.
A friendship chain is a chain of people who are connected by friendship, with no repetitions allowed. For example, the following is a friendship chain of length 5:
Carl Gauss $\rightarrow$ Isaac Newton $\rightarrow$ Charles Babbage $\rightarrow$ Ada Lovelace $\rightarrow$ Michael Faraday
Write a function which takes in a dictionary in the format above, and returns the length of the longest friendship chain in the data in the dictionary.
def all_combinations(elems, n, start_list = []):
if n == 0:
return [start_list]
all_combs = []
for i in range(len(elems)):
all_combs.extend(all_combinations(elems[:i]+elems[(i+1):], n-1, start_list + [elems[i]]))
return all_combs
def valid_friendship_path(path, friends):
for i in range(len(path)-1):
if path[i+1] not in friends[path[i]]:
return False
return True
def longest_path(friends):
for path_length in range(len(friends)+1, -1, -1):
paths = all_combinations(list(friends.keys()), path_length)
for path in paths:
if valid_friendship_path(path, friends):
print(path)
return path_length
return 0
# Another option, using ideas outside fo ESC180:
def longest_friendship_chain(friends):
# Define a helper function to find the longest chain of friends starting from a given person
def longest_chain(person, visited):
# Base case: if the person has no friends, return 1 (since the person is part of the chain)
if person not in friends:
return 1
# Initialize the maximum chain length to 0
max_chain = 0
# Iterate over the person's friends
for friend in friends[person]:
# If the friend has not been visited yet, find the longest chain starting from the friend
if friend not in visited:
visited.add(friend)
max_chain = max(max_chain, longest_chain(friend, visited))
# Return the maximum chain length plus 1 (to account for the person themselves)
return max_chain + 1
# Initialize the maximum chain length to 0
max_chain = 0
# Iterate over all the people in the dictionary
for person in friends:
# Find the longest chain starting from the person
visited = set()
max_chain = max(max_chain, longest_chain(person, visited))
return max_chain
friends = {"Carl Gauss": ["Isaac Newton", "Gottfried Leibniz", "Charles Babbage"],
"Gottfried Leibniz": ["Carl Gauss"],
"Isaac Newton": ["Carl Gauss", "Charles Babbage"],
"Ada Lovelace": ["Charles Babbage", "Michael Faraday"],
"Charles Babbage": ["Isaac Newton", "Carl Gauss", "Ada Lovelace"],
"Michael Faraday": ["Ada Lovelace"] }
print(longest_path(friends))
print(longest_friendship_chain(friends))
['Gottfried Leibniz', 'Carl Gauss', 'Isaac Newton', 'Charles Babbage', 'Ada Lovelace', 'Michael Faraday'] 6 6
friends = {"Carl Gauss": ["Isaac Newton", "Gottfried Leibniz", "Charles Babbage"],
"Gottfried Leibniz": ["Carl Gauss"],
"Isaac Newton": ["Carl Gauss", "Charles Babbage"],
"Ada Lovelace": ["Michael Faraday"],
"Charles Babbage": ["Isaac Newton", "Carl Gauss"],
"Michael Faraday": ["Ada Lovelace"] }
print(longest_path(friends))
print(longest_friendship_chain(friends))
['Gottfried Leibniz', 'Carl Gauss', 'Isaac Newton', 'Charles Babbage'] 4 4
(For the hypothesize + verify version)