Algorithms and Data Structures
Offered By: University of California, San Diego via edX
Course Description
Overview
This MicroMasters program is a mix of theory and practice: you will learn algorithmic techniques for solving various computational problems through implementing over one hundred algorithmic coding problems in a programming language of your choice.
No other online course in Algorithms even comes close to offering you a wealth of programming challenges that you may face at your next job interview. To prepare you, we have invested thousands of hours designing challenges as an alternative to multiple choice questions that you usually find in MOOCs. We believe in learning through application, especially when it comes to learning algorithms.
For each algorithm you develop and implement, we have designed multiple tests to check its correctness and running time — you will have to debug your programs without even knowing what these tests are! It may sound difficult, but we believe it is the only way to truly understand how the algorithms work and to master the art of programming.
Syllabus
Course 1: Algorithmic Design and Techniques
Learn how to design algorithms, solve computational problems and implement solutions efficiently.
Course 2: Data Structures Fundamentals
Learn about data structures that are used in computational thinking – both basic and advanced.
Course 3: Graph Algorithms
Learn how to use algorithms to explore graphs, compute shortest distance, min spanning tree, and connected components.
Course 4: NP-Complete Problems
Learn about NP-complete problems, known as hard problems that can’t be solved efficiently, and practice solving them using algorithmic techniques.
Course 5: String Processing and Pattern Matching Algorithms
Learn about pattern matching and string processing algorithms and how they apply to interesting applications.
Course 6: Dynamic Programming: Applications In Machine Learning and Genomics
Learn how dynamic programming and Hidden Markov Models can be used to compare genetic strings and uncover evolution.
Course 7: Graph Algorithms in Genome Sequencing
Learn how graphs are used to assemble millions of pieces of DNA into a contiguous genome and use these genomes to construct a Tree of Life.
Course 8: Algorithms and Data Structures Capstone
Synthesize your knowledge of algorithms and biology to build your own software for solving a biological challenge.
Courses
-
Building a fully-fledged algorithm to assemble genomes from DNA fragments on a real dataset is an enormous challenge with major demand in the multi-billion dollar biotech industry.
In this capstone project, we will take the training wheels off and let you design your own optimized software program for genome sequencing.
This big data challenge will cover the entire MicroMasters program. After a brief introduction to the steps required to build a genome assembler, we will let you take steps on your own to start working with real data taken from a sequencing machine and see if you can design genome assembly software that can compete with popular software used in hundreds of sequencing labs around the world every day.
-
In this course, part of the Algorithms and Data Structures MicroMasters program, you will learn basic algorithmic techniques and ideas for computational problems, which arise in practical applications such as sorting and searching, divide and conquer, greedy algorithms and dynamic programming.
This course will cover theories, including:
- how to sort data and how it helps for searching;
- how to break a large problem into pieces and solve them recursively;
- when it makes sense to proceed greedily;
- how dynamic programming is used in genomic studies.
You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).
-
A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently. In this course, part of the Algorithms and Data Structures MicroMasters program, we consider the common data structures that are used in various computational problems. You will learn how these data structures are implemented in different programming languages and will practice implementing them in our programming assignments. This will help you to understand what is going on inside a particular built-in implementation of a data structure and what to expect from it. You will also learn typical use cases for these data structures.
A few examples of questions that we are going to cover in this course are:
- What is a good strategy of resizing a dynamic array?
- How priority queues are implemented in C++, Java, and Python?
- How to implement a hash table so that the amortized running time of all operations is O(1) on average?
- What are good strategies to keep a binary tree balanced?
We look forward to seeing you in this course! We know it will make you a better programmer.
-
If you have ever used a navigation service to find the optimal route and estimate time to destination, you've used algorithms on graphs.
Graphs arise in various real-world situations, as there are road networks, water and electricity supply networks, computer networks and, most recently, social networks! If you're looking for the fastest time to get to work, cheapest way to connect set of computers into a network or efficient algorithm to automatically find communities and opinion leaders in Facebook, you're going to work with graphs and algorithms on graphs.
In this course, part of the Algorithms and Data Structures MicroMasters program, you will learn what a graph is and its most important properties. You’ll learn several ways to traverse graphs and how you can do useful things while traversing the graph in some order. We will also talk about shortest paths algorithms. We will finish with minimum spanning trees, which are used to plan road, telephone and computer networks and also find applications in clustering and approximate algorithms.
-
The world and internet are full of textual information. We search for information using textual queries and read websites, books and e-mails.
These are all strings from a computer science point of view. To make sense of all this information and make search efficient, search engines use many string algorithms. Moreover, the emerging field of personalized medicine uses many search algorithms to find disease-causing mutations in the human genome.
In this course, part of the Algorithms and Data Structures MicroMasters program, you will learn about:
- suffix trees;
- suffix arrays;
- how other brilliant algorithmic ideas help doctors to find differences between genomes;
- power lightning-fast Internet searches.
-
If you look at two genes that serve the same purpose in two different species, how can you rigorously compare these genes in order to see how they have evolved away from each other?
In the first part of the course, part of the Algorithms and Data Structures MicroMasters program, we will see how the dynamic programming paradigm can be used to solve a variety of different questions related to pairwise and multiple string comparison in order to discover evolutionary histories.
In the second part of the course, we will see how a powerful machine learning approach, using a Hidden Markov Model, can dig deeper and find relationships between less obviously related sequences, such as areas of the rapidly mutating HIV genome.
-
In this course, part of the Algorithms and Data Structures MicroMasters program, you will learn how graph algorithms are used in two fundamental problems in modern biology:
- How do we sequence a genome?
- How do we construct an evolutionary “Tree of Life?"
In the first part of the course, you will learn how genome sequencing relies on using a graph to assemble millions of tiny DNA fragments into a contiguous genome. We will then shift gears and learn how to construct an evolutionary tree of life from genome data.
-
Step into the area of more complex problems and learn advanced algorithms to help solve them.
This course, part of the Algorithms and Data Structures MicroMasters program, discusses inherently hard problems that you will come across in the real-world that do not have a known provably efficient algorithm, known as NP-Complete problems.
You will practice solving large instances of some of these problems despite their hardness using very efficient specialized software and algorithmic techniques including:
- SAT-solvers
- Approximate algorithms
- Special cases of NP-hard problems
- Heuristic algorithms
Taught by
Pavel Pevzner, Daniel Kane, Alexander S. Kulikov, Michael Levin, Neil Rhodes and Phillip Compeau
Tags
Related Courses
Algorithms and Data Structures CapstoneUniversity of California, San Diego via edX Artificial Intelligence in Bioinformatics
Taipei Medical University via FutureLearn AI for Scientific Research
LearnQuest via Coursera Genome Sequencing (Bioinformatics II)
University of California, San Diego via Coursera Bioinformatics
University of California, San Diego via Coursera