Big O notation is a somewhat complex idea for me to wrestle with, or it initially was at least, but after spending a decent amount of time learning about it in 165 I have come to a decent understanding of it by the time we began to discuss it. Essentially Big O seeks to describe the worst a program's runtime can possibly be, given constant sums and factors of difference (essentially selecting the highest order term such that choosing a lesser order term, regardless of constant multiple, would still be faster than the program given a high enough set of inputs.
For me it was helpful to observe graphs of the different types of inputs and how big-O big-Omega and big-Theta functions would compare to them. This seems like the simplest way to intuitively understand runtime analysis, in my opinion.
Sort Algorithms are numerous though there are a couple of categories that they typically fall into. We have looked at Selection, Insertion, Bubble, Merge, and Quick Sort.
Selection seems only to be a good idea to use if you are certain it will only be run over extremely small lists of data, the algorithm runs extremely slowly by seeking out smallest items on each iteration and returning them to the front, but this obviously creates a problematic runtime as it must traverse the entire list one time per item in the list. Not a recommended sort in most contexts
Insertion is somewhat similar to selection but iterates the opposite way, running through the sorted portion of the list to insert each subsequent item where it belongs within that sort, therefore only traversing the unsorted list once (one item each time) and only traversing the entire sorted list when the next selected item is larger than all existing sorted elements. Intuitively this makes it actually run slightly slower on already sorted data, and it is not a large improvement over selection, having a similar general runtime. Also not typically recommended.
Bubble sort is the worst sort algorithm. Do not use. Must traverse entire list comparing pairs of elements to move the largest to the back on every iteration. Very unwieldy. We have been told there are situations where it may help but none that I have yet seen.
Merge Sort is an efficient algorithm which splits the list and sorts sides separately. It can generally be an effective algorithm to use.
Quick Sort seems the best of the default choices we have been presented with (aside from builtins) as it can repeatedly split and sort smaller lists, combining them back together into a whole in a very effective and time efficient matter.
Friday, 6 December 2013
Overview of Week 12
This week of the course was perhaps one of the most interesting as it has relied on our ability to link together many of the previous concepts of the course in the creation of a complete binary tree type. This was a special subclass of a regular binary tree in which each depth must be filled before any nodes at a greater depth can be added, and nodes are populated in a specifically left to right order, then top to bottom, from the root.
This required extensive knowledge both of recursion and trees which have been some of our primary topics of discussion throughout the semester. It also provided an easy and reliable way to ensure trees are populated in a specific way, which could aid us in future use of trees, if we need to be able to examine trees in a parallel order, if we have access to the list of values, in the order they were populated into a complete binary tree we can bypass our usual methods of traversal and write a much simpler method. Very interesting stuff!
This required extensive knowledge both of recursion and trees which have been some of our primary topics of discussion throughout the semester. It also provided an easy and reliable way to ensure trees are populated in a specific way, which could aid us in future use of trees, if we need to be able to examine trees in a parallel order, if we have access to the list of values, in the order they were populated into a complete binary tree we can bypass our usual methods of traversal and write a much simpler method. Very interesting stuff!
Overview of Week 11
This week we spent the majority of our time invested in the exploration of the property function in order to encapsulate classes and prevent outside interaction from the user end. This seems like useful knowledge as Python is somewhat notoriously open with its code (Professor Heap's nudist colony comment comes to mind) and having at least some way of shielding it against direct user interaction provides both a helpful way to keep some code at least partially private and to provide some comfort to users who have come to Python from another programming language which likely has higher standards of privacy and user-code separation. In that sense, I found it very useful to learn about, having a background in BASIC and web-side design.
Overview of Week 9
Sorting Algorithms and Time Complexity were the main topic for this week, which I found to be relatively easy. The sorts we discussed were all covered in 108 last year and Big O notation has been the topic in 165 for the last several weeks. It was good to get a fresh perspective on them, but nothing struck me as overtly complex or beyond quick understanding.
Also this week was the conclusion of Assignment 2. Regexes are an interesting format though not one I immediately see the practical use for. In theory however their ability to specify various binary representations and demonstrate applications of recursion and linked lists was very helpful to comprehension.
Also this week was the conclusion of Assignment 2. Regexes are an interesting format though not one I immediately see the practical use for. In theory however their ability to specify various binary representations and demonstrate applications of recursion and linked lists was very helpful to comprehension.
Overview of Week 8
Binary Search Trees were a primary topic for this week, and understanding of how to effectively traverse a tree which has its elements sorted by side (lesser elements form the left children of each node and greater elements to the right). This also proved an important concept to me personally as it allowed me to more quickly understand recursion by thinking of binary search trees and their division of sorted elements in a way similar to the merge sort algorithm, which eventually helped me to link various concepts through trees as a recursive structure and gain a better understanding of recursion in general - I wonder if this conceptual link may also aid other students in understanding.
Week 7 Overview
Linked lists have been the primary topic of the week, although I have some trouble understanding instances that would render them preferable to using the more versatile binary trees. They are also more volatile, as destroying the reference to the root node of a linked list will cause Python to destroy the entire list as the whole set of values is determined solely from reference derived from the preceding value, in a trail leading from the root down to the last value.
Personally I do not see myself using this data type outside of assignments where I may be compelled to though perhaps there are additional circumstances that I have not yet learned about in which the linked list may be preferable.
I haven't had a chance to closely examine Assignment 2 and the properties of regexes yet but some of my friends in the class have told me they feel linked lists may be pertinent to the solution.
Personally I do not see myself using this data type outside of assignments where I may be compelled to though perhaps there are additional circumstances that I have not yet learned about in which the linked list may be preferable.
I haven't had a chance to closely examine Assignment 2 and the properties of regexes yet but some of my friends in the class have told me they feel linked lists may be pertinent to the solution.
Overview of Week 6
Our primary topic for this week was the introduction of binary trees. This is a special type of object, and one that ties closely to the concept of recursion. Binary trees are defined recursively in terms of parents and children, filling in levels of the tree from root through branches down to leaves. This type of data structure can be a useful one for search and sort algorithms, as well as being more practical than a linked list (in most cases) for relating pieces of data to one another, especially since most of the linked lists we've used have only been able to refer to itself and a "next" value, and I don't think it would be possible to construct a type of linked list such that it would refer to anything more than two values (previous and next).
With trees on the other hand, referring to the parent and children provides a possibility of at least 3 references for a node with 2 children, and if we were to construct a tree that allowed for more than 2 children an even larger web of references would be possible.
Furthermore, traversal of trees is best accomplished recursively. We have looked at inorder, preorder, and postorder traversals of binary trees, and it's been fairly easy to see the potential applications of each. Postorder seems like it would be the least used, although still relevant depending on the case. What is important to realize is that as much as we are learning new things about computer science, we are also learning new ways to look at, think about, and process the things we already know how to do.
With trees on the other hand, referring to the parent and children provides a possibility of at least 3 references for a node with 2 children, and if we were to construct a tree that allowed for more than 2 children an even larger web of references would be possible.
Furthermore, traversal of trees is best accomplished recursively. We have looked at inorder, preorder, and postorder traversals of binary trees, and it's been fairly easy to see the potential applications of each. Postorder seems like it would be the least used, although still relevant depending on the case. What is important to realize is that as much as we are learning new things about computer science, we are also learning new ways to look at, think about, and process the things we already know how to do.
Object Oriented Programming
Although we take this development somewhat for granted today, conceptualizing object-orientation before it existed must have been like trying to visualize the fourth dimension. This concept was entirely revolutionary in the writing of code as it gave us the ability to go beyond the simple commands involved in writing functions and variables, indeed we now have the power to surpass this level of code on a truly massive scale.
To see the beauty of this simplicity - we can examine even the language that we use! Python itself would be impossible if not for object orientation, and all the simplicities that Python brings with it would need to be hard-coded wherever they were used. Simple things like integers, strings, floats, lists would all need to be defined explicitly in our code whenever we wanted to use them, before we could even start to run functions using them, or worse, if there did not even exist a framework for defining objects, we would need to merely impose the restrictions associated with various object types onto any input to our functions, or perhaps more lazily just allow them to fail if given improper inputs.
Object orientation has allowed us to bundle special properties and restrictions with private functions that will operate especially for the object in question, and with this we are able to write massive frameworks, and more importantly to import existing objects and constructs that we have previously written. This is one of the easiest parts of Python, it has a huge number of predefined objects and simple tools for creating more that allow us to easily develop shortcuts and embrace the cardinal programming virtue of laziness, by simply writing implementations and then being able to reuse them in any instance where we require the same types of objects again, and that is a truly gargantuan advantage over implementing all of these myriad objects and properties on an individual procedural basis.
To see the beauty of this simplicity - we can examine even the language that we use! Python itself would be impossible if not for object orientation, and all the simplicities that Python brings with it would need to be hard-coded wherever they were used. Simple things like integers, strings, floats, lists would all need to be defined explicitly in our code whenever we wanted to use them, before we could even start to run functions using them, or worse, if there did not even exist a framework for defining objects, we would need to merely impose the restrictions associated with various object types onto any input to our functions, or perhaps more lazily just allow them to fail if given improper inputs.
Object orientation has allowed us to bundle special properties and restrictions with private functions that will operate especially for the object in question, and with this we are able to write massive frameworks, and more importantly to import existing objects and constructs that we have previously written. This is one of the easiest parts of Python, it has a huge number of predefined objects and simple tools for creating more that allow us to easily develop shortcuts and embrace the cardinal programming virtue of laziness, by simply writing implementations and then being able to reuse them in any instance where we require the same types of objects again, and that is a truly gargantuan advantage over implementing all of these myriad objects and properties on an individual procedural basis.
Recursion
Recursion was a principle that, upon my initial introduction to it completely blew my mind. I had no idea whatsoever how to be sure that it was working and while our Professor's assurance to "trust in the base case and write the rest assuming it works" would eventually prove to be exactly what I needed to do I found myself still instinctively tracing every call with my mind just to be certain.
What I didn't understand intuitively was how recursion would help, how it might be any better than iteration (Edit: As of Week 8 this is certainly more apparent, it may help in the future to use this lab earlier so that students become more quickly aware of the benefits of recursion).
The real breakthrough moment for me in understanding how recursion operates was when I was able to break it down in more of a lateral sense. Rather than looking at repeated self-calls and analyzing their correctness, I was able to see a program that would call itself, and simply subdivide the problem into a number of sub-problems proportional to however many recursions must be evaluated to reach the base case. Indeed one of the easiest ways I found of understanding it was to compare and contrast with divide-and-conquer algorithms, like merge sort for example, or binary search. Any programs which run in logn time bear a certain similarity to recursion, at least in the way I tend to conceptualize it, and I wonder if anyone else has also made this connection to facilitate their understanding.
What I didn't understand intuitively was how recursion would help, how it might be any better than iteration (Edit: As of Week 8 this is certainly more apparent, it may help in the future to use this lab earlier so that students become more quickly aware of the benefits of recursion).
The real breakthrough moment for me in understanding how recursion operates was when I was able to break it down in more of a lateral sense. Rather than looking at repeated self-calls and analyzing their correctness, I was able to see a program that would call itself, and simply subdivide the problem into a number of sub-problems proportional to however many recursions must be evaluated to reach the base case. Indeed one of the easiest ways I found of understanding it was to compare and contrast with divide-and-conquer algorithms, like merge sort for example, or binary search. Any programs which run in logn time bear a certain similarity to recursion, at least in the way I tend to conceptualize it, and I wonder if anyone else has also made this connection to facilitate their understanding.
Subscribe to:
Posts (Atom)