SLOG # 8: Week 10

   This week, we have been discussing about varieties of sorting algorithms in addition to their runtime efficiency. To start the week, our prof explained assignment 2’s function designs based on the interpretations of the assignment 2 PDF. After spending sometimes going over the assignment, we discussed on how default empty list parameters is a parameter that is mutable.

For example:

def f(n: list=[]):

    n += [1]

return n

   If inside a function, we append integer 1 in the list parameter given, then each time when we call on the function without giving the parameter, the parameter would refer to the default list [] first time and store the integer 1 within the list. The reference is kept with 1 added. The next time when we call on f() again after the first f() call, we would expect the return to be [1, 1], since the function will reference to the list parameter n for the default list. Although this would not affect the returned list for non-default function calls. The reference is kept and accessed during the next f() call just like the sample calls below.

>>> f()

[1]

>>> f()

[1, 1]

>>> f([0,2])

[0, 2, 1]

>>> f()

[1, 1, 1]

   This week we focused on studying algorithms such as quick sort, and merge sort as well as their run time. For quick sort, the idea is to choose a pivot point where a list with more than one element can be broken to two lists where the first list consists of elements smaller than the element before the pivot, where the other list consist of elements greater than the pivot if we were to sort the list in ascending order. From the two new sub-lists we created, we perform quick sort on each of the two. Then the first list that is sorted can add the pivot in terms of a list with a single element, and then add the sorted second list. This returned list is the sorted list that we called quick sort on. To maximize the quick sort algorithm, random pivot point should be used instead of a specific pivot so worst case run time can be minimized. 

   For merge sort, the idea is to split the list roughly to two list with length half of the original list if the list given have a length of two or greater. The two sub-lists will then be sorted using merge sort, the two sorted sub-lists will be compared and the corresponding elements will be moved around from first to the second and vice versa. Then the two lists can be added to return a sorted list.
 

   The lab we had this week was based on the continuation of linked lists and designing helper functions. From the lab handout we were asked to create linked lists using binary tree objects given such as using the tree given to create a linked list that is in-order of the binary tree. What was difficult about this lab was how to find a way to link one linked list at the tail of another linked list. My partner and I were able to create a helper function that helps finding the tail of a linked list and reference the other linked list to the tail. 

   This week have been fairly busy because of the csc165 midterm was on the same day of the due day of assignment 2. But on the bright side, this week’s lectures did make me realize the usefulness of recursion, especially in algorithm designs.