Advanced-Algorithms

Implementations of most algorithms learnt in the course UE18CS311 by PES University.

Assignments

Assignment 1

• Implement Dynamic table with and without struct hacking - Q1 - A / B
• Implement Splay Trees - Q2

Assignment 2

• Find longest common prefix in 2 strings using minimum R rotations - Q1
• Find longest common prefix in 2 substrings of a string using Rabin Karp and Binary Search method. link to a similar question - Q2

Assignment 3

• K Factor: Find number of strings of length N with K occurences of "abba" - Q1
• Find Edit distance with Insert + Delete using LCS algorithm - Q2A
• Find Edit distance with Insert + Delete + Subtitution - Q2B
• Find Edit distance with Weighted Insert + Weighted Delete + Weighted Subtitution - Q2C

Assignment 4

• Polynomial multiplication using FFT algorithm - Q1
• Solving linear equations using Chinese Remainder Theorem - Q2

Chapter - 1 Basics_Of_Complexity

• Dynamic Table - A1 - Q1
• Splay Trees - A1 - Q2

Chapter - 2 String_Comparisons

• Naive String Algorithm
• Modified Naive String Algorithm
• Rabin-Karp Algorithm
• Knuth-Morris-Pratt Algorithm
• Finite Automata String matching algorithm

Chapter - 3 Max Flow, Polynomials and FFT

• Recursive FFT for polynomial multiplication - A4 - Q1
• Ford Fulkerson/ Edmond Karp Algorithm
• Maximum bipartite matching

Chapter - 4 Number Theory

• Chinese Remainder Theorem - A4 - Q2
• Euclids Extended Algorithm - A4 - Q2

Chapter - 5 Dynamic_Programming

• Coin Row Problem
• Rod Cutting Problem
• Matrix Chain Multiplication
• Longest Common Subsequence

ToDo

• [C2] FSM
• [C2] Suffix Tree
• Assignment 1
• Assignment 2
• [C5] Rod Cutting problem
• [C5] Matrix Chain multiplication
• [C5] Longest Common Subsequence
• [C3] Ford Fulkerson Algorithm
• [C3] Fast Fourier Transform Algorithm (done in A4)
• [C4] Euclids Algorithm
• [C4] Euclids Extended algorithm
• [C4] RSA encryption