Data Structures & Algorithms IV: Pattern Matching, Dijkstra’s, MST, and Dynamic Programming Algorithms

Por: edX . en: , ,

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