Week 12 End of the Line, Hashing, Merge and Quick sort Big O analysis

This final week we finally finished off our Big O notation analysis by covering quick and merge sort. We began by calculating the time complexity or 'steps' involved with each program and then we built ourselves some intuition about the upper bounds of program running time before finally assigning a Big O notation to the program.

Time Complexity Big O

For instance let's assume n is equal to the length of the input into the program, and a program's time complexity is 3n^2 + 2. Then this inequality will hold:

3n^2 + 2 <= cn^2

The c on the right side is some real positive number (basically any possible number above zero).
The purpose of this real number is to account for all the constants that are added or multiplied on the left hand side - so that the left side is 'upperbounded' by the right.

The n subscript o on the graph represents a 'breakpoint' where the red line (function) becomes the upperbound of the blue function. Any value of n past this point will always follow the relationship of:
f(n) <= cg(n).

Similarly, there will some breakpoint for 3n^2 + 2 <= cn^2 as well, where cn^2 will always be greater or equal to 3n^2 + 2.

This was a very crucial piece of information for the class, because it bridged our intuition about taking the largest power as the Big O, and our mathematical sensibilities.

I think this was one of the few times that CSC165 played any sort of role in CSC148; anyone taking that course would not only understand the definition of big O, but be able to formally prove and disprove even the ugliest looking time complexities using underestimation and overestimation. An ego boost for those students I'm sure.

All of this time complexity analysis allowed us to parse the running time of quick and merge sort quite fluidly. I personally gained some intuition about merge sort besides the fact that I knew that the 'breakdown' step of mergesort had a running time of logn due to the fact that the input was broken in half each step until you have reduced the pieces to just 1 element, and that the 'merge' step had a running time of n.

Hashing

Next we talked about hashing and its ability to make lookups, insertion and deletion even faster than quick sort and merge sort. The reason for such quick operations is that each element is 'hashed' or given some kind of unique numerical identifier via a function. I really wish this topic was taught before assignment 2 was due, as it would have helped people speed up their program's running time. I personally discovered this myself, and utilized an Ordered Dictionary for faster lookups and insertion.

We also lightly covered hash collision where some items might receive the same unique identifier. One method of dealing with it was chaining, where  a kind of linked list situation occurs and mutliple items are 'filed' under a unique ID number.

The other method of dealing with collisions is 'probing', and from what I can understand, it basically finds the next empty space in the hash table and places the item there.

Final Thoughts

Overall I feel like the course was a good step up from CSC 108, as it moved beyond mastering python mechanics, to working with interesting data structures and problems (recursion and assignment 2 puzzle solver building). 

I think the high point for me was figuring out how to make both depth first and breadth first solve work in assignment 2. I must have some kind of masochistic element within me, because I probably hated figuring out what was wrong until the point of the program actually working. Then my brain did some acrobatics and rewired itself to interpret the past hours of debugging as enjoyable.

Key lessons learned from that was understanding what makes a program slow down or speed up, which depends alot on loop usage, data structures (lists versus dict, dequeues versus regular), and fully understanding tree structures and linked lists.

I say linked lists because that was entirely crucial to doing the solvers properly, as you had to build a single linked list using a 'parent' attribute. 

All in all, it's just really great assignment design to incorporate almost everything we learned so far in 108 and 148.

Week 11 SLOG Time complexity review, Assignment 2 interview prep, A quaint week 3 to 11 SLOG review

This week's material served to solidify concepts about running time from last week, as well as optimization techniques gleaned from building our programs in assignment 2. Though lighter in complexity (what a pun) than other weeks, it was no less interesting and dare I say it, more relevant in its possible application to other CS courses we are taking (IE csc 165). The second major point of relevance this week is the assignment 2 interview preparation, which I'll also dig into and lay out the strategy I'm going with during my time slot.

Running Time Lecture

Regarding the lecture we dived more in depth into algorithm efficiency utilizing both slides and in-class activities. The professor began in a methodical manner first by introducing a variety of different time complexities with constants and then systematically correcting us of our first glance intuition. For instance many people were perplexed at the idea of time complexities like 5n and 10n not having any difference in terms of worst case running time, however a quick sketch of the functions with the assumption of a massively huge n value (length of the input parameter) helped clarify things.

The second phase of the lecture had us tackle various sample programs and guess at their worst case running time in terms of Big O notation. The trickiest examples involved double loops with the loop variable increasing by an exponent, and programs that had if condition blocks with for loops included in them for added confusion.

It seems that the best technique to handle eccentric looking programs is to test with small values of n to get a sense of a pattern and then figure out whether a loop is running logn times, n times, n^3 etc; additionally Big O concerns extremely large values and therefore one should not be lured into certain if statements based on how much code is within it as shown in this example:

