{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Software projects\n", "## Formalities\n", "* Projects can be worked on in groups of **one up to three students**. \n", "* Below I give a **list of proposals for topics** of the project. You can either choose to work on one of those (and it's ok if multiple groups work on the same project). Alternatively, **if you have some project idea yourself**, write me a short email describing the idea and we can discuss whether it is suitable.\n", "* Concerning the size of the project: it should be big enough to allow you to show what you learned in the course. You can try to aim at investing between **4 and 10 hours of work**. For the projects I propose below, it will be enough if you implement most of the functions that I propose (but you are invited to program more or other functions). If you are unsure whether your project is big (or small) enough, you can always ask.\n", "* In the last lectures of the course we will learn about some **basic best practices** concerning programming (in particular concerning coding style, documentation, tests etc.). Your project should follow these best practices.\n", "* Deadline for handing in the projects is the **3rd of July**. Please send me an email with all relevant files, a short description what your project does and the list of participants of the project." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Proposals" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Triangles in the plane\n", "Write a class ``Triangle`` that implements triangles in $\\mathbb{R}^2$. A list of possible functions:\n", "* computing the area, circumference or center of mass\n", "* plotting the triangle\n", "* checking whether two triangles are congruent or similar\n", "* creating a triangle with given set of angles/length of edges/some combination of lengths and angles\n", "* checking containment of a point of $\\mathbb{R}^2$ in the triangle\n", "* checking whether the triangle is equilateral or isosceles\n", "\n", "**Further possibilities**\n", "* computing the [incircle and excircle](https://en.wikipedia.org/wiki/Incircle_and_excircles_of_a_triangle)\n", "* integrating a function $f(x,y)$ over the triangle" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Curve sketching\n", "Part of many calculus classes (even in highschool) is learning about [curve sketching](https://en.wikipedia.org/wiki/Curve_sketching) (German: Kurvendiskussion).\n", "Write some code for analyzing a function $f : I \\to \\mathbb{R}$ on an interval $I \\subseteq \\mathbb{R}$ which is given by a symbolic expression. In particular, it should be possible to find\n", "* zeros, extreme values and inflection points\n", "* derivatives and integrals\n", "* the tangent at a point\n", "* asymptotes\n", "\n", "and of course to plot the function (maybe enhanced with markings at the zeros, maxima, minima, etc with labels giving their coordinates, plots of the asymptotes decorated with their equations, ...). \n", "\n", "*Note:* Of course in full generality, the tasks above are extremely hard (e.g. to find zeros of an arbitrary polynomial, etc). The code should work with typical examples that could appear in exercises." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Countdown\n", "The British game show [Countdown]() features a [number game](https://en.wikipedia.org/wiki/Countdown_(game_show)#Numbers_round). The basic idea is that given six random numbers and a random 3-digit target number, the contestants should combine the six numbers using the operations ``+,-,*,/`` to obtain a number as close as possible to the target. See a video clip [here](https://youtu.be/V_4L8ZGmEa0?t=252) and see the wikipedia page for the precise rules.\n", "\n", "Implement both a function for producing a game (i.e. the six + one numbers above), as well as for finding the best solution(s) to a given game." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Automorphism groups of polytopes\n", "A *polytope* $P$ is the convex hull of finitely many points in $\\mathbb{R}^n$. We say that $P$ is *full dimensional* if there does not exist a proper affine subspace of $\\mathbb{R}^n$ containing $P$. A (linear) *automorphism* (or *symmetry*) of $P$ is an [affine transformation](https://en.wikipedia.org/wiki/Affine_transformation#Representation) which sends the polytope to itself. Often one does not allow arbitrary affine transformations, but restricts to [rigid transformations](https://en.wikipedia.org/wiki/Rigid_transformation) (which only allow rotations, reflections and translations) or even proper rigid transformations (which only allow rotations and translations).\n", "\n", "In this project, the goal is to write a function ``polytope_symmetries`` which takes the set of vertices of a polytope and computes its symmetry group. Optional parameters should allow to specify the type of transformations that are allowed (linear, rigid or proper rigid), and the output format (as a permutation group or [matrix group](https://doc.sagemath.org/html/en/reference/groups/sage/groups/matrix_gps/finitely_generated.html)).\n", "\n", "*Hints about the algorithm* (uncomment to see)
\n", "\n", "\n", "In SageMath, the function ``Polyhedron.restricted_automorphism_group`` computes the group of linear automorphisms, using non-trivial mathematics. You can use this to check your own program. In particular, try to match the [number of symmetries of the platonic solids](http://www-groups.mcs.st-andrews.ac.uk/~john/geometry/Lectures/L10.html):" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "120" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "I=polytopes.icosahedron()\n", "G = I.restricted_automorphism_group()\n", "G.order()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Multivariate interpolation\n", "For an infinite field $K$, a polynomial $f \\in K[x]$ of degree $d$ is uniquely determined by its values at $d+1$ points (see [here](https://en.wikipedia.org/wiki/Lagrange_polynomial)). This can be generalized to polynomials in multiple variables: if you know $f \\in K[x_1, \\ldots, x_n]$ at sufficiently many points, you can uniquely reconstruct it. In this project, you would write a function ``multivariate_interpolate`` which does this reconstruction.\n", "\n", "Inputs could either be lists ``points, values`` of the evaluation points and the values of $f$, or a function ``F`` which can be evaluated at concrete points $(x_1, \\ldots, x_n)$. Also, the bound on the degree of $f$ could be specified either as a bound on the total degree, or as a vector of length $n$ with bounds on the degree in each variable $x_i$. \n", "\n", "Further possible optional arguments:\n", "* ``symmetry = None`` allowing to specify that $f$ is invariant under certain permutations of its arguments (which can reduce the number of points needed to determine it)\n", "* ``check = False`` whether the interpolation function should evaluate at more points than necessary, to determine whether the given values/function ``F`` really is a polynomial of the specified degree\n", "\n", "*Remark:* Even though this is a very natural and useful function, it is currently not implemented in SageMath. If you do a good job with this project, you could consider submitting this as new code to be integrated into SageMath (and I would be happy to help with this)." ] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.1", "language": "sage", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.3" } }, "nbformat": 4, "nbformat_minor": 2 }