Preview this course in the non-credit experience today!
Start working toward program admission and requirements right away. Work you complete in the non-credit experience will transfer to the for-credit experience when you upgrade and pay tuition. See How It Works for details.

Specialization: Advanced Data Structures, RSA and Quantum Algorithms

Instructor: Dr. Sriram Sankaranarayanan, Professor of Computer Science

Prior knowledge needed: You must understand all concepts covered in Dr. Sankaranarayanan's non-credit Algorithms for Searching, Sorting, and Indexing and Trees and Graphs: Basics courses to succeed in this course. We highly recommend successfully completing those two courses in the non-credit experience before starting this course; they are a great option to refresh your skills and ensure you're ready. Note that you cannot apply credit from either of these courses toward MS-CS graduation requirements.  Completion of previous courses. Calculus, probability theory: distributions, expectations and moments. Some programming experience with Python.

Mathematical Background

We expect that the student is comfortable with basic mathematics at the level of a US College first year STEM student. This includes basic notions such as

• Sets and Functions: Properties of sets, definition and properties of functions.

• Logarithms and Exponentials: and their properties.

• Basic series summations: arithmetic and geometric series summations.

• Probability theory: basic definition of probability, independence of events, probability distributions and expectations.

CLRS has a helpful appendix but a student unfamiliar with these concepts can find numerous high quality explanations online.

Programming Background

The course involves solving programming assignments in Python. You must be comfortable with python programming.

• Basic control structures in python: conditional branches, for loops and recursion.

• Functions: defining and calling functions, and recursion.

• In-built data structures: Lists and Dictionaries

• Classes

Our use of python will get more sophisticated as the course progresses to accommodate some learning of python.

## Course Decription

This course introduces number-theory based cryptography, basics of quantum algorithms and advanced data-structures.

## Learning Outcomes

• Understand how basic number-theoretic concepts are used to build the RSA crypto-system.
• Learn about how quantum computers can be used to break the RSA cryptosystem.
• Understand the foundations of quantum computation and its basic building blocks.
• Explore the differences between classical and quantum algorithms.

Assignment

33% (11 assignments; 3% each)

Programming Assignments

52% (4 assignments; 13% each)

Final Exam

15%

## Course Content

Duration: 10 hours

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

Students can expect a programming assignment at the end of this module. The assignment explores some basic algorithms for factoring numbers. Problems requiring you to provide manual answers are not graded. They are intended to help you develop your ideas.

Duration: 13 hours

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 have a brief introduction to IBM qiskit package for exploring quantum circuits.

Students can expect a programming assignment at the end of this module. This assignment asks you to design simple quantum algorithms and design circuits to implement them using the quantum gates you learned about in the lectures. The manually graded problems are just for your own design process: we encourage you to do them though we will not grade them. Your work will be autograded.

Duration: 12 hours

We will describe Shor's algorithm and as part of Shor's algorithm show how Quantum Fourier Transform (a very useful operation for quantum systems) 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.

Students can expect a programming assignment at the end of this module. This assignment will study Shor's algorithm. It has problems involving designing and programming solutions. The manually graded problems will carry no credit but are important for the process of thinking through solutions before programming them.

Duration: 8 hours

We will learn two important and interesting data structures to round off this course. The first data structure will be the widely used B-Tree data structure which is used in indexing and storing large amounts of data on a disk. Next, we will study algorithms on strings esp. string search algorithm. We will study the suffix trie data structure: a very useful data structure for fast searching over strings.

Students can expect a programming assignment at the end of this module. This assignment covers the material for B-Trees and Suffix Tries. It relies a lot on the interactive notes and the code we wrote for these two data structures. Manually graded problems carry no points but solving them is essential to developing the solution.

Duration: See below

This module contains materials for the final exam. It will involve formulating a solution/algorithm for some problem and then implementing it in Python to pass test cases. If you've upgraded to the for-credit version of this course, please make sure you review the additional for-credit materials in the introductory module and anywhere else they may be found.

The exam is open notes: you are welcome to look up notes and videos of materials from our Coursera webpage. However, you are forbidden from asking others for solutions: this includes other students, friends, or asking for solutions from people on the web.

Manually graded problems do not have any points assigned to them. All points are obtained by writing code that passes test cases.

The notebook should finish running in 1.5 minutes (roughly) or you will not get a grade on the exam. This is important since you should be employing efficient solutions to problems.

We have given you useful code from our notes so that you do not have to cut and paste them. You should run those cells before attempting to solve the problem or run test cases.

This exam may require you to create simple quantum algorithms and implement them in QISKIT so that we can autograde your work.  We have presented QISKIT in our notes and provided many examples of how to express quantum circuits in QISKIT.  You may find documentation of QISKIT from the
IBM website

You will have 36 hours from when you start the attempt. The number of submissions is limited, so submit only if you are absolutely sure that you are done.