Sorting Algorithms

There are many different types of sorting algorithms that can be coded in a program and each offer their advantages and disadvantages. Efficiency is a measure of how the running time of a program increases compared to the load given (n), for example as the size of a list increases.

First there is Selection Sort. This is a type of sorting method where the minimum value is selected and then switched to the first index, and then then next minimum is found and switched to the second index, etc. This sort is very inefficient once the lists grow because it does not cut down the running time because no matter what order the list is in even if it is partially sorted, it has to go through all the values. The efficiency of this sorting method is O(n^2).

Secondly there is Quick Sort. This is a type of sorting method where a divide and conquer approach is taken splitting up the list into smaller sections and then recursively working through the sub parts. A pivot point is picked at random and the elements are sorted to the left if it is smaller, and to the right if it is larger. This method is very efficient as the worst case is O(n^2), which is identical to the Selection Sort, however the best case is O(n log n), which is significantly faster!

Lastly there is Merge Sort. This is a type of sorting method where the list is broken down into single elements first and then sorted into groups of two (L[0] + L[1], L[2] + L[3], etc). After all the elements are sorted into groups of two, the groups are then sorted using the same method into groups of four, this keeps happening until there are only two lists left that are merged together into one. This method has a worst case of O(n log n), which is even faster then Quick Sort because it's best case is better then that (in the cases that the sub lists are already sorted).

Big O Notation

After learning a couple of different sorts available in Python, at first I was wondering why we are learning this as it is obvious that we can choose any of them and they will work perfectly! However, then came the reason, even though to us currently, 1 second is not a big difference when running our code, when you have a lot of different aspect each taking that 1 second and all other functions rely on them, it builds up considerably.

Dr. Heap then showed is different sorts and how they are labeled with Big O Notation and it finally made sense when people online are referring to their codes using O(n) or something like that. Now I understand the importance of logically solving the problems but ensuring that their running time are kept to the minimum when the size increases. Like the Lab when comparing Queues and Stacks.

Assignment Reflection

Finally completed the assignment that was due, and handed it in on time! Having read the instructions and listened to Dr. Heap, I was very scared approaching this assignment as I had no idea what the topic it was covering was about and how to approach it in the slightest way. Looking back on it however, I am very pleased with how it went and after learning thoroughly about recursion, it helped significantly.

At the beginning, I compiled a list of cases from my own examples as well as compiled some from piazza that were contributed by Dr. Heap and some from Chance. After I had these I proceeded to write test cases for the program beginning with the RegexTree construction. After approaching the problem, it lead to itself just being typed out, seemed fairly straightforward and I was actually surprised by the speed in which I was able to code it up.

Then came the match section. That proved to be the challenging portion of the assignment, but I approached it the same way. Thinking about cases and typing them up so I could track my progress from easy to expert examples. I approached the problem from solving very simple RegexTrees a.k.a single RegexTreeNodes. Then approached the intermediate areas such as single BarNodes, StarNodes and DotNodes. Lastly I made sure that all the No

Updated Thoughts

Having the exercise (number 6) made me understand finally how to understand recursion properly. Having to code a couple of methods that could be easily implemented using recursion, I saw how the process of going through the trees works in recursion! Now I face trying to understand and code Regex related methods. Having never heard of regular expressions and not knowing what they are for, the assignment proves to have multiple layers to go through before I can be successful in coding it. Hopefully I can go through the __init__ method soon and it will click. 

So far it has been great in the class and compared to CSC108, this class is so much more about the science behind what we are doing and different approaches to problems which is great and gives so much more experience and tools when faced with a problem. Having looked at job postings recently, there is still so much to learn and I hope that I can take the knowledge I learn in this class and apply it to other languages with ease since I understand the premise (specifically java and C++).

Binary Trees!

Having gone through binary trees and now learning about binary search trees, a lot of the topics we have covered in the course are coming into play. Not only do I have to learn about the trees themselves and learn about the traversing methods that are possible, but also many different applications need to be built into the class which is very rewarding once complete. The functions we learned today were very useful in knowing and it is very interesting in how very simple topics such as if statements can be made (along with a little recursion) into complex searches and deletions from trees. Having this knowledge is very helpful with other topics and I believe that this will be an excellent skill to possess when working with lots of data whether it is on a server or database and knowing the various methods will allow for very easy searching and manipulating once it is up and running.

I am excited to see where this leads to and what other interesting topics will be covered once we near the exam, and in the end, it is very exciting to see the progress that I have made coming into the course (from CSC108) and what I will possess after finishing this course!

Topic Question 1

    Object-Oriented Programming (OOP), is very useful for computer scientists. It is a concept that allows for encapsulation of data within specific sections allowing for functions to act as intermediates between what is given and what is wanted. This allows the programmer to structure their program more logically, and have specific controls for what is allowed to happen to specific data. In contrast, non-OOP is just a long script of instructions that may be broken down into sections but in the end it is globally accessible to the whole program and many bugs can appear because there is no rules to what can be implemented on what data (ex. has no methods like OOP does).

    Recursion is a very tricky topic as previously mentioned in a post. It is the idea of formulating a specific set of instructions under a function, however the main focus is that in the body of that function, it uses itself to calculate a variable it needs to use. This allows the programmer to write shorter code, as the functions can keep going back and calculating instead of writing complicated loops. It is used in solving complex ideas, where one output is needed for a second input, etc. Once this complex idea is understood, it is a very powerful tool in computing, saves a lot of time in analyzing data, and in the end is the most efficient way to solve the problems where it is needed rather then trying to incorporate loops and temp. variables, etc.

Assignment 1 was very difficult, especially the implementation of the Tour.py file. This is my first time learning and implementing recursion, and I must say that it is a very abstract idea that takes quiet a bit of time getting used to and wrapping your brain around it. The assignment itself was interesting in the fact that it is an open ended problem in the world currently and that even the most skilled designers and mathematicians have not come up with a concrete solution. I hope the next assignment however will not have tktinker in it as I know NOTHING about, which made things a lot more difficult to another level then if I would have known at least something about. But oh, well. Things learned from this assignment especially recursion, and even some of the pre-coded areas of tktinker will come in very handy in the future and will for sure improve my knowledge and arsenal of techniques I will have!