Class2.md

Class 2: Recursion & Search Algorithms

Topics

• Compare iteration and recursion with factorial function
• Search algorithms: linear search and binary search

Resources

• Review Make School's algorithm analysis slides
• Read Vaidehi Joshi's article on logarithms, binary search, and big O notation with excellent, beautiful drawings
• Read Interview Cake's article on logarithms and binary search
• Read Interview Cake's article on the idea behind big O notation
• Read Stack Overflow's plain English explanations of big O notation
• Read Justin Abrams's article on big O notation explained by a self-taught programmer
• Watch HackerRank's recursive algorithms video, binary search algorithm video, and big O notation video
• Watch Harvard's old recursion video, new recursion video, stack frames video, linear search video, binary search video, asymptotic notation video, and computational complexity video

Challenges

• Implement iterative factorial function using recursion starter code:
  • Implement factorial(n) - the product of all 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 recursion_test.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 search_test.py to run the search unit tests and fix any failures
• Annotate functions with complexity analysis of running time and space (memory)

Stretch Challenges

• Implement recursive permutation and combination functions
• Make these functions efficient by avoiding repeated subproblems
• Write your own unit tests to ensure your algorithms are robust