csc148 slog

Hey! This week we looked further into Big Oh and run times.

Last week, we defined Big Oh as:

t e O(g) if there are positive constants c and B so that for every natural number n no smaller than B, t(n) <= cg(n)

Using the Big Oh theorem, we can derive that if t e O(n), then t e O(n^2). This then can be extrapolated to show that O(1) is a subset of O(lg(n), which is a subset of O(n), which is a subset of O(n^2), which is a subset of O(n^3), and so on.

Big Oh is a way of showing us run time. If a function’s run time is in O(n), we can assume it will take n steps. If it’s run time is in O(lg(n)), we can assume it will take lg(n) steps. An example of code run time (in iteration, in this case) can be looked at as follows:

The code above has a run time in O(n^5). This is because the first while loop will run in n^3 steps, and the second will run in n^2 steps, however, when nested as shown, the n^2 step loop will run n^3 times, meaning it will run n^2 x n^3 times, that being n^5.

A summary of the Big Oh theorem with respect to different statements in code is as follows:

# sequences: max(O(each statement)) 

# loops: product of iteration of each loop (what we looked at above)

Hey! This week was short due to Good Friday... Happy Easter!

This week we started looking into efficiency in our programs. This is something I've been looking forwards to, since efficiency is something that matters in the real world (and soon in school)! 

We started out by looking at a Fibonacci method, which would have a hard time finding a number in the Fibonacci method at a high index. We fixed this by adding a seen set, which would be checked each time so that a new instance of the method would not have to be opened if the number were seen previously. This took a huge load off of the hardware and made running the method at a higher index much easier, therefore being more efficient by reducing redundancy in the method.

Following the demonstration of this method of increasing efficiency, we were introduced to run-times and Big Oh. When a run-time is proportional to lg(n) (which in computer science is log base 2) that means, for instance, that in an ordered list, when searching for a value we can “divide and conquer”. Start by dividing the list by two, then again, and again, until the value is reached. Big Oh was defined this week such that: 

t e O(g) if there are positive constants c and B so that for every natural number n no smaller than B, t(n) <= cg(n)

In normal words this means that the function t(n) is less than or equal to g(n) times a constant when n (or, graphically, x) is greater than or equal to another constant.

This week’s SLOG was also a bit delayed due to my heavy work load in school.

This week we looked into mutation with BSTs. The most important thing I learned this week was the management of heavy algorithms, when we were working with making a delete function for BSTs. In lecture, we were told numerous times that we should always set up a series of comments when we have to handle a rigorous algorithm like that required for a BST (The reason for this being that we want to utilize the fact that it is a BST).

Hey! I’ve fallen behind a little bit due to a huge load of assignments and midterms over the past 3 weeks, but I’ll still make sure to keep to date!

Binary Trees are an ADT we derived from Trees, which we learned about last week. Binary Trees are simply Trees, however they only have two children, which are specified in the class initializer as left and right. This allows for us to branch into other types of the Tree ADT, a couple being: the Arithmetic Expression Tree, and the Binary Search Tree. 

The Arithmetic Expression Tree simply allows us to calculate an arithmetic expression through the use of a binary tree. Each parent node is an arithmetic expression while each of the left and right nodes will equate to a number. In it’s simplest form, an Arithmetic Expression Tree would look something like:

   + 

1     2. If we use a function we made in class to evaluate this tree, we would get 3.

This week our class looked into another Abstract Data Type called Trees! Prior to looking at the Tree ADT in CSC148, I had already learned of it in high school, similarly to other topics we've looked at in the course. However, likewise to Linked Lists, my education of Trees from high school wasn't that strong. I had a hard time grasping the whole idea of Trees themselves. I could never see a purpose for them in computer science. After looking at how powerful Trees are in CSC148, I’ve now got an idea about what trees can be used for. 

Trees in computer science are very similar to a tree in real life. For an example, take a family tree. At the top of a Tree there is a node, which is naturally (in computer science) called the <b>root</b>, and this node can have a number of children. These children can lead on to be subtrees, or more simply, leafs. Subtrees are simply another tree taking the node as if it were a root, while leaves have no children at all (as a leaf would not have branches sticking off of it). Trees then have a few important attributes. Trees act in a way where there is no cycles - they do not loop back at any point (as a real tree would). Each tree has a height, which is easily calculated by taking the longest path (sequence of nodes, with edges between each) and adding 1, and a depth, which is the height of the tree minus the height of the node specified, respective to that node.

This last week we went over recursion! When a method is recursive, it calls itself within it’s code. This can be very useful when dealing with nested lists and other abstract data types such as stacks or queues. I went over recursion a little bit last year in Java, however, my class did not go as in-depth as we have so far in CSC148. The most important thing I learned related to linked lists was the formatting of for loops and if statements within a single line. This was done very easily in Java due to it’s heavy syntax (relative to Python!). These single-line for loops are useful for opening multiple instances of a method at the same time with different variables, recursively. 

The week prior to reading week included our midterm, and an expansion of our lessons in linked lists. I learned of linked lists in grade 12 (last year), and up until just recently I haven’t found a reason for linked lists to be used! They’re confusing, take a while to learn, and are not built in to any given language. 

When my class went over them in Java in grade 12, I remember the concept being a little harder to grasp. This experience with the concept really helped me in visualising and using linked lists.

The way I like to explain linked lists is to treat it literally as the name suggests. It’s a linked list! Each element in a linked list is called a node, and are treated almost as a list with two variables, one being the value, and the other being a pointer, which points to another node. 

The reason for using linked lists over builtin lists is the way it is stored in memory. Linked list’s nodes can be stored at any valid point in memory, while lists are stored together in one huge part of memory.