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.

Week 7:

Hello everybody, 

           I hope everybody had a great reading week! This week we learned about linked lists. I thought they were unnecessary, because why couldn't we just use trees? The linked list looked like a tree with the root being the value, and the child being the rest of list (subtree). It wasn't until after this week's lab that I realized how useful they are for storing data. The recursive iteration through the linked lists made it really efficient which I found out after we remade the queue class with the linked list instead of the list data structure. The enqueue times with linked lists were much faster and better than with the normal lists. However, I wonder what other good uses there are of linked lists...? 

          As for Assignment 2, when first looking at the instructions, I was really confused. I had no idea of exactly what the goal of the assignment was. However, after reading the lecture slides a few times over I realized how simple it was implement regex tree program. Recursion was very important in making the trees. Once I found out how to implement each root node, then call them recursively, and accordingly, each regex tree just built its self. 

      I really enjoy the assignments in this course, because they really force us to understand the material taught in the course. 

Week Six: Trees

Welcome back,

           

         I hope everybody was very happy that reading week had officially began (I know I was). The topic in lectures this week, Trees was very interesting. This data structure was of a new type, something we never seen before. Trees organize data in a non linear fashion, unlike lists and stacks, trees are organized with respect to the hierarchy of the data. Every tree has one root node, and children belonging to that root. These children can either be subtrees - another tree with lower hierarchy than the root node - or a leaf node - node with no children. 

        Dan mentioned that trees were similar to the structure of a HTML document, and since a friend of mine has been learning HTML lately, I checked for myself. I thought it was pretty cool when I confirmed it myself. My buddy showed and discussed how the HTML document was organized with respect to the importance of the data in the document. Furthermore, we could relate trees to dictionaries, whereby each root of the tree is a key in a dictionary and the subtrees are values in the dictionary, which are also dictionaries. However you can see this would get messy because there can only be one reference to a specific key in a dictionary. Thus, that right there is what makes trees unique. 

Week Five ("Week No Sleep")

Hello again,

        It's already week five of the Spring term in 2014, and consequently, it's feeling like the fifth week of our Spring term of 2014. The weather is brutal and the mid term season is even worse, and I doubt I'm the only one feeling the wraith of this time of the year. However, on the bright side we do have reading week approaching us, which will be a nice time to relax and not worry about class for a while. Furthermore, Dan's decision to push the due date for Assignment 1 back another week, is giving me a great opportunity to perceiver through the assignment on the break so that perfection can be accomplished.

         Moreover, speaking of the Assignment 1, I started it this weekend (thinking it was due on February the 13th) and so far I think its coming out great! It took me a long time to start the assignment because I was having a hard time trying to understand how all the methods were going to be used by ConsoleController and GUIController. With that, I couldn't decide if the "cheeses" on the stools were better off an Int object or a Cheese object. However, after about an hour I got myself and my thoughts together and started typing. From there the assignment went pretty well. I didn't run into any troubles (lucky), so testing went well , thus leading me to a near completion. I still have a bit more implementation to do, about 10% left, plus tweaking design and style to finish it up. I'm going to finish up the assignment during the break, because unfortunately many of use have a nasty 20% Linear Algebra midterm on Friday. I guess w'll see how that goes, but non the less good luck on Assignment 1 and for some, on the Linear Algebra Test!

Week 4 Review

My fellow programmers,
    Welcome back for the latest week's review in CSC148. The major topic in class this week was Recursion. Recursion is the process whereby a complex problem is solved by breaking the problem down into simpler problems, until a base case is reached. Solving the base case allows us to reconstruct all the solved subproblems, to finally solve the bigger problem, initially presented. From the definition of recursion you can already notice that it seems like a great tool to use to solve a lot of complex problems.
    When Dan first started lecturing about recursion I was shocked that we never learned about this in CSC108, because seriously, I feel like this could have been a great way to think through a lot of the problems we faced last term. However, as I pondered about the clever algorithm I realized that I have been using it for a long time, but on a broader scale. Recursion is a great tool when solving problems involving critical thinking, because when put in a unfamiliar situation we must relate the big picture of the problem to smaller, more familiar problems. After solving these simple, and familiar problems, we can put their solutions together to finally solve the original problem that was presented to us.
    Anyways, going back to CSC148, I'm facing a problem understanding a minor detail of recursion. I don't understand how we could call a function within the implantation of that particular function. It seems like this is very important when solving problems using recursion, as we design a function to handle a complex problem by calling it within its self to handle the base case of that problem. I thought this whole time that a function couldn't be called until the function definition was complete. However,  hopefully after using recursion more often I'll be able to fully understand how this type of code is compiled, thus I'm excited to use recursion in next week's lab and when solving other computer programming problems.