Algorithms

Linear Search

Get index
Find object (based on some attribute)
Get list of elements or object (based on some attribute)
Remove elements from a list

The goal is to search a collection to discover the location (index) of a particular element.

Bubble Sort

Recursion

Resursion, simply put, is when a function calls itself. Unfortunately getting a working recursive function is slightly more complicated than that.

Let’s take this function as an example:

def count_from(n):
    print(n)
    count_from(n + 1)


count_from(1)

Is the count_from function recursive? Yes! It is a function that calls itself. The down-side is it never stops calling itself. In Python you end up getting a RecursionError after The Call-Stack gets too large. In Java, this is called a StackOverflow error (sound familiar?).

The Base Case

What is the absolute limit? The last possible value for n where we know the answer and we can simply return it?

The Recursive Step

Take care of the smallest part and offload the rest of the answer to “someone else”.

factorial(5)
-----
5 x | (4 x 3 x 2 x 1)
-----

return 5 * factorial(4)

return n * factorial(n - 1)


bunny_ears(4)
----|
2 + |  (2 + 2 + 2)
----|


bunny_ears_2(5)

bunny # 5     4   3   2   1
       ----|
math    2 +| (3 + 2 + 3 + 2)
       ----|

The Call-Stack

Understanding the call stack is vital to be able to trace and analyze recursive functions.

At the base of the call-stack, we have the “main” program or as shown in the image below, the “global frame”.

Everytime a function gets executed, it is thrown to the top of the call stack.

def wake_up():
    print("waking up")


wake_up()

When the function is completed, it gets removed.

If you call functions within functions, the stack gets larger and larger.

Warning

Under construction.

Topics by Category:

- Searching
  - Linear
  - Binary
- Sorting
  - Pigeonhole
  - Bubble
  - Binary (in-sort)
  - Merge-sort
- Recursion
  - Primary concept
  - Recursive step
  - Base case
- Time/memory complexity
  - Big-O notation

Topics by Timeline:

- Recursion (every day)
- Time complexity (throughout)
- Linear Search
- Linear filtering
- Pigeonhole sort
- Bubble Sort
- Binary Search
- Binary in-sort
- Merge-sort

Other (advanced) topics (that may not be covered):

- Memoization
- Traversing trees
  - Breadth-first search
  - Depth-first search