This is an list of homework assignments for grading. The deadline is February 28th. The minimal requirement to pass the course is the preparation of at least 2 working solutions. To get a 'good' or 'excellent' grade, you need 3, resp. 4 working programs from below.

It is also possible to bring your own problem to work on. This might be related to a math/cs course at your university, your thesis work etc. In this case, I will ask you to consult me so that I can make the problem into a valid homework assignment. To send me the solutions / ask questions, my address is: "".join(["bfhieelu.un.@tpe"[7*j % 16] for j in range(16)])


Various programming using some SageMath fetures



NUMBER PUZZLE

Write a function that has a list with four (not necessarily distinct) integers and a 5th number, called the goal as input. The function should determine whether it is possible to get the goal as a result of a calculation involving all 4 numbers in the list, parenthesis and operations +, -, *, /. The order in the list is irrelevant. For example, from the list [3, 3, 5, 5], you get 34 e.g. by (3*3) + (5*5). In contrast, from the list [1, 2, 3, 4] you can not get 1000. Another test case is [3, 3, 8, 8] and 24, here the answer is yes (a good exercise to find it by hand).

CHOMP

Write a function that determines whether a position in a game of chomp of size 6x6 is a winning position or not. Don't hesitate to look up the game of chomp and how wining and losing positions can be identified in a finite game.

NUMBERS ON A BOARD

We play the following: initially there are up to 30 15 [problem updated due to unintended level of difficulty] integers written on the blackboard. In each step, we select two numbers, erase them both and write the absolute value of their difference back on the board. The game finishes when there is only one number left on the board. Determine all numbers that can be the output of the game for a given initial list.

PREFIX NORMAL STRINGS

A string of length n consisting entirely of 0s and 1s is called prefix normal if for each number k with 1≤ k ≤ n, the prefix of length k contains at least as many 1s as any other contiguous substring of length k. (A non-empty prefix of a string is a substring that contains the starting character.) Write a function that checks prefix-normality of strings, and counts the number of prefix normal strings of length n up to 23.

RANDOM GRAPH

Let n be a positive integer parameter, and p be a real number from the open interval (0, 1). Create a simple undirected graph on n vertices, and for each pair of vertices, create an edge between the pair with probabilty p (make the choice for edges independently and randomly). You obtain a random graph. Determine the number of components, the size of the largest component and the largest eigenvalue of the graph's adjacency matrix. Repeat the experiment with the same parameters and make a histogram of the calculated values (how often does the maximal component's size fall in this and this interval etc.). Also play with parameter p for fixed n, and plot how the calculated properties of the graph (take an average of several experiments for each p) change as a function of p.

RANDOM MATRIX

Let n be a fixed positive integer in the interval [5, 20]. Create an n-by-n matrix with elements chosen independently randomly from the same probability distribution. Calculate the determinant and the largest absolute value among the eigenvalues. Make 1000 experiments and make a plot of the observed empirical distribution of the two quantities. Repeat the experiment for the uniform distribution in [0, 1], the uniform distribution in [-1, 1], a normal distribution and 2 others. Find statistical methods for comparing the distribution of the determinant for the uniform and the normal distribution.

NUMBER OF DIVISORS

Given a positive integer n, SageMath can calculate the number of positive divisors of n easily from the prime factorization of n (there is a function for that). Finding a number n that has exactly a prescribed number t of divisors is not so difficult either: e.g. 2^t-1 has t divisors. Finding the smallest positive integer n with exactly t divisors can be tricky, and probably does not have a very nice mathematical characterization in general (it does for prime t and some other special values). Write a Sage program that finds the minimal such n. A few test cases: 16 is the smallest number with 5 divisors, 60 is the smallest with 12 divisors and neither 2³¹ nor 2*3*5*7*11 are smallest with exactly 32 divisors. The program should work for values of t up to 1000.

GENERALIZED CRT

The chinese remainder theorem states that the set of congruences
a₁ x ≡ b₁  (mod m₁)
a₂ x ≡ b₂  (mod m₂)
...
a_n x ≡ b_n  (mod m_n)
always has a simultaneous solution in the integers whenever the moduli are pairwise relatively prime and the a_i are all 1, moreover the solutions form exactly one residue class modulo the product of the m_i. Write a function that takes a system of arbitrary congruences (maybe without the relative primality conditions) and checks whether the system has solutions or not and gives the solutions if they exist as a residue class modulo some integer. Hint: check compatibility of congruences by taking the gcd of moduli: e.g. if we know x ≡ 3 (mod 6) and x ≡ 4 (mod 10), then by looking at x modulo the gcd of 6 and 10, i.e. 2, it would have to be both odd and even, which is impossible.



Some plot-related assignments:



BUFFON

Buffon's needle problem models the following experiment. We drop n needles of length l onto a plane onto which infinitely many parallel lines are drawn at distance d from each other. We assume that l < d. We assume that the both the position where the needle lands and the angle at which it points is random. It is known that the probability of a needle hitting some line is 2l/dπ. Make a function that performs the experiment with the specified parameters and calculates the observed frequency of needles hitting a line. Also make a drawing with different colors assigned to lucky and unlucky needles. Look up Buffon's needle drop experiment for details.

RANDOM WALK

Illustrate a 2-dimensional random walk by making a plot from arrows displaying a path of length n, starting from the origin and in each step moving left, right, up or down with equal probability. Count the number of times you reached the origin, list the positions furthest away from the origin, the longest interval of time away from the origin, and 2 other statistics you like. Make a plot of these values as you change n.

CHARGES ON A SPHERE

Let n be a positive integer up to 10. Imagine a unit sphere in 3 dimensions with n equal positive charges placed on the surface of the sphere. The motion of the charges is constrained: they cannot leave the surface of the square in either direction. Simulate their movement if the forces between them obey an inverse square law (and they repel each other). Prepare an animation or an interactive 3D plot of the motion using SageMath's functionality for numerically solving differential equations. Plot the position of the charges they settle in (if they do).