I personally fell prey to the elif n > 97 statement and concluded the running time was n, when really it was constant. Never again will that happen I swear!

Despite this week's material being less intensive than other weeks featuring recursion, I felt like it had more relevance due to the fact that I had been optimizing code for assignment 2 frantically. First by using better data structures like deque and ordered dictionaries and secondly by reducing as many nested loops as possible. For instance my grid peg solitaire used to have an n cubed running time because of a misplaced loop, but I managed to cut it down to just one nested loop bringing it to n squared running time. 

Assignment Interview Preparation

The biggest tips I found regarding programming interviews is to understand how to translate programs into either intuitive diagrams or simple English. In addition, many people recommend that you are also able to dive anywhere in the code and be able to describe what that block of code actually does in the context of the entire program. 

To better prepare myself I met with group members for a kind of 3 way interview session - we challenged each other to explain different parts of the assignment and occasionally smirking at the kind of comments we left in (ie: one member loved putting in Dark Knight Rises movie references). One habit we worked on was our penchant for getting bogged down describing the code on a micro level rather than a macro one - that is not always relating a segment of code to the overall functionality of the program. Thankfully we ironed such interview wrinkles out before adjourning our drill session.

For the interview I'm hoping that a big picture approach to explaining the code will allow me to stay within a 5 minute time-frame. However, just incase the interviewer decides to talk about one block of code for 5 minutes I've also familiarized myself with every swap, loop, or assignment statement. Bring it on Noel.

Week 3 to Week 11 Reflections

I began my SLOG and CSC148 journey expecting increased difficulty and deeper thinking, and I wasn't wrong. As we got into more interesting data structures like trees and linked lists I found my CSC 108 skills becoming less and less predominant and more akin to a reinforcing scaffolding - it was soon clear that I had to develop different mental tools to fill the rest of the 'building' out. However difficult it was to utilize the new data structures and recursion techniques, I feel like the course has forced me to evolve from a fledgling computer scientist to a less... helpless computer scientist (not so dramatic of a level up I know!).  To put it another way, the recursive and tree elements of this course are analogous to learning counter attack and 'tell' reading techniques from the martial arts world while CSC 108 taught the mechanics of punching and kicking.

Week 10 Assignment 2 Crunch

 This last week has been the most interesting so far... mostly because of what A2 pushed me to do.

I had to figure out how to speed up running time by removing unnecessary loops, using fast data structures like ordered dictionaries and deque, and I also had to learn how to implement search algorithims within the context of a puzzle solving problem.

By using queues I managed to do both searches iteratively. I got to admit the exercises from class, as well as the discussion on Piazza really helped me design a search algorithm that on first glance is incomprehensible, or atleast leagues more difficult than simply using recursion (for DFS).

However, when it all came together, the concept of iterative DFS is just insanely simple. It's simply the queue system of BFS with a one statement difference - children are prepended instead of appended.

As for the lecture material for this week refreshed some concepts of the deletion BST method and we touched on the differences between different Big O running times from constant to exponential. What was emphasized to us (with some humor) was how drastically poorer you could make your program run if you were to use one too many loops.


Overall, I enjoyed the fact I liked how CSC 148's material and lessons really came together in this final assignment and week's material, and I really feel like I improved my programming/logic skills.

Week 9 Recursion, tests, assignments

A more straight forward accounting of CSC 148's material... 

This has been a packed week for csc 148. We had to drill ourselves with recursion exercises to deal with the second test and now we have to utilize those honed  recursive thinking skills to handle assignment 2.

A big upside is that the preparation for the test and the material taught in class has greatly alleviated the difficulty of the second assignment. The tree exercises in particular are very helpful in conceptualizing the solving of the assignments.

I've yet to fully delve into the newly taught deletion methods of a Binary Search Tree, but I'd imagine that mastering it will be crucial to scoring well on the final exam. Intuitively the program can be broken down into these parts:

1.Look for the node which holds a data value which is the same as your data paramter:

You utilize the BST property of the tree and search in logn time by putting in if statements to look left if the current node being looked at is greater than your data value, look right if the current data value is less.

2. Once you find the node in question 'X' (with the right value), you must check the left child if it has one, and right if not.

3. If there is a left child, you look at the subtree connected to that node and put the maximum value in X's place. If there's no right child you simply move the right child into X's place. Doing either of these actions will preserve the BST's property.

4.Delete nodes that you've moved into X's place.

If you asked me to do this at the beginning of the course, I would be baffled. However, despite knowing how Binary Search Trees work, I'm still amazed at how algorithims can take advantage of it.

This video in particular was very helpful in solidifying concepts learned in class:

