Class2.md

Class 2: Wednesday, March 22 – Recursion & Search Algorithms

Topics:

• compare iteration and recursion with factorial function
• searching algorithms: linear search and binary search

Resources:

• review Make School's algorithm analysis slides
• read InterviewCake's article on the idea behind big O notation
• read StackOverflow's plain English explanations of big O notation

Challenges:

• implement iterative factorial function using recursion starter code:
  • implement factorial(n) - the product of the integers 1 through n
  • run python recursion.py number to test factorial on a number
    • example: python recursion.py 8 gives the result factorial(8) => 40320
  • run pytest test_recursion.py to run the recursion unit tests and fix any failures
• implement recursive linear and binary search algorithms using search starter code:
  • implement linear_search(array, item) - the first index of item in array
  • implement binary_search(array, item) - the index of item in sorted array
  • run pytest test_search.py to run the search unit tests and fix any failures
• annotate all functions with running time complexity analysis

Stretch Challenges:

• implement efficient permutation and combination functions