Final Post

As we come to end of CSC148 I can truly say the course has opened up my eyes to the great diversity of Computer Science. I have learned about Binary Search Trees, Python list Trees, Recursion, Linked Lists, Sorting and Efficiency along with many more topics. The course has hopefully given me a good foundation for the computer science I will be learning in the future.

Week 11: Sorting and Efficiency

Efficiency is a sought after aspect of almost any action in life. The implementer always wants to ensure the task that they are trying to complete is done in the fastest and most efficient way possible. In computer science it is the same feeling towards programs and functions. A computer scientist wants to make sure that the algorithm they are creating will work efficiently. Sorting algorithms are a good learning tool for observing how time complexity and efficiency are involved in a program. In this weeks lab we did several time tests on various sorting functions such as; Pythons tim sort, quick sort, merge sort, bubble sort, selection sort and many others. we observed the sped of the functions with 3 different inputs from best case to work case. Best case being a sorted list to sort. Worst case being an unsorted reversed list. And the average case being a random list. We saw as various functions worked well with different inputs but also how some other functions decreased in efficiency tremendously. 

The different sorts in the lab all had different O(n) values. O(n) is a term made to represent the limiting value and speed in which a functions divides tasks. Selection sort would have a run time of O(n^2), as it compares every item with every other item in the list to see what element s the smallest. Insertion sort has the same O(n) value because it needs to compare each element with every other item in the list. The run time of bubble sort is also O(n^2), because it compares every possible pair in the list. Quick sort has a value of O(nlgn), although the worst run time is still O(n^2), the function partitions it into two lists continuously,  while returning a number each iteration. Python's Tim sort has a run time of O(nlgn), which it works out through adaptive sorting methods.

Memoization was also discussed in class a way a function could be slower than it could possibly be. This is because of redundant recursive calls such as seen in the fibonacci sequence which calls f(n-2) two times(f(n-l) same value is on next recursive iteration). This is a waste of a call and also a waste of time. For these reasons we analyze programs and their efficiency to develop products that are the best they possibly can be. Sorting has shown me how and why efficiency is so very important as a CS subject.

BST

Binary search trees have always been an interest for me in computer science. From the beginning the topic has clicked with me and I find them to be very iterating data structures. Something new for me was learning how they communicated and mutated into linked lists. Binary search trees are nodes with up to 2 child nodes. where the first node at the top of the tree is the root and the bottom nodes with no children are leafs. Also the node above the current node is called a parent node. The traversing taking places in three ways preorder, postorder, and finally in order. In order is when the left subtree is traversed then the root is placed and right subtree comes last. Pre order the root comes first followed by the right then left subtrees. Finally the post order traversal is when the right then left subtrees are traversed folioed by the root. Traversing is a recursive way to display the tree in a list. Trees are abstract data types that have been used in computer science for many year and also a long time to come.

Linked lists

This week in class we are learning about linked lists. It is an interesting data structure that aeries its own navigation system. The lab consisted of many problems in which we had to modify and alter linked lists. Linked list nodes contain two real elements. The first part is where the data or value is stored and the second is a link to the next node in the list, thus "linked lists". Deleting a linked list would consists of moving one of the pointers to the next node to the node which comes after the the one you want to delete. Visually it is more of a skipping action than deleting. Linked lists have been interesting in the past lectures and labs and I can't wait to see how they will grow with me in the future.

Recursion

Recursion is a tool in programming used to replicate a similar action in a repetitive way. It will break the task down over and over until it is small enough to complete. These smaller tasks which once made up the bigger task will be easier to compute then added up again the bigger task is solved as well.  Some examples that could make recursion very useful tools are problems like; the fibonacci sequence, factorials, and the tower of hanoi, amongst several others. All these problems involve breaking down big numeric problems into smaller tasks, then solving the smaller task. Though recursion does make these more complicated tasks easier to manage it does have its downsides. Recursion is not so easy to understand or write. Secondly there are things about the stack you have to worry about such as stack overflows and such.

Recursion is the act of repeating itself over an over, but this would seem to go on forever. The simple solution o this problem is a base case. The base case is an unchanging condition set in place for when the bigger problem gets broken down enough where it would not make any sense to go further. For an example we can use the factorial. The factorial formula is (n * (n - 1)*...*1). But we know that the special case for factorial is 0, since the factorial of 0 is 0. This would act as our base case in this instance. It will yield our small sections of the bigger problem to at the minimum 0. This giving us a recursive result.

This idea of recursion has been a great milestone in all programming over the ages. It gives people the ability to take great tasks and make them several small easy ones thus making them much asker to compute.

Trees

Trees in programming are a data structure that can take on many forms. They involve linking nodes to each other all originating from a root. A node is one element of the tree. A root is the beginning node. A leaf is a node with no children(no nodes on lower level). Binary trees are trees in which every node can have up to two nodes attached to it.

Traversing is parsing throughout he data in a tree. There are three ways in which you can traverse the data in a  tree; pre-order traversal, in-order traversal, and post-order traversal. Pre-order traversal is when you start with the root then the left subtree then the right. In-order is when you start with the left then the root then the right subtree. Post-order is when you start with the left subtree, then the right, and finally the root.

To end this discussion I just wanted to state that trees are a very useful recursive data structure and they did not pose many difficulties.

Inheritance

These past few weeks we have learned a few different topics. One of them being Inheritance. I feel this is a good way to reduce the replication of code. It saves space and and makes a denser final product keeping the solution tight.

A good example of this was shown through the weeks lab. If you have a main class which holds all the main attributes of something that is Motorized other things can extend of this. For example a car and a motorcycle both contain a motor but they also have unique attributes from on another. So in this case they would both inherit the motor attributes, but the car would have something else specified within it such as four wheels, while the motorcycle would only have two. This example really made the idea of inheritance clear for me.

After doing many examples I have found inheritance to be a great tool for object oriented programming. As the days go on I will go deeper into it and other corner cutting efficiency techniques.