Algorithms Based on Maths

Project Description

This project is intended to analyse algorithms that are based on maths and discover their applications. We will mainly cover the following algorithms/ techniques:

  1. Hashing: It is mainly used to store big arrays/ strings compactly and is thus used for pattern matching/sub-array equality, etc. in an optimal way.
  2. Linear Diophantine Equations: We will discuss the conditions for solutions to exist and look for optimal ways to find them explicitly.
  3. Gaussian Elimination: It is mainly used for solving linear equations but it has many other tricky applications like finding all xor subsets, etc. which will be discussed explicitly.
  4. Probability Theory: We will look at some applications of Linearity of Expectation and formulating recursive relations for calculation of various parameters.
  5. Generating Functions: We will learn to solve recursive relations in an optimal way like Fibonacci, etc.
  6. FF: A very widely used algorithm to multiply polynomials/n-bit numbers optimally.

Mentors

  • Utkarsh Gupta
  • Nitin Garg
  • Yash Gidwani

Learning Roadmap

Link to codeforces group for this project.