BST + Recursion = Happy

 BST + Recursion = Happy

This week's lab was the very first lab in which my partner and I had to stay till the very end and still didn't finish. Recursion makes life so much easier! I remember  in the first week when Danny was jokingly saying that by the end of the semester, we would all want to always use recursion on every problem. Well after this lab, I have to say that I have been converted to recursionism (well, to some extent). Implementing the count_less() function iteratively actually required a significant amount of work whereas the recursion solution was easy as 3.1415... (a little math humor :D)

I'm also starting to grow fond of BTSs and just trees in general. Off the top of my head, with binary search trees we can:

• Search in O(lgN) time (well, if it's fairly balanced)
• Find the minimum
• Find the maximum
• Find the inorder successor
• Find the inorder predecessor
• Do Huffman encoding by using a BST to get prefix-free binary strings
• And so many more things (as we've been seeing in class, exercises, labs, and assignment 2)...

I was also looking at different types of trees and I found so many interesting thing:

• There are different ways to balance a binary search tree:
• AVL trees
• Red & Black trees
• And there are many more kinds of trees, each tailored for a specific purpose:
• Radix trees: useful for constructing dictionaries with keys that can be expressed as strings
• There are prefix trees, suffix trees, and there are even trees to sub in for hash tables!

Dynamic Programming

Dynamic Programming

Dynamic Programming is another Divide and Conquer method of solving problems. Similar to recursion, we make make use of smaller cases of the problem to solve larger cases. The difference is that in recursion, we store the solutions to the smaller cases to avoid recomputing them. At times, DP (the street name for Dynamic Programming) is significantly more efficient than recursive solutions to the same problem. Here is a problem that runs significantly faster when using DP than when using recursion:

Example:

Let us have a rod of length n. We can divide this rod into smaller rods of integer lengths. Each length of a rod sells at a given price. What is the maximum revenue we can have by dividing this rod?

Prices:

Length        1        2        3        4        5        6        7        8        9        10

Price         $3      $7      $9      $12    $15    $19    $21    $24    $28    $30

Solution Using Recursion:

def cut_rod(n, p):

    """

    Recursive Solution to the rod cutting problem

    """

    if n == 0:

        return 0

    return max((p[i] + cut_rod(n-i-1, p)) for i in range(n))

if __name__ == '__main__':

    p = [3, 7, 9, 12, 15, 19, 21, 24, 28, 30]

    print(cut_rod(10, p))

After running, this codes prints out the number 35 as the maximum revenue that we can by dividing a rod of length 10. Playing around with different, we can see that indeed this is true.

10 = 2 + 2 + 2 + 2 + 2

Maximum Revenue = $7 + $7 + $7 + $7 + $7 = $35

Solution Using Dynamic Programming:

def cut_rod(n, p, r):

    """

    Dynamic Programming Solution to the rod cutting problem

    """

    if n == 0:

        return 0

    elif r[n-1] != -1:

        return r[n-1]

    r[n-1] = max((p[n-1-i] + cut_rod(i, p, r)) for i in range(n))

    return r[n-1]

if __name__ == '__main__':

    p = [3, 7, 9, 12, 15, 19, 21, 24, 28, 30]

    r = [-1 for x in range(10)]

    print(cut_rod(10, p, r))

This solution produces the same output as the recursion solution, 35. The difference here is that instead of simply calling the recursion function to solve for our smaller cases, we check if it has already been solved and use the answer it if it has been.

Runtime Analysis:

By going through the code for the first method and analyzing its recursion tree, we can see that it has a runtime of order O(2^n). Analyzing the runtime of the second solution tells us that its runtime is of order O(n^2) which is significantly smaller!!!!!

Sample Runtimes:

Case                                1            5            10            15            20            25

Recursion                        0.001     0.001     0.002       0.036        1.334       42.684

Dynamic Programming     0.001     0.001     0.001       0.001        0.001       0.001

Binary Trees

Binary Trees

A Binary Tree is a tree data structure with an arity (branching factor) of 2. Each node in the tree can have a left child node and a right child node. "Binary trees are used to implement build binary search trees and binary heaps" which are used in efficient sorting and searching algorithms. In class, we learned how implement binary trees, how to use them for binary searches, as well as insert or delete nodes.

This week I came across the Huffman Coding algorithm. I tried solving this problem on my own and realized that binary trees have a very interesting application here. Huffman coding is a file compression method. First, the characters in the file are ranked based on their frequency. Then a binary string (a string of 1's and 0's) is assigned to each character with the following properties:

• No binary string should be prefix-free. (no binary string should be the prefix of another binary string)
• The shorter string are assigned to the more frequent characters
• Let L_i denote the length of the binary string assigned to character a_i. Let F_i denote the frequency of the character a_i. The assignments should be done in a way such that the sum of L_i * F_i is minimum.

Binary trees are used in generating the prefix-free binary strings:

We can generate a binary tree that contains all possible binary strings:

• Let the root node be an empty string
• The right child node of a parent node will have the same string as its parent but with a 1 added to the end of the string
• The left child node of a parent node will have the same string as its parent but with a 0 added to the end of the string

In order to have prefix-free binary strings, we should choose them in such a way that none of them is the root of a subtree containing another one of them.

WASN'T THAT COOL! xD

Recursion

     Recursion is a process that repeats itself until it reaches a solution. The solution to a recursive problem requires the solution to a smaller version of the same problem. A recursive algorithm has a Base Case (a case that the solution is known for), as well as a Recursive Step (which determines how the recursion should repeat itself and make use of smaller cases). For example, in order to find the "n"th Fibonacci number, F(n), we need to find F(n-1) and F(n-2) because the recursive step for Fibonacci numbers is, F(n) = F(n-1) + F(n-2). Similarly, in order to find F(n-1), we need to first find F(n-2) and F(n-3).We repeat this process until we reach our base cases, F(1) and F(2). It is known that F(1) = F(2) = 1. From the base case, we can determine that F(3) = 2, F(4) = 3, and ...

     Another example is the Sierpinski triangle. The picture below demonstrates that in each step, we take a black triangle and we turn it into 3 black triangles with 1 white triangle in the middle.

Advantages:

• If implemented well, recursion can be a great solution to some problems.
• Using recursion can reduce the amount of code written.
• There are some problems that simply cannot be solved without recursion. For example, in order to display all the files in a system, you need to use recursion.

Object Oriented Programming (OOP)

     Since the beginning of CS 148, we've been working with classes, objects, instances, attributes, ... and we always hear the buzz work, "Object Oriented Programming". So, what exactly is OOP?

ob·ject

noun  \ˈäb-jikt, -(ˌ)jekt\

a thing that forms an element of or constitutes the subject matter of an investigation or science

ori·ent·ed

adjective\ˈȯr-ē-ˌen-təd\

interested in a particular thing, activity, etc.

pro·gram·ming

noun\-miŋ\

Well... ya know... programming

     Object oriented programming is a programming paradigm in which you have classes, and instances of those classes called Objects. Classes can be thought of as blueprints for the objects. Every object has attributes and some methods associated with it. The attributes store certain data about the object, and methods are procedures that can be executed on them.

Advantages of OOP:

• One of the main advantages of object oriented programming is that you can recycle code. Instead of writing all the code for every single object, you create a class, and get instances of the class.
• Modifications can be done in a much simpler fashion. If a certain attribute or method has to be changed, removed, or edited, one can do so by simply making the changes to the class.
• OOP forces programmers to plan well before writing their code, which is results in more robust code.