Sorting and Efficiency

  We've reached the topic of sorting algorithms and their efficiency. There are factors in our code such as nested for/while loops which increase the run time of a function. To represent the efficiency of a function, we've introduced the "Big O notation" which describes the performance/complexity of an algorithm. For example, an algorithm with O(1) means that it will always finish executing in the same time no matter the input size. O(n^2) shows that the algorithm performance is proportional to the square of the size of the input. The same goes for O(n^3), O(n^4) etc.

  Some sorting algorithms introduced this week include selection sort, merge sort, and quick sort. Quick sort's algorithm works in the following way:

1. Finds a random "pivot" element in the list
2. check if the first element of the list is less than the pivot element. If it is less, then move to the left side, if more, move to the right.
3. Quick sort is then called again on both the right and left side.
4. once sorted, left side + pivot  + right side.

The run time of quick sort is O(nlogn)/O(nlogn)/O(n^2) with the run times representing best/average/worst cases respectively.

Merge sort takes the list and divides it in half. and then merge together the two sorted lists.
The run time of Merge sort is O(nlogn) for Best/Avg/Worst case run times.

Selection starts at the beginning of the list,  swaps the smallest value in the list and swaps it with the List[i]. This continues until the end of the list. The run time of Selection sort is o(n^2) for best/avg/worst case run times.

The topic of Big O and algorithm analysis tie in together nicely with what I've been learning in CSC 165h.



     

Week 7

   This week featured some more linked lists. The idea of a linked list did not stick with me at first, but after drawing pictures and help from the T.A's, it became clearer. We think of a Linked list as a group of nodes which represent a sequence. The following illustration of a linked list shows how it works where the numbers are the values and the second box is the "rest" of the list which is basically a "link" to the rest of the list.
[1][]-->[2][]-->[3][]-->[]

   The last empty node being the end of the list. I found the lab for this week much easier than last week as I had a better understanding of the linked list and once my partner and I realized how the getitem method in the linked list file worked, implementing the ones that were asked became an easy task as they were all similar in structure to the __getitem__ method and the way it handles it recursively.

  The assignment part 1 involved creating a Regex class which I find acts like the tree class that was given in the notes. The implementation was similar but with the appropriate conditions. I don't feel too confident about what I submitted as it feels too "big" and inefficient and i'm sure there were things that I could have done to shorten the code.

 My goal is to once and for all understand fully how to create recursive functions and list comprehension.

week 5

This week featured some more recursions. The lab work for this week was much tougher than previous weeks. I find myself having more and more problems dealing with recursive functions. Though the concept is clear in my head, the act of implementing what I want becomes the issue. Also, the first assignment is also in the works. It's definitely tricky but seems do-able nonetheless and also a bit of fun in my opinion. Mid term week doesn't help much either in terms of finding the time to do everything but it'll get done.

Week 4

   This week featured some more recursions, inheritance, and exceptions. Once again, my programming background is little to none so everything that I've learned so far is completely new. I liked the idea of inheritance which seems very convenient when making classes which have similar properties. My instructor really wanted to have us get familiar with what recursions are and what I've gathered is that you basically call the same function that you're defining to basically repeat a process until the property you want is fulfilled. Everything has still kept me interested in this program and hope it continues to do so.

Object Oriented Programming.

   Csc 148h is definitely a step up from the 108 course that i took last semester. Not only did I find the labs more difficult, but the lectures have a lot more in depth material to cover. With my background in computer science being little to none, I find i'm traversing into new waters with every lecture I attend. Some interesting things that stuck were the stack class and raising exceptions with python. I found those to be neat things to work with in the programs and learned new methods. I'm looking forward to the lectures in the future and learning new things every week.

test

test