Get a head start on program admission

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.

Course Type: Pathway | Breadth

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.

Foundations of Data Structures and Algorithms - Courses 1-2 Optional, Courses 3-5 Required for Online MS-CS

View on Coursera

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.

Course Grading Policy

Assignment

Percentage of Grade

Graded Assignments

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.

    2022 Coursera Innovation Award Winner Ribbon

    2022 Coursera Innovation Award Winner. Learn more.

    Notes

    • Cross-listed Courses: Courses that are offered under two or more programs. Considered equivalent when evaluating progress toward degree requirements. You may not earn credit for more than one version of a cross-listed course.
    • Page Updates: This page is periodically updated. Course information on the Coursera platform supersedes the information on this page. Click the View on Coursera button above for the most up-to-date information.