Exact Pattern Matching Algorithms

Exact Pattern Matching

• Input: Strings T (Text) and P (Pattern)
• Output: All positions in T where P appears as a substring.

Brute Force Algorithm

• Slides the Pattern down Text
• Running time: Θ(|T||P|)

Skipping Positions

• Allows for skipping positions when comparing the pattern to the text.

Definitions

• Border: Prefix of a string that is also a suffix, but not the entire string.
• Example:
  • "a" is a border of "arba"
  • "ab" is a border of "abcdab"
  • "abab" is a border of "ababab"
  • "ab" is not a border of "ab"

Shifting Pattern

• Finds the longest common prefix 'u' between the pattern and the text.
• Finds the longest border 'w' of 'u'.
• Moves the pattern such that the prefix 'w' in the pattern aligns with the suffix 'w' in the text.

Algorithm Efficiency

• Definition: Algorithm performance measured in terms of time and space usage.
• Time Complexity: How runtime changes with input size, often expressed using Big O notation (e.g., O(n), O(log n)).
• Space Complexity: Amount of memory used by the algorithm as input size changes.
• Trade-offs: Balancing time efficiency against memory usage, some algorithms are faster but might need more memory.

Data Structures

• Definition: Organized ways to store and manage data efficiently.
• Types:
  • ** Primitive:** Basic data types like integers, characters, floats
  • Composite: Collections of primitive data types like arrays, structures, classes
  • Abstract Data Types (ADTs): Conceptual representations of data like lists, stacks, queues, trees, and graphs.
• Key Operations: Common actions performed on data structures like insertion, deletion, traversal, searching.
• Choice of Data Structure: Depends on the algorithm's requirements, efficiency of operations, and memory usage.

Complexity Analysis

• Purpose: Evaluating algorithm performance and efficiency.
• Big O Notation: Describes the worst-case scenario of an algorithm's time complexity.
• Big Θ Notation: Describes the average-case performance of an algorithm.
• Big Ω Notation: Describes the best-case scenario of an algorithm's time complexity.
• Asymptotic Analysis: Examining how algorithms behave as input size increases infinitely.

Graph Algorithms

• Definition: Algorithms designed for processing and analyzing graphs.
• Key Algorithms:
  • Dijkstra’s Algorithm: Finding the shortest path in a weighted graph.
  • Depth-First Search (DFS): Exploring a graph by going as deep as possible along a branch before backtracking.
  • Breadth-First Search (BFS): Exploring a graph by examining all neighbors at the current depth before moving on.
  • Prim’s and Kruskal’s Algorithms: Finding the minimum spanning tree in a graph.
• Applications: Network routing, scheduling, social network analysis.

Design Patterns

• Definition: Standardized solutions for common software design problems.
• Categories:
  • Creational Patterns: Focus on object creation (e.g., Singleton, Factory Method).
  • Structural Patterns: Deal with object composition (e.g., Adapter, Composite).
  • Behavioral Patterns: Manage algorithms and responsibilities between objects (e.g., Observer, Strategy).
• Importance: Promote reusability, scalability, and maintainability in software design.