Final word for the week: compared to csc 108 the topic of BST's and these new delete methods are much more difficult, and dare I say it, maybe even harder than everything in that course besides the final exam.

Week 8 Binary Search Trees and more recursion

This week we were tasked with more tree structures and the usage of recursion within them.

In the lab we worked on recursion methods that involved a tree which has its children in a list. A crucial aspect of mastering these types of trees is to know when to place items inside or outside the list comprehension square brackets.

Personally I feel like novice when trying to formulate these recursion functions, often relying on a bit of trial error via the interpreter. So far I've been using this visualization to better imagine recursion processes:

Additionally, it is useful to think of a very short 2 level tree to get a handle of what the base cases and recursive cases should be. The benefit is that you can easily see your program 'resolve' itself, or hit the base case with only one step. If your program works for this simplified example chances are it'll work for all other levels. 

Other things to look out for are fringe base cases and being wary about nested lists. For the former problem, inputs like like empty trees or None require a special base case to handle them. Regarding nested lists I realized that I should be careful about using them as each recursive call combined with a list comprehension will produce a nested list each level that is returned. The way to get around this is to either use a helper function 'gather lists' which flattens a depth 2 list to a single level, or just not have base cases return list objects at all.

It's funny that these kinds of tips can't really be taught and appreciated without actually diving in to the programming. 

In addition, another useful technique that I learned that helps with finding values to certain depth levels is to use a function that decrements depth each recursive call. For instance Call(tree, n - 1) paired up with a base case of 'if n == 0' would allow values at a desired depth to be manipulated.

Week 7 Recursion and Trees - Danger Zone

This week we continued with the concept of recursion and touched briefly on Trees. Of the two concepts, I believe recursion to be the more difficult one-primarily due to the difficulty of finding an incremental step that could be folded down into a base case. The base case however isn't too difficult to discover right off the bat.

Regarding the topic of recursion I have problems imagining an incremental case that will collapse neatly into the base case. Am I just too much of a dullard to grasp this concept quickly? For instance, I can't imagine how I'd handle the permutations function recursively (posted on the website), and I'd imagine that I will experience the same trouble with more complicated examples. Luckily our professor structured the lesson to address such depressing thoughts. He started by framing recursive problems like Factorials and Fibonacci as a tree, and traced the path downwards with arrows; then subsequently retracing upwards to show the effect of a function 'wrapping' itself up to produce a single value.Professor Amir then moved onto introducing a technique which depicts the function calls as elements that are being put in a 'stack' - I found this very useful , but I think I will gravitate towards making tree diagrams more often than this formal method. I think as long as I am consistent with the way I depict function calls I'll be alright.

Regarding Trees, he only touched on a few applications of it but it illustrated the benefits of recursion. He showed several examples which involved calculating the length of trees, the number of branches in a tree, the max branch per node and the number of children - all of which made use of recursion and list comprehension to solve it neatly. I could only imagine the nightmare of coding these problems with loops-I shudder at the thought. Additionally, the ideas of 'parents' and children were introduced and I found that previous lectures on nodes quite useful in understanding this new structure-the trees were simply a collection of nodes that pointed to two 'children'.

Punctuating the discussion of these 2 aforementioned concepts were timed (and presumably marked) exercises that incentivized people to apply the words coming out of professor Amir's mouth. What I discovered is that I need way more practice to be able to answer unfamiliar recursive problems quickly.

Some final thoughts: recursion seems to be the most difficult topic thus far, and the entire course has finally eclipsed the difficulty of 108. Not to disparage CSC 108 but the difficulty of the course came from the final exam which tested our ability to combine all the basic concepts to solve well formed questions; whereas CSC148 starting from at least 1 week ago is leaning towards creativity and much deeper thinking. For now, I think I'll scrounge up problems from some free online courses, notably from MIT.

This particular link: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/unit-1/lecture-6-recursion/ has a good explanation of recursion.

Time to really step up programming efforts it seems, can't wait to see what's coming ahead.

Week 6 Assignment 1 Crunching, Linked List refresher, and Recursion

Interesting week to say the least as an assignment is quickly approaching its due date.

The assignment is definitely more robust then those in 108, and I believe it gives ample practice, especially for those students who crave something to whet their programming lust.

Two interesting topics were discussed this week (though linked lists is admittedly 'old'). Recursion seems to require alot more experience than using the good ol' loop. Some additional thought is needed to properly structure problems into base cases and a 'recursive' case that can collapse the problem down to the base case. I'll definitely be adopting this slowly, before utilizing it heavily. 

I found a great visceral live demonstration of this concept, it's called the Tower of Hanoi problem:

As the course seems to picking up pace, I'll have to increase my efforts towards this course accordingly. For now it's back to the assignment.