Most popular programs
Trending now
Delve into Pattern Matching algorithms from KMP to Rabin-Karp. Tackle essential algorithms that traverse the graph data structure like Dijkstra’s Shortest Path. Study algorithms that construct a Minimum Spanning Tree (MST) from a graph. Explore Dynamic Programming algorithms. Use the course visualization tool to understand the algorithms and their performance.
5,973 already enrolled!
This Data Structures & Algorithms course completes the 4-course sequence of the program with graph algorithms, dynamic programming and pattern matching solutions. A short Java review is presented on topics relevant to new data structures covered in this course. The course does require prior knowledge of Java, object-oriented programming and linear and non-linear data structures. Time complexity is threaded throughout the course within all the data structures and algorithms.
You will delve into the Graph ADT and all of its auxiliary data structures that are used to represent graphs. Understanding these representations is key to developing algorithms that traverse the entire graph. Two traversal algorithms are studied: Depth-First Search and Breadth-First Search. Once a graph is traversed then it follows that you want to find the shortest path from a single vertex to all other vertices. Dijkstra’s algorithm allows you to have a deeper understanding of the Graph ADT. You will investigate the Minimum Spanning Tree (MST) problem. Two important, greedy algorithms create an MST: Prim’s and Kruskal’s.
Prim’s focuses on connected graphs and uses the concept of growing a cloud of vertices. Kruskal’s approaches the MST differently and creates clusters of vertices that then form a forest.
The other half of this course examines text processing algorithms. Pattern Matching algorithms are crucial in everyday technology. You begin with the simplest of the algorithms, Brute Force, which is the easiest to implement and understand. Boyer-Moore and Knuth-Morris-Pratt (KMP) improve efficiency by using preprocessing techniques to find the pattern. However, KMP does an exceptional job of not repeating comparisons once the pattern is shifted. The last pattern matching algorithm is Rabin-Karp which is an “out of the box” approach to the problem. Rabin-Karp uses hash codes and a “rolling hash” to find the pattern in the text. A different text processing problem is locating DNA subsequences which leads us directly to Dynamic Programming techniques. You will break down large problems into simple subproblems that may overlap, but can be solved. Longest Common Subsequence is such an algorithm that locates the subsequence through dynamic programming techniques.
Basic knowledge of the Java programming language, object-oriented principles, and various abstract data types from LinkedLists to Hashmaps to Trees to Stacks & Queues.
Module 0: Introduction and Review
Module 12: Pattern Matching Algorithms
Module 13: Introduction to Graph Algorithms
Module 14: Minimum Spanning Trees
Module 15: Dynamic Programming
Who can take this course?
Unfortunately, learners residing in one or more of the following countries or regions will not be able to register for this course: Iran, Cuba and the Crimea region of Ukraine. While edX has sought licenses from the U.S. Office of Foreign Assets Control (OFAC) to offer our courses to learners in these countries and regions, the licenses we have received are not broad enough to allow us to offer this course in all locations. edX truly regrets that U.S. sanctions prevent us from offering all of our courses to everyone, no matter where they live.
Who can take this course?
Unfortunately, learners residing in one or more of the following countries or regions will not be able to register for this course: Iran, Cuba and the Crimea region of Ukraine. While edX has sought licenses from the U.S. Office of Foreign Assets Control (OFAC) to offer our courses to learners in these countries and regions, the licenses we have received are not broad enough to allow us to offer this course in all locations. edX truly regrets that U.S. sanctions prevent us from offering all of our courses to everyone, no matter where they live.
