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.
