Last Week: 

On Sorting:

I learned a lot more about run-time complexity at yesterday's lecture.Assume there are 2 functions, f1 and f2 that are O(n^2) and O(nlogn) respectively. Consider 2 compositions, g(s) = f`1(f2(s)) and h(t) as f2(f1(t)).

We can analyze minimum and maximum runtimes, assuming we can choose inputs t and s. This I didn't know: I thought that regardless of the kind of objects being operated on, the run-time would be the same. Now I understand why it's specifically called worst-case. Anyways: for the minimum(or best case scenario), just choose the easiest input possible (like anything returning bools after simple linear operations, or even just anything returning argument t or s). 

If we further assume that both f1 and f2 perform some sort of str to str conversion (the specific code doesn't matter), we know that for g, f2 will give an output of n^2 (another thing I learned, that O applies to both complexity for runtime and output size), and altogether, as nlogn is faster than O(n^2), the overall runtime cannot be less than n^2. For the worst case, it will look like a regular composition, or be 2n^2logn.

A similar analysis can be performed for h, but the key is that I learned a proper technique for evaluating these type of things: I can vary inputs depending on which scenario I am concerned with, and that the overall output will not always be an arithmetic composition. I have to think about how the code works: if there are 2 operations, and are they are performed consequently, for a worst case the overall run-time will be the sum, as in any case the program must execute both. Also, given 2 different Os for such consequent operations, the asymptotic runtime(which is really "run-time in the limit", or "where run-time will even out") will be dominated by the longer time, as for the above example, nlogn is a negligible addition to n^2. 

Lastly, this type of analysis can give much more tighter bounds than what I was doing before. In any case, I will pay most attention to whatever Big O practice is posted as this is my weakest area by far.

Week of March 26th:

The lab really helped me understand the different sorting algorithms. Apparently, there are 2 things you can do to optimize performance: run the cprofile and check which areas are taking up the most computation, then rewrite them. However, this may not always solve the issue (for example, in bubblesort 1 and 2, as the algorithm may be too intensive even at the simplest implementation). In this case, we were advised to write a new algorithm altogether.

The cprofile was very insightful. For example, I learned that just storing the length of the list in a dummy variable instead of calling len(L) at each recursive call can save quite a bit of time. I did not know that in the long-run, the len() call would weigh the time down so much. I also learned that boolean comparison statements slow the sorts down too. 

The Excel chart for all three types of lists was very insightful. The timsort destroyed everyone each time, but I was still curious about it. Apparently it is compiled in C, which, being a "lower" language grants it the super speed, and uses various methods to find runs, or subsets of the list that are already sorted. I learned that (even though the code is alot longer than the sorts we looked at) it spends the majority of the time deciding which sort to use, but that this really pays off because it makes the actual sorting instantaneous. In any case, I was very impressed.

I still don't really get Big-O, in the sense that almost all of the graphs in my chart looked somewhat parabolic. But is there a quick way to 'eyeball' the worst-case-complexity just by looking at the algorithm? The last question on the midterm implied this, but as I'm still uncertain, and I need to ask about this.

Surprisingly, the early exit in bubble_sort 2 added no real benefits as my investigation with the TA showed. Also want to know why this happens.

This week, I finished a2. I fixed the __eq__ expressions for a more efficient design: before, they didn't 'stack properly' and hence were not respecting the tree structure of regexes, but after a rigorous debug process I think I worked the kinks out. In any case, I could easily replicate everything on the assignment sheets.

Through working on this, I came to really appreciate OOP. I started with a really complex and long code design for the regexes, but through constant streamlining managed to slim it down more and more; at every step it became evident which parts could be put together more efficiently. So the __init__became very vital as well, because I ended up making a down to up approach, where I initialized basic regex objects, and with them started creating much more complex ones.

In any case, I really think this assignment helped me understand ADTs more in general (i.e versus direct inheritance) and also solidified my comprehension of methods, namely the __eq__, which I didn't know before. Now I see that a class can have its own eq method, and this opens up new possibilities and a more versatile way of interacting with other objects (vs, for example, just using the =)

In any case, super excited for part 2 !

Week of Feb 27th:

Learned alot about OOP this week in studying for the midterm and starting a2:

I now understand inheritance much better, and I see that the __init__ and __eq__ methods are just that: methods: I had a hard time as I thought they were somehow different from any other methods, but after working through the boundedStack Subclass and IntStack subclass exercises I understood how their inheritance actually works as I had to call it form my superclass Stack:

I became much better at one statement recursions after going through the nested_depth and max_depth examples and now have no problem using them on the fly. My issue was that I was not comfortable not seeing it a usual loop structure (my TA presented it to us like this) and hence I could not easily identify the base case when seeing it in one line, but after trying it out a few times it finally clicked.

For linked lists this week, my partner was away (for which I am grateful), and I got to do the whole lab by myself, so I felt like I learned twice as much. I had no problems reimplementing the queue as a Linked List but spent an hour trying to make sure it decapitates like a queue and not a stack; I'm still not clear on this so I will have to ask my TA next week.

I also realized why I was having such a hard time with init before: my shell doesn't allow me to define the class types for self and other input variables in the init statement, so all the programs I wrote before would never run in my shell and I didn't get why; I also can't use the ) -> bool/object/None,etc: to end off my inits, but once I figured this out everything has been much easier.

I did almost all of a2.1 today; in fact I had alot of fun. My regexes work exactly like trees; for me the biggest challenge was getting the correct __repr__ for say, regex1, but then removing the quotation marks when regex1 was used as an input in some other regex2. I solved this by assigning a self.value within each regex's init that holds its actual character and then using the repr to just add outside ' 's to the self.value; I've been able to successfully duplicate every compound regex on the assignment sheet so far so I assume it works!

One error I made today was to write if regex == s statements for each regex's __eq__ method, but I see now that for more complex and longer regexes this might not work. Instead, I need to redefine them recursively using the input regex __eq__ methods, so that

regex==s becomes regex1.__eq__(s) etc.This will link it back to the base case, which is the single length regex eq method.

Also sorry this entry is late, I completely got carried away with a2!

Feb 13: Filter, Zip, and A1

This week in lab I learned about the zip function. This function takes at least 2 lists, and creates a new one with tuple entries corresponding to the first items in both. So, for example, if I had a = [1, 2, 3] and b = [a, b, c], zip(a,b) would give me [(1,a), (2,b), (3,c)]. This is like a matrix concatenation of sorts and was also exemplified in the lab, where it was used for  some basic linear algebra functions.

The lab was great. We got to strip down and rewrite dot and cross product functions without using list comprehensions; we built them up form scratch. For example, the filter list comprehension is both a loop and an if statement in one line, and is a much more efficient way of 'filtering' whether to do something or not, but once we  rewrote it as the original loop structure, I could better understand what was actually happening inside.

We finished assignment 1. Actually using the things we have learned over the last 6 weeks in such a dynamic setting greatly enhanced my understanding of OOP. Inheritance, subclass, method headers, the init, I now understand all of these. I was impressed with how streamlined and efficient the OOP code allows this game to be. As we programmed it, we 'built' up from the ground and got to see the various functions pass objects back and forth between each other. So it made sense that console controller wouldn't work without TOAHModel, and etc.

I also finally understand the if name == main; all somebody had to tell me was that whatever code you write underneath will be executed when the program runs. I also zeroed in on instantiation as I had a huge problem where my console controller was trying to run a general model (i.e TOAHModel()), but now I understand that to create an instance of the game I had to take one particular case that inherits from the class, so for example game1 = consolecontroller(4) which was then passed onto TOAHModel and instantiated as one instance of the TOAHModel class. The TA really helped with this.

Lastly, on a1 recursion. Originally I thought I had to establish a base case for the Tour min moves function M(n), but a friend suggested a better approach (I thought). 

Instead of working backwards to the base case, we built 2 loops that accumulated the i value giving us the min moves value, and a list of the corresponding Ms. So this was really like a reverse recursion where we built the list going forward, meaning that to solve n = 6 you need to know all the previous ones, but they had been built up for you. This really interested me as I think in this instance a simple loop structure accomplished the same task but in a way that seemed way more intuitive to me. In terms of OOP, I mean I was surprised to see that there may be more than one approach and that everything I've learned in class is really a tool, to be used depending on what the situation calls for.

Finally, I've found a much quicker way to deal with raising assertions, using 1 or 2 lines and an assert condition with a comma and the message following after.

Feb 6: a1 and recursion.

This week was very productive as my partner and I really got into a1. We've written the raw functions and the whole thing looks functional; now comes the debugging. Overall I really liked this assignment for how it made us check the relationships between different classes. Throughout this I think I really saw the value of OOP, and the whole 'system' really appealed to my intuition. 

The lab was even better, and I really liked that they gave us super simple examples. Now I'm very curious to see how a more complex recursion would look, in the sense that in terms of efficiency this really appeals to me. My partner and I did the extra exercises at the end of the lab, and even started the string reverser recursion (which fascinated me the most). 

Ive gotten better at syntax, defining classes and functions, and all the stuff that was troubling me at first. I'm worried for the midterm as I haven't written a paper programming test since 2010 and I still find myself having to resort to google when implementing things. On the other hand, I've been really surprised at how helpful all the TAs in this department are (meaning, in my major, this never happens), so I think it would be stupid on my part to not use them as a resource. Namely, I'm going to ask someone about __init__ because I am still struggling with it. I get what it does, what instantiation is, etc, etc, but I need to understand, algorithmically, what the implementation looks like in my mind. (For example, in a1, it says that my use of init for TOAHModel is a syntax error and I have no idea how to debug it as it looks no different than  the way they used init for cheese.).

In any case, I really liked the methodology of this assignment, because while it was a simple task, working backwards from the fully functional code was a really cool way to learn it; in some sense, you can't do this without a thorough understanding of what's going on . Anyway, I'm most stoked for the recursion part, so we'll see !

Week of January 29th, 2014: Exceptions, Assert, and a1

I'm super stoked for assignment 1; after reading up on the TOAH I've been curious on how to program the 3rd stage in such a way that the code can find the optimal solution, but I still have to look into that. Right now I'm supposed to implement the actual game loop, and while I understand and can visualize the control flow in  my mind, I am still somewhat uneasy calling things from the TOAH.py. But I hope to figure that out as it develops.

I also really liked this week's lab; unfortunately my partner and I got much too carried away with testing (we literally wrote tests for every possible case) and hence couldn't do the second half of the assignment, which I wanted to see as it also gave a more intuitive way to think of OOP. The definition on the open source website really fascinated me as it said while other programming languages write an explicit function/definition for things, OOP makes these a part of an actual class; for example in my kitchen I do not think of an individual "toast" procedure but rather conceive of it as a part of my toaster. For me this is somewhat shocking as I've learned all previous languages with a counterintuitive, somewhat 'untrue' conception of how to program and implement operations (in the sense that I see now reality is closer to OOP). So to see that Motorcycle class inherits from the original class was very cool for me, and it also resolved my previous problems with inheritance, classes, and subclasses. So again, it's a shame we didn't get to it ! We both vowed to ask our TA earlier next time.

In any case, I am also very curious to see where OOP implementation would be preferable to non-OOP implementation in the real world, especially in anything related to statistics or finance. From what I've seen, R is very popular for any economic analysis, while python's ability to handle text is very advantageous. But what about other applications, especially regarding big data ? I will investigate this as the semester goes on. 

Anyway, onto a1. Should be cool !