Data Structures & Algorithms IV: Pattern Matching, Dijkstra’s, MST, and Dynamic Programming Algorithms
Module 0: Introduction and Review
- Review of important Java principles involved in object-oriented design
- The Iterator & Iterable design patterns, and the Comparable & Comparator interfaces
- Basic “Big-Oh” notation and asymptotic analysis
Module 12: Pattern Matching Algorithms
- Examine algorithms for text processing, the simplest being Brute Force
- Apply preprocessing techniques in Boyer-Moore to improve performance
- Knuth-Morris-Pratt (KMP) avoids waste in prefixes of the pattern to achieve the best runtime
- Approach the pattern matching problem from the perspective of hash codes in Rabin-Karp
- Consider the time complexity of each of the algorithms
Module 13: Introduction to Graph Algorithms
- Explore the Graph ADT and its representation in auxiliary data structures
- Implement the Depth-First Search and Breadth-First Search graph traversal algorithms
- Examine weighted graphs and Dijkstra’s shortest path algorithm which uses edge relaxation
Module 14: Minimum Spanning Trees
- Study weighted, undirected graphs to find Minimum Spanning Trees (MST)
- Apply greedy algorithms to solve the MST problem
- Prim’s algorithm operates on connected graphs and employs the concept of cloud
- Approach the MST problem with Kruskal’s algorithm using cluster and forest concepts
Module 15: Dynamic Programming
- Apply the Dynamic Programming techniques that focus on the subproblems
- Examine the components of a dynamic programming algorithmic solution
- Implement the Longest Common Subsequence algorithm to solve DNA