Exercises¶
Problem 1
This is a continuation of Lab 3 Problem 6.
Consider the sequence of numbers defined through the following iteration:
For example, if \(x_0 = 3\), then the sequence is \((3, 10, 5, 16, 8, 4, 2, 1)\). The Collatz conjecture is the claim that no matter which positive integer is chosen as the starting point \(x_0\), the sequence will always reach \(1\) eventually. No one has proven that this is always the case, but a counterexample has yet to be discovered.
Write a function named collatz_sequence() that accepts a positive integer \(x_0\) and returns a list containing every term of the Collatz sequence \((x_0,x_1,x_2,\ldots,x_n)\), in order, starting at \(x_0\) and ending at \(x_n = 1\), where \(x_n\) is the first occurrence of \(1\) in the sequence.
Reminder: In the even case, use integer division //, not float division /.
Test Cases
print(collatz_sequence(1))
print(collatz_sequence(3))
print(collatz_sequence(27))
[1]
[3, 10, 5, 16, 8, 4, 2, 1]
[27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]
Problem 2
The Fibonacci sequence is defined by the iteration
In other words, after the first two terms, every term in the sequence is the sum of the two terms that immediately precede it.
Write a function named fibonacci() that accepts a positive integer \(n\) and returns a list containing the first \(n\) terms of the Fibonacci sequence, in order.
Test Cases
print(fibonacci(4))
print(fibonacci(14))
print(len(fibonacci(150)))
[1, 1, 2, 3]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
150
Problem 3
For \(0 < x \le 2\), the natural logarithm \(\ln(x)\) can be written as the infinite series
This is called the Taylor series for \(\ln(x)\) centered around \(x = 1\). Although a computer cannot add up infinitely many numbers (it would take infinitely many computations), the sum can be approximated by adding together the first several terms.
Write a function named natural_log() that accepts a number \(x\) and a positive integer \(n\) and returns an estimate for \(\ln(x)\) using the first \(n\) terms of the above series.
That is, compute the number
which will be close to the true value of \(\ln(x)\) if \(x\) is near \(1\).
Test Cases
This test case prints the value of natural_log(x, n) and compares it to NumPy’s np.log(x).
import numpy as np
x = 1.2
for n in [5, 10, 20, 25]:
lnx = natural_log(x, n)
print(lnx, abs(np.log(x) - lnx))
0.18233066666666664 9.109872712048661e-06
0.18232155522031743 1.5736371650199033e-09
0.1823215567939545 8.326672684688674e-17
0.1823215567939546 0.0
As \(n\) increases, the approximation approaches and eventually agrees (up to machine precision) with np.log(x).
Problem 4
If \(a\) and \(b\) are integers, we say that \(a\) divides \(b\) if there exists an integer \(c\) such that \(b = ac\). In other words, \(a\) is a divisor of \(b\), and we write \(a | b\) to mean “\(a\) divides \(b\).”
Implement the following.
A function named
divisors()that accepts a positive integer \(n\) and returns the set of positive integers that are divisors of \(n\) (including 1 and \(n\)).A function named
common_divisors()that accepts two positive integers \(m\) and \(n\) and returns the set of positive integers that are divisors of both \(m\) and \(n\).
Hint: An integer \(a\) is even if \(2 | a\), meaning \(\frac{1}{2}a\) is an integer, that is, \(a \div 2\) has remainder zero. Likewise, \(3|a\) if \(a \div 3\) has remainder zero.
Test Cases
In the following tests, keep in mind that the elements of a set may print in any order.
print(divisors(20))
print(divisors(99))
print(divisors(1829389))
{1, 2, 4, 5, 10, 20}
{1, 33, 3, 99, 9, 11}
{1, 1829389}
print(common_divisors(12, 9))
print(common_divisors(10, 50))
print(common_divisors(108, 36))
{1, 3}
{1, 2, 10, 5}
{1, 2, 3, 4, 36, 6, 9, 12, 18}
Problem 5
A graph is a set of nodes (also called vertices) together with a set of connections between nodes, called edges. In a directed graph, the edges point from one node to another with a specific direction. The following figure shows a directed graph with nodes \(\{A,B,C,D,E\}\) together with the edges \(\{(A,B), (B,C), (C,D), (D,A), (E,C)\}\), in which \((X,Y)\) means there is an edge from node \(X\) to node \(Y\).
A directed graph where each node has exactly one edge leading away from it, such as the graph shown above, is called a functional graph. A dictionary is a natural data structure for representing a functional graph:
Each key in the dictionary defines a node.
Each value in the dictionary is one of the nodes.
Key-value pairs \((X,Y)\) represent an edge from node \(X\) to node \(Y\).
For example, the graph shown above can be represented with the following dictionary.
graph = {"A": "B", "B": "C", "C": "D", "D": "A", "E": "C"}
A path between two nodes \(X\) and \(Y\) is an ordered sequence of nodes that traverses the graph edges from node \(X\) to node \(Y\). In the above graph, the path from node \(A\) to node \(D\) is \((A, B, C, D)\), while the path from \(E\) to \(B\) is \((E,C,D,A,B)\).
Write a function named get_path() that accepts a dictionary representing a functional graph, a starting node \(X\), and an ending node \(Y\).
Return the path from node \(X\) to node \(Y\), including both endpoints, as a list.
Account for the following special cases:
If the starting and ending nodes are the same (\(X = Y\)), return a single-item list [\(\,X\,\)].
If, after leaving the starting node \(X\) but before finding the ending node \(Y\), the path arrives back at a node that is already in the path, then there is no path between \(X\) and \(Y\); return
-1in this case.
You may assume that the starting and ending nodes are both in the graph (keys in the dictionary).
Test Cases
graph = {"A": "B", "B": "C", "C": "D", "D": "A", "E": "C"}
print(get_path(graph, "A", "D"))
print(get_path(graph, "E", "B"))
print(get_path(graph, "C", "C"))
print(get_path(graph, "A", "E"))
['A', 'B', 'C', 'D']
['E', 'C', 'D', 'A', 'B']
['C']
-1
graph = {
"A": "G",
"B": "H",
"C": "B",
"D": "A",
"E": "H",
"F": "H",
"G": "B",
"H": "J",
"I": "E",
"J": "D",
}
print(get_path(graph, "A", "D"))
print(get_path(graph, "E", "B"))
print(get_path(graph, "A", "F"))
['A', 'G', 'B', 'H', 'J', 'D']
['E', 'H', 'J', 'D', 'A', 'G', 'B']
-1
The Collatz sequence from Problem 1 can be thought of as a functional graph by treating \(1\) as a terminal node with a self-loop.
collatz = {
1: 1,
2: 1,
3: 10,
4: 2,
5: 16,
6: 3,
8: 4,
10: 5,
12: 6,
16: 8,
20: 10,
24: 12,
}
print(get_path(collatz, 3, 1))
print(get_path(collatz, 24, 1))
[3, 10, 5, 16, 8, 4, 2, 1]
[24, 12, 6, 3, 10, 5, 16, 8, 4, 2, 1]
Problem 6
Suppose a university collects data from each student about the courses they want to sign up for, and that the data are gathered into a dictionary mapping student names (keys) to the set of their desired courses (values). The university staff must then “invert” the dictionary to find, for each course (new keys), the set of students signing up for that course (new values), called the roster.
Write a function named course_rosters() that accepts a dictionary of student schedules and returns the corresponding dictionary of course rosters.
Hint 1: It is possible to implement this function with dictionary and set comprehensions. However, this may be one case where a comprehension is more trouble than it is worth.
Hint 2: If a particular course is not yet a key in the dictionary of rosters, add it as a key whose value is (initially) an empty set().
Test Cases
In the following tests, keep in mind that the elements of a set may print in any order.
schedules = {
"A": {"X", "Y", "Z"},
"B": {"X", "Y"},
"C": {"Y", "Z"},
}
rosters = course_rosters(schedules)
for key, value in rosters.items():
print(key, value)
Z {'C', 'A'}
X {'A', 'B'}
Y {'C', 'A', 'B'}
schedules = {
"Abby": {"cs580", "math213", "math215", "math290", "phscs530"},
"Bryn": {"math213", "math215", "math290", "stat538", "stat666"},
"Caleb": {"cs580", "math290", "phscs530", "stat538"},
}
rosters = course_rosters(schedules)
for key, value in rosters.items():
print(key, value)
math290 {'Abby', 'Bryn', 'Caleb'}
math215 {'Abby', 'Bryn'}
phscs530 {'Abby', 'Caleb'}
math213 {'Abby', 'Bryn'}
cs580 {'Abby', 'Caleb'}
stat666 {'Bryn'}
stat538 {'Bryn', 'Caleb'}
Problem 7
Let \(S\) be a set. The power set of \(S\) is the new set \(\mathcal{P}(S)\) whose elements are all the subsets of \(S\). In other words, \(A\in \mathcal{P}(S)\) exactly when \(A\subseteq S\). The power set \(\mathcal{P}(S)\) includes the empty set and \(S\) itself. For example, if \(S = \{1, 2, 3\}\), then
Write a function named power_set() that accepts a set \(S\) and returns the power set \(\mathcal{P}(S)\) as a list of sets (sets are not hashable, so we cannot have a set of sets in Python).
Hint: Are subsets most closely related to products, combinations, or permutations?
Test Cases
The subsets may be listed in a different order.
print(power_set(set()))
print(power_set({1, 2}))
print(power_set({1, 2, 3}))
print(len(power_set(set(range(4)))))
[set()]
[set(), {1}, {2}, {1, 2}]
[set(), {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}]
16