Sorting

     In everyday life, sorting means to arrange a collection of elements in a certain way, for example arranging a deck of cards in increasing order. There are many different ways to sort a deck of cards but what would one have to do to sort a whole deck in the least amount of time?

     Through our lectures we learned many algorithms to sort a Python list and which of these algorithms were more efficient when compared to each other. We compared the algorithms using Big-O Notation which counts the number of steps that get executed when trying to sort a list of n items. One of the sorting algorithms we looked at was Selection Sort:

1	def selectionSort(alist):
2	for fillslot in range(len(alist)-1,0,-1):
3	positionOfMax=0
4	for location in range(1,fillslot+1):
5	if alist[location]>alist[positionOfMax]:
6	positionOfMax = location
7
8	temp = alist[fillslot]
9	alist[fillslot] = alist[positionOfMax]
10	alist[positionOfMax] = temp
11
12	alist = [54,26,93,17,77,31,44,55,20]
13	selectionSort(alist)
14	print(alist)

     (code from Interactive Python - Sorting)

     From the code above, we say that the selection sort algorithm is O(n^2) because when sorting a list of n elements, the outer for loop runs n times as with the inner for loop. This runtime complexity is quite inefficient when compared to the Quick Sort or Merge Sort algorithms which have O(nlogn) complexity on average.

     My goal when it comes to sorting is to learn the complexities of the worst and best cases of the algorithms we've learned, and most importantly, to understand why it has that specific complexity. To achieve this I will practice tracing the code for the algorithms, trying to notice the lines of code that get executed the most (such as the nested for loop in the example above). 

A Revisit to Recursion

     In the beginning of the course we were introduced to an important concept of programming called recursion. Just to remind ourselves, a recursive function is one that calls itself and is used in order to solve a problem which can be broken down into smaller instances. A recursive solution is found by first solving the simplest instance (or base case) of a complex problem then using that solution to find a solution to a more complex instance, then using that solution... and you get the point by now.

     Since our introduction to recursion, we have practiced writing recursive code whether it was through finding the sum of a nested list, drawing with Python's turtles, stacking cheeses or through creating trees. These examples and practice problems during labs really helped me when it came to writing recursive code for our first test. Using the Tree class, one of the problems was to write a function two_whether which returned whether at least one value in a Tree is 2. It looked something like this:

class Tree:

    """Bare-bones Tree ADT"""

    def __init__(self: 'Tree', value: object=None, children: list=None):

        "Create a node with value and any number of children"""

        

        self.value = value

        if not children:

            self.children = []

        else:

            self.children = children[:]

def two_whether(t: Tree) -> bool

    "Return whether at least one value in tree is 2

    precondition - t is a non-empty tree with number values

    >>> tn1 = Tree(2, [Tree(4), Tree(4.5), Tree(2), Tree(5.75)]

    >>> two_whether(tn1)

    True

    """

    return t.value == 2 or any([two_whether(x) for x in t.children])

    The base case in this example was if t.value == 2, and the recursive part was searching through the children of the Tree if any of their values were == 2. 

    One of my goals in this class is still to master recursion, and after being able to answer that question on the test I feel like I am reaching closer to my goal.

Moving Cheeses + Reading Week Game Plan

     Our first CSC148 assignment was to code a game in which we were to move a stack of cheeses from an initial stool to a destination stool, without placing a larger cheese on top of a smaller cheese. When we were first assigned this project, I had remembered doing a similar puzzle to this (called the "Tower of Hanoi") and was able to recall a strategy in completing the game. After being able to visualize a solution to the game, regardless of the number of stools or cheeses, and through discussion with my partners for the assignment, implementing the code into Python became a somewhat easier task.
     I enjoyed working on this assignment for a couple of reasons. Firstly, it helped me practice coding using recursion. In this game there is a least number of moves to move the stack of cheeses depending on the number of cheeses to move. This means that moving a large amount of cheeses uses the same strategy as moving a smaller amount of cheeses. This is a recursive problem, because once we figured out how to move a small stack of cheeses using the least amount of moves (base case), we are able to recall this solution when dealing with a larger instance. Another reason I enjoyed this assignment was because of the opportunity to work in a group. I feel that I am able to learn and grasp content easier when I work through it with others; sharing knowledge and insight.
     With this assignment completed, I plan to use reading week to prep for our first term test which will cover quite a bit of content such as OOP, inheritance, recursion and much more.
     (Ending these blog posts has always been troublesome for me so I'll just conclude here and wish          everyone a productive reading week!)

Intro to Recursion

     In the last set of CSC148 lectures we were introduced to recursion, which at the time I knew nothing about other than "it is a technique used to solve problems". Due to my (terrible) lack of knowledge of the subject I decided to google "recursion" to learn more about the topic, and found something interesting. After I made sure I typed in recursion correctly, google still suggested this:

At first I didn't know that this was done purposely by google, but after further investigation of recursion I knew why google decided to add this little "easter egg". 

     I now understand that recursion involves some sort of repetition (because clicking the suggestion in google led to the same page). When implemented in programming to for example, a function, it would mean allowing a function to call itself.

     The example we did in class using Python's turtle also helped me understand recursion but in a more visual sense. We commanded these drawing turtles to draw "tree bursts" starting with the base case of level 1 then gradually increasing the levels too see how recursion was being represented. As the levels increased, I saw that the level 1 tree burst was being used to draw the level 2, and 3 and so on.. tree bursts. From this, I understood that when facing a recursive problem, it's solution will come from solutions to smaller or the most basic instances of the same problem.

     With that being said, my goal this week and perhaps next week will be to master recursion, which will not just help me complete our first CSC148 assignment, but will help me in many ways throughout my computer-programming journey.

Object-Oriented Programming

     From what I have learned in class thus far, object-oriented programming (or OOP) is a programming paradigm, which simply means style of programming. How one would implement OOP in python (or another programming language) is through the creation of "objects" which contain data, but may also operate using it's stored information.

     It was not until "lab01" that I really understood this concept. During this lab we were asked to analyze a word problem and from that, keep note of the major nouns, verbs and adjectives. At first, I thought to myself, "How can this possibly help me in writing code?"I then thought about how in the real world, we are surrounded by different objects of which have various properties and functions. As a result, I knew that each noun would be an object for the program, and each verb and adjective would describe what methods I would have to implement for my newly created object.

     In my previous computer science course; CSC108, my peers and I mostly used a different style of programming called "procedural programming" which mostly means how it sounds: to program by procedure. This programming paradigm focuses on writing functions that operate on data taken through it's parameters. Now, coming into CSC148 I cannot speak for the rest of my peers when I say that object oriented programming is almost Aladdin-like to me (get it? A whole new world, lame, I know). This new style of programming goes one step further beyond my knowledge from CSC108 and teaches me (and the rest of my fellow beginner programmers) how to kill two birds with one stone; creating an object with both stored data and functionality.