Start learning →

Strings, grids and bits

Finding a pattern in a text without repeating work, finding routes across a grid with breadth-first search and A*, and working directly on the bits of a number.

About 10 hours of study

Learning objectives

Lessons

  1. 1

    String matching: naive search and KMP Advanced

    Find every place a pattern appears in a text: the simple O(n·m) method, and Knuth–Morris–Pratt, which never moves backwards in the text.

  2. 2

    Searching grids: BFS and A* Advanced

    Treat a grid as a graph to find shortest paths through mazes and maps with BFS, then reach the goal faster with A*'s distance guess.

  3. 3

    Bit manipulation Intermediate

    Use AND, OR, XOR and shifts to test, set and clear single bits, list every subset, and solve classic problems with no extra memory.

Module practice

Module quiz

1. What is the worst-case time of the naive string search?
2. The lps table of KMP depends on what?
3. What is the lps table of ABCAB?
4. How much work does BFS do on a grid of R rows and C columns?
5. What is 13 & (13 − 1)?
6. A multi-source BFS starts with every exit in the queue at distance 0. What does each square's distance mean?
7. The items are a, b and c, for bits 0, 1 and 2. Which subset does the mask 5 stand for?

‹ Numbers and recurrencesFinal assessment ›