Advanced Data Structures, RSA and Quantum Algorithms

This module covers a brief recap of elementary number theory, GCD, Euclid's algorithm, Bezout coefficients and presents the RSA public key cryptosystem. It then shows how the security of RSA relies on the supposed hardness of the factoring problem for numbers that are semi-primes

This module covers the basics of quantum computing with an introduction to qubits, the concept of a superposition, the effect of measuring a qubit, elementary quantum gates, direct/tensor products, entanglements, quantum parallelism and ends with a presentation of Grover's search algorithm

We will describe Shor's algorithm and as part of Shor's algorithm show how Quantum Fourier Transform is computed. We will show how the power of quantum parallelism combines with the divide-and-conquer paradigm for algorithm design to yield exponential speedups for computing Quantum Fourier Transforms

We will learn two important and interesting data structures: B-Tree data structure for indexing and storing large amounts of data on disk, and suffix trie data structure for fast searching over strings