Slog#10

             This week I continued to learn about many sorting methods - from the most optimal to the worst. In lecture, we compared runtimes of various sorting methods and determined the runtime at the best case and the worst case. Comparing sorting algorithms, you see that some preform optimally under certain conditions like a small or random list, while other sorting algorithms excel at sorting longer lists when compared to others (like sorting algorithms that are logarithmic outperform those that are quadric by a long shot). With this in mind, I always wondered if there could be a hybrid algorithm that takes the best characteristics of two algorithms. It turns out that Timsort does just this, it is a hybrid sorting algorithm derived from insertion sort and merge sort. At the worst case, Timsort is within big O of nlogn and at best case it has a constant runtime (within big O of n). In the lab this week, I had to return an inorder linked list that shows the tree from the furthest left node to the furthest left, to do this we used two helper functions within the main function and recursion. For the second part of the lab, we had to write a method for the longest path, I found this to be more challenging. This week was all about sorting algorithms. 

         This week I completed my homework exercise #3 - part a and b. I found part b to be easier. For this I used 3 functions to help with the main function sum_to_deepest which had to return the sum to the keys from the root to the deepest levels leaves in a TreeList. As for part a, the function make_tree had to construct a tree when given the a preorder list and an inorder list. To start, I created the functions preorder and inorder which took a TreeList as their parameters and then returned the corresponding preorder and inorder list. This helped when making the example calls and helped to better visualize the tree. The function make_tree consisted of many conditions to satisfy all the simpler possibilities, and then recursion was used to satisfy the more complex trees. Part a took the longest because I had to understand exactly what was happening with diagrams. In the lab, I continued to alter linked lists by doing the same things in various different ways. In the lectures, we learned about sorting a list using various sorting methods and considering their base case, worst case, and predicting how well they run with lists of different sizes. 

        This week we continued working with and manipulating linked lists. The lab this week seemed easier because I can more easily visualize the structure of a linked list. I find that the simplest way to understand linked lists is to visualize it in its connected form as lists made up of an item (value) and the remaining list (rest), for example: BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, BTNode(12, BTNode(10, None, None), BTNode(14, None, None)))) Another way to visualize a linked list with more clarity is: 

|1-|-->|3-|-->|98-|-->|5-|-->|77-|-->|4-|-->|X-|

However, to me, it is important to view the list as being linked with a head that so the first example is more clear. Visualization is very important as I am working on my Assignment 2 part 1, where I have to set up a Tree classes, without much implementation, other than __init__, __repr__, __eq__. This involves mainly planning the Tree. In lectures this week, we continues learning about linked lists and I learned a new way to represent a list - by flipping a Tree on its side. I had continued practice with changing linked lists in various ways. 

Recursion - Slog 7

        Recursion is the act of repeating something constantly until a conclusion is reached when it meets a specified requirement or it continues infinity. In computer science recursion is used to make a problem simpler by consistently reducing the problem to a more clean and strait forward one each time. A conclusion is reached when the smaller and smaller problem reaches a base case, a condition that exits the recursion. Without the base line, python will call the function until it runs out of memory and the program crashes. I remember the function that was taught in CSC108 - is_palindrome, this function checks if a word is a palindrome ( is the read the same forward as it is backward) I found the same example using recursion:

def is_palindrome(word):

if len(word) == 1 or len(word) == 0:

return True

else:

if word[0] == word[-1]:

            return is_palindrome(word[1:-1])

        return False

The base case is this function is the first if statement which checks if the word in of length 0 or 1 which is automatically a palindrome. Otherwise, if the character at the first index is equal to the character at the last, this is where recursion steps in to make the word smaller. If the word is ‘hello’ -> this returns False. If the word is ‘racecar’, the second statement is true and therefore the string ‘aceca’ goes through the function again. Then ‘cec’ then ‘e’ - this is where the base case is reached and the function exits and returns True. This is how recursion makes the problem simpler and simpler each time until it can be dealt with easily with the first statement. I find that this example makes it easy to understand recursion especially for me because I am very new to this concept. However there is a much easier way to write this function by simply reversing the given string and comparing the result:

def isP(s):

a = s[::-1]

    return a == s

        As the level of difficulty is increased, the use of recursion in your code will simplify seemingly difficult tasks using repetition as I found with the Tower of Hanoi from assignment 1. A recursive function makes a call to itself within the function body. When you visualize the execution of a recursive function, you will se that it repeatedly goes through the function over and over until the base case is True. After you reach the base case, you run out of lines in the function and it does an implicit return to the previous value which returns None - this makes the activation frame on the stack go away. This continues until all frames are gone.