Bachelor Seminar: Algebra and Computer Science
Instructor: Xavier Généreux
Content
This course on the application of algebra to computer science aims to introduce students to the different subjects of computer science that make use of algebraic theories such as groups, rings, fields and many other objects. This means that we cover a large spectrum of subjects within computer science. The goal of this seminar is twofold: first to learn about these algebraic structures and second to understand how they can be used in computer science.
Prerequisites
A certain level of mathematical maturity is recommended.
Organisation
There will be a mandatory session at the beginning of the semester, where I will explain the organisation of the course in detail. I will also present the list of topics during this session. You will have until the following week to choose your topic.
Topics can be chosen among the Topics list below.
After you had some time to familiarize yourself with the topic, there will be a mandatory session of short-talks (2-3 minutes) where you give a quick summary of your topic.
At the end of the semester we will take another 1 to 3 mandatory sessions for the seminar talks.
In between there will be no scheduled meetings, but of course I will be available for questions on your topics either virtually via mail, Zulip etc. or in person. At the request of students, there may be supplementary sessions to introduce some of the mathematical prerequisites required for specific projects.
References
- [1] Garding, Tambour - Algebra for Computer Science
- [2] Aubin, Rousseau - Mathematics and Technology
Topics
The following list of topics details rather vague areas of computer science that make some use of algebra. In many cases, more than one project can be done on the same topic. If two or more students select the same topic, they should communicate with me their specific plan and coordinate with each other to avoid overlap as much as possible. I have suggested some ressources but you are encouraged to seek out others.
Error correcting codes
The idea of error correcting code is to enable the robust transfer of data. This is done by adding some type of redundancy in the message allowing a receiver to detect and/or recover a lightly damaged message. The obvious question is how do we minimise redundancy while keeping a maximal amount of information. Many types of codes have been designed, all with their advantages and disadvantages. Here are some codes that would make a good project:
- Hadamard and Reed-Solomon codes
- Reed-Muller codes
- LDPC codes
- Many codes use deep mathematics structures. Come talk to me for some more advanced options!
References: [1] and [2]
Public key cryptography
Public key cryptography is a method of securing communication where each party possesses a pair of keys: one public and one private. Messages encrypted with the public key can only be decrypted with the corresponding private key, ensuring secure transmission without the need for a shared secret. Here are two of the most popular public key schemes:
- RSA
- The ressource [2] gives a good introduction to public key cryptosystems like RSA. If a student chooses this project, they are expected to push the discussion beyond a classical presentation of RSA.
- References: [2]
- ECDSA
- This is another popular cryptographic scheme used to certify the authenticity of a message. How does it work? What is it based on?
- References: https://www.cs.miami.edu/home/burt/learning/Csc609.142/ecdsa-cert.pdf
Integer factorisation
Factorisation is known to be a hard problem for computers. Since the introduction of RSA in 1977 there have been many new factorisation algorithms proposed to solve this problem.
References: [1] and “A Tale of Two Sieves” by Carl Pomerance
Other related topics:
- Pollard’s rho algorithm (+Brent)
- Lenstra elliptic-curve factorization
Pseudo-randomness
A truly random algorithm is known to be unachievable in practice. What kind of algorithms exist to emulate such behaviors? What are they based on?
References: [1] and [2]
Applications of the discrete Fourier transform
Fourier transforms are used everywhere in computer science. The first item of this list is an algorithm to compute Fast Fourier Transforms. The other items are applications of DFT.
- Cooley–Tukey FFT algorithm
- Schönhage–Strassen algorithm
- JPEG
References: [1], [2], Multidigit Multiplication for Mathematicians by Daniel J. Bernstein
Monoids and automatas
Theory of automata and formal languages based on ideas from linear algebra.
References:
- [1]
- “Semirings, automata, languages” by Werner Kuich and Arto Salomaa
Algebraic type theory
Category theory provides a unified treatment of mathematical properties and constructions that can be expressed in terms of “morphisms” between structures. This theory can be used to organise and develop the kinds of structure that arise in semantics for logics and programming languages.
References:
- Categories for Types by Roy L. Crole
- https://www.cl.cam.ac.uk/teaching/1617/L108/catl-notes.pdf
Hits and PageRank
Web search engines use eigenvector computations. How do they work? On what theory is it based on? How do they fix scale issues?
References:
- Amy. N. Langville and Carl D. Meyer, A Survey of Eigenvector Methods for Web Information Retrieval, SIAM Review, Volume 47, Issue 1, (2005), pp. 135–161.
- [2]
Your favorite topic!
Come talk to me if you would like to do something else.
Examination
Talk (40%): Near the end of the semester, you will present your topic to the group. As the subjects are very distincts, the talks should be accessible and offer a good introduction to the topic.
25 min + 5 min of questions
Paper (60%): A written seminar paper on your chosen topic (60% of the grade), the length of which must be between 7.000 and 14.000 characters. (~6 pages)
Here is the recommended structure of the paper:
- Introduction to the topic
- Prerequisites
- One or two related exercices with solution
- Detailed overview of your topic
- Conclusion with related subjects (and state of the art)
Submissions can be both in German and in English. The talk must be in English.
Schedule
IMPORTANT: The kickoff meeting will be held on Wednesday, April 17th, from 10:00 to 12:00.
“Wn” stands for the n-th week of the year.
2024
====
--- start of summer semester
W16 Kickoff meeting on Wednesday, April 17th, from 10:00 to 12:00.
W17
W18
W19
W20
W21
W22
W23
W24
W25
W26
W27
W28
W29
--- end of summer semester
W31
W32
W33
W34
W35
Artikelaktionen