Class3.md

Class 3: Friday, March 24 – String Algorithms

Topics:

• unit testing, Python's unittest module and pytest tool
• palindromes: strings that read the same forwards and backwards, ignoring punctuation, whitespace, and letter casing
• string searching: find the starting index of the first occurrence of a pattern in a string
• permutation: arrangement of all items in a set into a sequence or order
• anagrams: permutations of words or phrases that produce another word

Resources:

• read StackOverflow's answers to the question what is unit testing?
• read The Hitchhiker's Guide to Python's tutorial on testing your code
• play around with Wordsmith's Internet Anagram Server

Challenges:

• implement palindrome checking functions using palindromes starter code:
  • implement is_palindrome_iterative - iterative version
  • implement is_palindrome_recursive - recursive version
  • run python palindromes.py string1 string2 ... stringN to test is_palindrome
    • example: python palindromes.py ABC noon RaceCar 'Taco, Cat' gives the result:

    FAIL: 'ABC' is not a palindrome
PASS: 'noon' is a palindrome
PASS: 'RaceCar' is a palindrome
PASS: 'Taco, Cat' is a palindrome
    

  • run pytest test_palindromes.py to run the palindromes unit tests and fix any failures
• implement string searching functions (try both iterative and recursive versions):
  • implement find(string, pattern) - true if string contains the entire pattern
  • implement find_index(string, pattern) - the starting index of the first occurrence of pattern in string
  • stretch: implement find_all_indexes(string, pattern) - a list of the starting indexes of all occurrences of pattern in string
• write your own unit tests for your string searching functions
  • include several test cases that are both positive (examples) and negative (counterexamples)
• annotate functions with complexity analysis

Stretch Challenges:

• implement permutation generating functions (try both iterative and recursive versions)
• implement anagram generating functions (try both iterative and recursive versions)
  • Hint: use the Unix words list located at: /usr/share/dict/words

Project:

• phone call routing scenarios 1 and 2:
  • implement phone number prefix matching
• annotate functions with complexity analysis