Theory and Practice of Algorithms Proofs

Repository meant to accompany the course Theory and Practice of Algorithms at the Hokkaido University, that I took in Summer 2020. Even though originally intended to only contain solutions and proofs given in Lectures, I have decided to expand it to lecture notes as well, which include definitions, lemmas, algorithms, theorems and corollaries written on slides, in order to have them available for future reference.

All documents were created using Texpad and TexMaker for MacOS, and .pdf documents were created using pdflatex. The repository contains only .tex files which can be used to generate .pdf documents.

Course Outline

• Lecture 1 - Introduction to Basic Discrete Structures (Rings, Groups, Fields and Master Theorem)
• Lecture 2 - Finite Groups, Finite Rings and Finite Fields (GCD, Chinese Remaindering and Euler's Phi Function)
• Lecture 3 - Finite Fields (Generators and Group Cyclicity)
• Lecture 4 - More About Finite Fields (Field Characteristic, Algebaric Structure of Finite Fields and Irreducible Polynomials)
• Lecture 5 - Finite Fields, Alogrithms (Uniqueness of Finite Fields, Modular Exponentiation and Pseudo-Primes)
• Lecture 6 - Testing Primality (Introduction to AKS Algorithm and its Steps)
• Lecture 7 - Testing Primality - II (Preparations for and Correctness Proof of AKS Algorithm)
• Lecture 8 - The Schönhage–Strassen Multiplication Algorithm Part I – Preparations (Roots of Unity and Discrete and Fast Fourier Transformations)
• Lecture 9 - The Schönhage–Strassen Multiplication Algorithm Part II – FFT, Karatsuba Algorithm (Fast Fourier Transformation, Karatsuba Algorithm and The Schönhage–Strassen Algorithm)
• Lecture 10 - The Magic of Probabilty (Introduction to using Probability Algorithms with One-sided Error for Testing)
• Lecture 11 - Freivald’s Matrix Multiplication Checker and Solovay and Strassen’s Primality Test (Freivald's Algorithm, Solovay Strassen Primality Test, Jacobi Symbol and Quadratic Residues)
• Lecture 12 - Parallel Computations (Introduction to parallel problems and Uniform Families of Boolean Circuits)
• Lecture 13 - Parallel Computations - II (Radix-4 Representation, Fermat Ring and Iterated Addition)
• Lecture 14 - Distributed Algorithms - Leader Election (Introduction to Distributed Algorithms and Leader Election Algorithms)
• Lecture 15 - Distributed Algorithms - Leader Election II (Time Slice Alogirthm and Lower Bound for the Leader Election Algorithm)

Notes About Solutions

Lectures 6, 9, 10 and 14 have no exercises stated in slides, so documents for those lectures only contain the 'Lecture Summary' section.

It is worth noting that proofs and exercise solutions are done to the best of my ability, without insight into correct solution, which means that they are not necessarily 100% correct. I do plan, however, to return and make corrections to the possibly faulty solutions, should I expand my knowledge on the topics in the future.