Advanced Data Structures, RSA and Quantum Algorithms

Advanced Data Structures, RSA and Quantum Algorithms

This course is part of Foundations of Data Structures and Algorithms Specialization

Instructor: Sriram Sankaranarayanan

Access provided by Exxaro

6,163 already enrolled

4 modules

Gain insight into a topic and learn the fundamentals.

58 reviews

Advanced level

Recommended experience

5 weeks to complete

at 10 hours a week

Flexible schedule

Learn at your own pace

4 modules

Gain insight into a topic and learn the fundamentals.

58 reviews

Advanced level

Recommended experience

5 weeks to complete

at 10 hours a week

Flexible schedule

Learn at your own pace

What you'll learn

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

Skills you'll gain

Tools you'll learn

IBM Cloud

Details to know

Shareable certificate

Add to your LinkedIn profile

Assessments

12 assignments

Taught in English

See how employees at top companies are mastering in-demand skills

Learn more about Coursera for Business

logos of Petrobras, TATA, Danone, Capgemini, P&G and L'Oreal

Build your subject-matter expertise

This course is part of the Foundations of Data Structures and Algorithms Specialization

When you enroll in this course, you'll also be enrolled in this Specialization.

Learn new concepts from industry experts
Gain a foundational understanding of a subject or tool
Develop job-relevant skills with hands-on projects
Earn a shareable career certificate

There are 4 modules in this course

Introduces number-theory based cryptography, basics of quantum algorithms and advanced data-structures.

This course can be taken for academic credit as part of CU Boulder’s Masters of Science in Computer Science (MS-CS) degrees offered on the Coursera platform. This fully accredited graduate degree offer targeted courses, short 8-week sessions, and pay-as-you-go tuition. Admission is based on performance in three preliminary courses, not academic history. CU degrees on Coursera are ideal for recent graduates or working professionals. Learn more: MS in Computer Science: https://coursera.org/degrees/ms-computer-science-boulder

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

What's included

5 videos5 readings5 assignments1 programming assignment2 ungraded labs

5 videos Total 148 minutes

Introduction to Public Key Cryptography 21 minutes
Euclid's Algorithm and GCD 23 minutes
Extended Euclid Bezout Coefficients 18 minutes
RSA Cryptography 44 minutes
Quantum Physics Computing Basics 42 minutes

5 readings Total 36 minutes

Course Updates and Accessibility Support 1 minute
Earn Academic Credit for your Work! 10 minutes
Course Support 10 minutes
Assessment Expectations 5 minutes
AI Citation and Acknowledgement 10 minutes

5 assignments Total 125 minutes

AI Policy Quiz 5 minutes
Quiz on Public Key Cryptography 20 minutes
GCD and Euclid's Algorithm 30 minutes
Bezout Coefficients 20 minutes
Quiz on RSA 50 minutes

1 programming assignment Total 180 minutes

Week 1 Programming Assignment 180 minutes

2 ungraded labs Total 120 minutes

Notes on GCD, Euclid's Algorithm and Extended GCD 60 minutes
Notes on RSA public key cryptosystem 60 minutes

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.

What's included

8 videos5 assignments1 programming assignment3 ungraded labs

8 videos Total 180 minutes

Qubits and Super Positions 30 minutes
Unitary Operators and Reversible Computation 7 minutes
Multi Qubit Quantum States 30 minutes
Multi Qubit Quantum Gates 29 minutes
Quantum Parallelism 15 minutes
No Cloning Theorem 5 minutes
Bells Inequality Power of Entangled States 22 minutes
Grover Search Algorithm 43 minutes

5 assignments Total 295 minutes

Qubits 45 minutes
Single Qubit Quantum Gates 45 minutes
Multiple Qubit Quantum States 120 minutes
Multiple Qubit Quantum Gates 40 minutes
Quantum Parallelism and Implementing Classical Gates 45 minutes

1 programming assignment Total 180 minutes

Week 2 Programming Assignment 180 minutes

3 ungraded labs Total 180 minutes

Interactive Notes on Basics of Quantum Computation 60 minutes
Interactive Notes on Multi-Qubit Quantum Systems 60 minutes
Interactive Notes: Grover's Search Algorithm 60 minutes

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.

What's included

7 videos1 reading2 assignments1 programming assignment2 ungraded labs

7 videos Total 202 minutes

Order Finding and Factoring 23 minutes
Order Finding on a Quantum Computer 26 minutes
Recap: FFT Basics of Complex Numbers and Roots of Unity 48 minutes
Recap: Discrete-Time Fourier Transforms 35 minutes
Recap: FFT Divide and Conquer Algorithm 22 minutes
Quantum Fourier Transform: Part 1 19 minutes
Quantum Fourier Transform: Part 2 28 minutes

1 reading Total 10 minutes

Note 10 minutes

2 assignments Total 240 minutes

Order Finding And Factoring 180 minutes
Quantum Fourier Transform 60 minutes

1 programming assignment Total 180 minutes

Week 3 Programming Assignment 180 minutes

2 ungraded labs Total 120 minutes

Detailed Notes on Shor's Algorithm 60 minutes
Interactive Detailed Notes on Quantum Fourier Transform 60 minutes

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.

What's included

12 videos1 programming assignment2 ungraded labs

12 videos Total 191 minutes

Introduction to B-Trees 4 minutes
Structure and Properties of B-Trees 18 minutes
Simple Example 3 minutes
Searching for a Key in a B-Tree 6 minutes
B-Tree Key Insertion Algorithm 9 minutes
B-Tree Key Deletion Algorithm 11 minutes
Tries: Basics 40 minutes
Suffix Tries 13 minutes
Generalized Suffix Tries 34 minutes
Ukkonen's Algorithm - Part 1 25 minutes
Ukkonen's Algorithm - Part 2 26 minutes
Concluding Remarks 3 minutes

1 programming assignment Total 180 minutes

Week 4 Programming Assignment 180 minutes

2 ungraded labs Total 120 minutes

Interactive Notes on B-Trees 60 minutes
Interactive Notes on Suffix Tries 60 minutes

Earn a career certificate

Add this credential to your LinkedIn profile, resume, or CV. Share it on social media and in your performance review.

Build toward a degree

This course is part of the following degree program(s) offered by University of Colorado Boulder. If you are admitted and enroll, your completed coursework may count toward your degree learning and your progress can transfer with you.¹

Instructor

Instructor ratings

(16 ratings)

Sriram Sankaranarayanan

University of Colorado Boulder

5 Courses 98,201 learners

Offered by

University of Colorado Boulder

Why people choose Coursera for their career

Felipe M.

Learner since 2018

"To be able to take courses at my own pace and rhythm has been an amazing experience. I can learn whenever it fits my schedule and mood."

Jennifer J.

Learner since 2020

"I directly applied the concepts and skills I learned from my courses to an exciting new project at work."

Larry W.

Learner since 2021

"When I need courses on topics that my university doesn't offer, Coursera is one of the best places to go."

Chaitanya A.

"Learning isn't just about being better at your job: it's so much more than that. Coursera allows me to learn without limits."

Learner reviews

5 stars
81.03%
4 stars
8.62%
3 stars
1.72%
2 stars
5.17%
1 star
3.44%

Showing 3 of 58

Reviewed on Aug 11, 2024

Great specialization, as close to a real university course series as possible in this online setting.

Reviewed on Nov 23, 2024

Amazing teaching, well made tasks and assessments. However, some computing task takes quite a while, a lot of code to familiarize with before you can solve the problems.

View more reviews