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.