Mathematics Undergraduate Seminar Series presentations today at 3 p.m.
Wednesday, Apr. 8 | 3-3:50 p.m. | Bridges 268
Featuring MSUM students Ashley Borchardt and Paige Meyer
The Mathematics Undergraduate Seminar Series presents two student presentations by Ashley Borchardt and Paige Meyer
Ashley Borchardt: Opening Doors with de Bruijn Sequences
De Bruijn sequences are a fascinating topic in mathematics that can
be applied in a variety of different scientific, and conventional, spheres of study and application. De Bruijn sequences can be found in techniques for genetic coding, computer systems and programming, and even cracking the code to a locked door. In this presentation, we will explore what a de Bruijn sequence is and answer the questions “Can they be counted, and if so, how many are there?” We will aid our exploration by examining how de Bruijn sequences relate to directed graphs and Eulerian circuits, which will allow us to enumerate these sequences using Gustav Kirchhoff’s Matrix Tree Theorem.
Paige Meyer: The Traveling Salesman Problem
Suppose there is a salesman who needs to visit a selected set of cities. We want to find which order to visit these cities to minimize the total distance traveled by the salesman, in order to minimize the money spent on gas driving from city to city. It is not a difficult problem to calculate the total distance for a few cities, but as the number of cities increases, so does the time needed to solve this problem. We do not want to spend all day deciding on which order this salesman should visit the cities, so we want to find a way to quickly compute the route the salesman should take. During this seminar, we will discuss various algorithms that aid in solving or approximating a solution for this problem relatively quickly.