Week 11

Hello everybody,

         I hope the test went well for everybody, because it didn't go well for me. I studied the night before the test, hence I didn't have a strong understanding of the material. After looking at the test again I realized that almost everything on the test was explicitly covered.... I'm especially disappointed that I didn't get the 'removing the leaves from a tree' question. This was probably the simplest question on the test, yet I tried solving it by doing a bunch of unnecessary operations at the leaf node, when I could simply, just returned None. I guess I didn't really understand what the question was asking for... Here's the actual solution from the course website:

Code:

def remove_leaves(t: 'BTNode') -> 'BTNode':
if not t or (not t.left and not t.right):
return None # no nodes, or root is leaf
t.left = remove_leaves(t.left)
t.right = remove_leaves(t.right)
return t

Assignment 2

Good Day all,

           Assignment 2 is due in two days, and fortunately, I'm progressing fairly well. I got stumped on the is_regex function for a while, but once I found out how to split up / iterate through a regular expression, the rest of the solution came easy.  Since we aren't being marked on efficiency,  all_regex_permutations was defined fairly easy because some code Dan supplied in a pervious lecture. I just finished defining the build_regex_tree function, and now am currently stuck on the regex_match function. I'm having a difficult time matching a regex string with any star regex. For example:

Code:
>>> tree = StarTree(DotTree(RegexTree("1", []), RegexTree('0', [])))

>>> regex_match(tree, "1010101010")
True

>>> regex_match(tree, '1101')
False

I am having a hard time finding a way to implement the difference between the two given strings. I'm finding this the hardest part of the assignment..... What do you all think?

P.S. The link to the A2 outline slides, Dan put on the discussion board, have been very helpful!

Anagrams and complexity

Hello everybody,

          In class this week we discussed complexity of an algorithm. We looked at two different approaches to find all the anagrams of an English word. The first algorithm involved finding all the permutations of the given word then returning all the words in the English word list that match one of the permutations. The second algorithm involved computing the signature of the word - a signature is the alphabetical arrangement of the letters in a word - then iterating through the word list and checking if the signature of our word matched the signature of the word in the word list. This approach was much more efficient then the first approach. The permutation approach involved a ridiculous amount of computations on the given word, followed by a full iteration through the word list for however many permutations were created by our word. As words get larger, the amount of permutations they have grow at a high order. Thus, the number of steps taken for this algorithm grows non-linearly for two inputs -  the length of the word, and the length of the word list. On the contrast, the number of steps taken with the second algorithm grows linearly, as a function of the length of the word list.

         The second algorithm was very clever, and showed that our understanding of a specific problem is key to coming up with a plausible solution. The second algorithm seemed much easier to implement as computer program, compared to first algorithm. However the signature approach involved a stronger intuition of english words.    

Week 8: Binary Search Trees

Hello friends, 

       The main topic in lectures this week was Binary Search Trees (BST's). A binary search tree is a binary tree, whereby every node's value is greater than values of all nodes in its left subtree, and less than the values of all the nodes in its right subtree. BST's allow efficient searching of data. To find a specific value, v in a BST, we can compare v to the value r at the root.

- If v = r, then the value is found

- If v < r, we move down the left subtree than repeat this process

- If v > r, we move down the right subtree then repeat this process

- If we reach an empty node than the value is not in the tree

The find function is defined below for a "BTNode" class.

code:

def _find(node: BTNode,  data: object): 

if not node or node.data == data: # reached None or data 

return node 

elif data < node.data: 

return _find(node.left, data) 

# data => node.data: 

return _find(node.right, data) 

We also discussed in class that this find function can be modified and used to implement insert and delete function. This is because both these function do similar comparisons to the values at each node, but then modify the node when the value is found. 

It is important to note that searching a BST  is only more efficient than searching linearly through a list when the BST is balanced. If a BST has values at each node, whereby the child of each node is greater than its parent, then searching through the BST will be the same as searching through a list. Thus, BST's are efficient only when there are values greater and smaller in the subtrees of each node. A 'complete binary tree' is an ideal BST, because each level is full except the bottom level, which is filled from left to right.