Week 12: Last Impressions

CSC148 has been an enjoyable experience, and a great introduction to ADTs such as LinkedLists and Binary Search Trees. The most important concept that I have encountered this semester, in my humble opinion, would definitely be the ever-so-frightening recursion. Although this semester has been a bit of a struggle with grasping and harnessing recursion in my code, I expect to continue to hone by skills over the rest of my undergraduate career.

Unfortunately, I do have some concerns that my choice in completing A3 Option B instead of Option A will hurt me on the CSC148 final exam. A2 was markedly harder than A3, and I feel that option B was most probably tacked onto A3 as a result of a lack of feedback on our A2. The strike definitely has impacted me a many ways this semester.

However, I feel confident that I am continually improving on my coding skills, and I look forward to this summer where I'll be taking CSC207 and CSC236.

Good luck to my fellow classmates, and Happy Exam Season!

Week 11: Revisiting a previous post

Note: Links to blogs that I have commented on or read have been included in this post. 

I have decided to revisit last week's (week 10's) post, as it describes the continuing struggle I have faced with grasping and mastering recursion. I wish I could say my approach to learning recursion has been anything other than brute forcing my way through a problem until I obtain a correct answer, or learning through mimicry, but that would be a lie. 

Recursion is the one concept in CSC148 that I have struggled with, and it is a fundamental concept that all programmers should have a strong understanding of. 

In week 7 of this course, I defined recursion in my own words:

"""
Recursive functions are functions that call themselves. If a task can be divided into identical, smaller sub-tasks, this is a good indication that you can perform this task by recursion.

They have a conditional structure that specifies a base case (or cases): a condition (or conditions) that will stop the function from making calls to itself.  The also have a general case, which specifies the method in which recursive sub-calls will be combined. Essentially, the general case is the part where the function calls itself. It is important that you designate a base case, or the function call will reach a maximum recursion depth, and result in a stack overflow.

What is this legendary stack you speak of? Recursion is actually a method of using stacks to achieve a task. However, call stacks are stored in a computer's memory, and these stacks cannot become infinitely large, as computers do not have an indefinite amount of memory space. Thus, when a recursive function has a bug, and never reaches a base case, the computer will eventually runs out of memory and crash the program. This is called a "stack overflow".
"""

I think recursion is definitely a concept that does not come easily to me. It will most probably be a concept that I gradually come to terms with as I grow as a programmer. It is certainly a new, and unused way of approaching a problem that I have never personally encountered prior to this semester.

I worry for myself, as I am concerned that I will not do well without having a fully understanding of recursion going into the exam and into 2nd year programming courses.Regardless, all I can do is try harder.

I think the one thing that keeps me afloat is realizing that my struggles are not unique to just me. 

For example, here are a list of blogs that I have either read or commented on:

https://humaircsc148slog.wordpress.com/2015/03/15/week-9-back-to-bsts-insertions-and-deletions/comment-page-1/#comment-2  Humair takes time this week to describe Binary Search Trees and various methods associated with these classes. Humair always takes the time to write informative posts, and it's always informative to see how my peers approach different problems. Humair's blog has been a pleasure to read this semester

https://csc148winter2015.wordpress.com describes their journey with recursion, and how they developed over the period of a semester. Notably, the writer finds that they learned how to approach recursion in their own unique way. 

http://christiangarciacsc148.blogspot.ca/2015/03/week-10-impressions-of-week-9.html?showComment=1427568192945 always takes the time to create clear and concise diagrams to help his peers understand topics. His posts are always informative. In one of his posts, he mentions a quote from a fellow student that he found guided him through his learning: 

“I think the key concept is: don’t start [from] details but start from structure.”

He proceeds to state that: "This is definitely a good advice to take home. Structure is really important when programming. A clear structure can help not only the person coding, but people looking at that code. Also, having a plan before starting anything helps to clarify ideas and to have an easier time coming up with a solution."

I think, ultimately, that recursion is as complicated as you make it. I have to learn how to simplify problems. To not overthink things, and to take things slowly. Rather than coding desperately, and trying a billion solutions until I find the one that works, I should rather just sit down and pause. Think about the core problem I'm trying to solve, and let things fall into place. 

I think one's approach to solving a recursive problem could actually be indicative of one's approach to solving every day problems. 

I'm normally a highly stressed individual who sweats all of the details. I angst over the trivial technicalities, and fail to see the larger picture at times. I have long since come to recognize this problem, and I continually work to change this aspect of myself. Hopefully, as time passes, I will be able to apply a calmer, more methodical approach to solving problems both in my programming life and in my everyday life. 

Week 10: Assignment 3

Again, the strike continues, and it's beginning to take its toll. I haven't really been following up on the lab material, as I should have, because of the chaos that has been going on. Debates being turned into term papers, assignments being pushed forward or pushed back. It's been a crazy time. In particular, the wording of the last couple of labs has been a little confusing and off-putting for me, and I'm not very sure how I should approach them.

Regardless, I've been working on Assignment 3, and it has been successful for the most part. Again, in this assignment we are working with trees. However, the tree is composed of GameStateNodes. I found that this lab required an extensive use of helper functions that simplified the assignment for me.  The difficult part was identifying the helper functions that were needed.

I had problems with two of the functions in the assignment, but these problems were fairly quickly overcome. Strangely enough, I found that assignment 2 was leaps and bounds more difficult than assignment 3. This may in part be because I chose to complete Option B rather than Option A, which seemed to be a longer undertaking.

Anyways, branching_stats was one such function that I had difficulties with, as my preconceived notions of dictionaries in Python were lacking. I kept attempting to use the .add() dictionary method, to no avail. A little tinkering around with dictionaries put me back on track.

Another function I had difficulties with was a helper function I used to collect all of the paths in the tree. I had difficulties conceptually seeing the path I had to undertake so as to obtain the path in each tree. Although I could see how I would go about doing this visually, I had difficulties translating it into code. After deriving the solution for the answer, I was saddened by how simple the answer really was, and how long it took me to find the solution .

I think recursion is definitely a concept that does not come easily to me. It will most probably be a concept that I gradually come to terms with as I grow as a programmer. I worry for myself, as I am concerned that I will not do well without having a fully understanding of recursion going into the exam and into 2nd year programming courses.

Regardless, all I can do is try harder.

Week 9: Optimizing Recursion

Thus far in CS148, we have learned that while recursive functions are often more elegant than functions that use loops, they are often not as efficient. However, there are ways of optimizing recursive functions.

For example, in a recursive function on a tree, you can choose to ignore branches of the tree that will not impact the output of your function. This reduces the number of recursive calls you make on your tree, and optimize the efficiency of the function.

        

    # The optimization here is that you can ignore branches. So you add conditions to IGNORE them.

    # When do you ignore the left branch? When node.data < start.

    # When node.data < start then you ignore the left branch.

    # See below:

    

    def list_between(node, start, end):

    ''' (BTNode, object, object) -> list

    

    Return a Python list of all values in the binary search tree

    rooted at node that are between start and end (inclusive).

    

    >>> b = BTNode(8)

    >>> b = insert(b, 4)

    >>> b = insert(b, 2)

    >>> b = insert(b, 6)

    >>> b = insert(b, 12)

    >>> b = insert(b, 14)

    >>> b = insert(b, 10)

    >>> list_between(None, 0, 15)

    []

    >>> list_between(b, 2, 3)

    [2]

    >>> L = list_between(b, 3, 11)

    >>> L.sort()

    >>> L

    [4, 6, 8, 10]

    '''

    if node is None:
        return []
    else:
        left_list = (list_between(node.left, start, end) 
                     if node.data > start 
                     else [])
        right_list = (list_between(node.right, start, end) 
                      if node.data < end 
                      else [])
        node_list = ([node.data] 
                     if (start <= node.data <= end) 
                     else [])
        return left_list + node_list + right_list

Week 8: Linked Lists

In week 8 of CSC148, we learned about Linked Lists (LLs).

Summary of Linked Lists:

- Linked lists are data structures
- Linked lists are similar to trees in that they utilize nodes.
- These nodes are represented as a sequence.
- Linked lists are similar to arrays (lists), as they both store data.
- However, there is a unique difference between lists and LLs.

- In a vector, if we wish to insert data into our array, we have to move all of the subsequent entries by one or more indices. Although this is not too much of a problem when we have a list of length 1 or 2, this becomes a huge undertaking when we have a list of length 2,000,000. The amount of work grows in direct proportion to the number of items in the list.
- Insertion and deletion operations in an array grows linearly with the number of entries.

- We can use another data structure to perform an insertion or deletion operation that is independent of the number of items in the array : the LL
- In a LL structure, each of our nodes is linked to the node following it.
- We access elements in a vector through indices. Each element is contiguous to one another
- In a LL, the way we get to another node is through links that use pointers to point to the memory address with the next node in the LL. We also have a terminating value for our last node in the list to indicate that it is the end of the list.

- To insert a new element in the list, all we must do is grab one of the pointers in the list (let's call this point A) and point it to this new value (C). Initially, node (A) was pointing to node (B). So, we can point this new node (C) to point (B). In a LL, we can have a million values, but all we have to do to insert one node is redirect those three values. This is in comparison to having an array with a million values. Nifty!
- However, vectors(arrays/lists) excels in different ways. Although LL are superior for insert/deletion. It does excel at being able to access any particular element in a constant amount of time through the power of indices.
- In the case of LLs, you must follow the pointers throughout the LL to "find" the node that we're interested in. In LLs, we only have a mechanism to go forward, and we must start at the front of the LL and traverse the entire LL to "find" our node.
- WLists can go backwards, but we have not covered this topic.

Week 7: Selected Summary - Recursion Post from Week 4/5

In week 4 of CSC148, we broached the topic of recursion. Recursive functions are functions that call themselves. They have a conditional structure that specifies a base case (or cases): a condition (or conditions) that will stop the function from making calls to itself.  The also have a general case, which specifies the method in which recursive sub-calls will be combined. Essentially, the general case is the part where the function calls itself. It is important that you designate a base case, or the function call will reach a maximum recursion depth, and result in a stack overflow.

What is this legendary stack you speak of? Recursion is actually a method of using stacks to achieve a task. However, call stacks are stored in a computer's memory, and these stacks cannot become infinitely large, as computers do not have an indefinite amount of memory space. Thus, when a recursive function has a bug, and never reaches a base case, the computer will eventually runs out of memory and crash the program. This is called a "stack overflow".

If a task can be divided into identical, smaller sub-tasks, this is a good indication that you can perform this task by recursion.

Fortunately, I find tracing recursion (relatively) straightforward to parse. Unfortunately, I find recursive functions extremely difficult to write. In last week's lab, we were introduced to tracing recursive functions in Python. Tracing recursion mentally is a bit of a mess at times, when you're trying to determine the output of a function call. 

For example:

def nested_concat(L):
    """(list or str) -> str

    Return L if it’s a str, if L is a (possibly-nested) str return
    concatenation of str elements of L and (possibly-nested) sublists of L.

    Assume: Elements of L are either str or lists with elements that
            satisfy this same assumption.

    # examples omitted!
    """
    if isinstance(L, str):

        return L
    else: # L is a possibly-nested list of str

        return ’’.join([nested_concat(x) for x in L])

In this function, we pass an argument that can either be a list or a string. If the argument is a string, then then argument is returned. Else, the join function is used to concatenate all ofthe elements in the argument. The tricky part is realizing the recursive bit: essentially, the 

base case is that the argument should be a single, concatenated string. The function will

mutate all of the elements, sub-elements, sub-sub-elements (and so on), until it meets this condition. I've commented the tracing of two of the example calls posted in the lab below. 

1) nested concat([’how’, [’now’, ’brown’], ’cow’])
# To trace this call: 
nested_concat([[’how’, [’now’, ’brown’], ’cow’]])
# We notice that L is a list: thus the else condition is reached
--> ’’.join([nested_concat(x) for x in [’how’, [’now’, ’brown’], ’cow’])
#We notice that there is a sublist in L, so we concatenate the elements in that list --> ’’.join([’how’, ’nowbrown’, ’cow’]) 
#Now L is a list of str. Let's concatenate! 
 --> ’hownowbrowncow’
 

  
2) nested_concat([[’how’, [’now’, ’brown’, [’cow’]], ’eh?’]]) 
# First, we notice that there are multiple sub-lists --> ’’.join([nested_concat(x) for x in [[’how’, [’now’, ’brown’, [’cow’]], ’eh?’]]# We identify that ['cow'] is the innermost list, and concatenate each element in that list (only 1)# The list containing ['cow'] is ['now, 'brown', ['cow']]
# so we would end up with 'nowbrowncow'
# The list containing 'nowbrowncow' is [['how', 'nowbrowncow', 'eh?']]
 --> ’’.join([’how’, ’nowbrowncow', 'eh?’] 
 --> ’hownowbrowncoweh?’

Although I understand the concept of recursion, I am finding it difficult to actually put it into practice. Specifically, I have difficulties selecting and coding the base case and the general case of a recursive function. Parsing and developing recursive functions is something that will take some time to get the hang of. Hopefully I will be able to wrap my head recursion and get a strong handle of this very essential concept.

whimsies and I were in a similar situation of understanding the conceptual ideas behind recursion, but having difficulties executing this knowledge in week 5. Hopefully, our understanding of recursion has grown over the last couple of weeks!

Week 6: Object Oriented Programming

Please head over to https://nanalelfecsc148slog.wordpress.com/2015/02/16/summary-of-object-oriented-programming/ for an interesting post on OOP!

In week 6 of CSC148, we have been assigned the topic of summarizing Object-Oriented Programming.

Below, I will share a quick summary of OOP in jot-note and sentence form.

The Object-Oriented Paradigm

Object-Oriented Programming emphasizes objects (data) over actions. This is in contrast to procedural programming, where programs are approached by decomposing problems into a series of actions (functions).

In OOP, we approach a problem by decomposing it into data types. The difference is what we consider first (data before actions vs actions before data).

Objects in Python:
Class (data type definition): a blue print for creating objects
- field/attribute (data member)
- method (function member [action], operations for acting upon data)

Instantiating an Object
An object/instance is a piece of data.

When we instantiate a class,  each instance has its own copy of the fields, but not its own copy of the method.

Principles of OOP

[1st Principle]
Encapsulation: The fields of an object should only be read by methods of that instance's class.
 
- Methods act as "interface" to object's field
- Idea that when you create a class, the methods that you give that class encapsulate (encompass) all of the knowledge that is meant to be done to the data that makes up that data type (modulate data)

[2nd Principle]
Inheritance: The idea of inheritance is that some data types/classes may overlap, such that one data type has all of the same methods/fields found in another.

- The child class will inherit all of the methods/fields of the parent class (including any attributes/methods that the parent class has inherited itself)
 - Child/Descendent = subClass. Parent/Ancestor = superClass

Abstract data types can be a bit confusing to identify as supertypes/subtypes. Think before using inheritance. is-a (a car is a type of vehicle) vs has-a (cars have steering wheels, but a steering wheel would not be a subclass of a car. a steering wheel is not a type of car). Extending/composition.
 
In some OOP languages, every Class is required to inherit from one other class. By default, this Class is a special Class called the object Class, which is built into the language.

Overriding: To override in OOP means to redefine an inherited method.

Invoking methods: object.method(args)

Polymorphism
x.foo()
Polymorphism: depends on type x

Class member (member of class itself, not any instance)
- Class.field
- Class.method(args)


Summarizing Privacy and Property in OOP (Jot-notes)

- Python has no notion of attributes being private, so they're all accessible to clients, but Python has a property mechanism to redirect access to an attribute so that it muse use a method

- property() function:
    - create a method to set x to its initial value. can only be done during initialization. check whether             the name _x is already defined in object self
    - def set_x(self,x):
        if '_x' in dir(self):
            raise Exception('Cannot change')
        else:
            self._x = float(x)
    - next, make sure anybody wanting to use value of attribute x actually uses the value referred to by     _x:
    - def get_x(self):
        return self._x
    - Now, we must tell Python to redirect all atempts to assign to or evaluate x using applicable    
    methods
    - property() ==> takes 4 arguments: method to get value of x, method to set value, method to del         attribute x, and some documentations (arguments can optionally be done)
    - x = property(get_x, set_x, None, None)
    - now: all client code that evalutes or assigns to x is redirected to get_x and set_x

Optionally, you can use @ headers:

For example:

class Example(object):
    def __init__(self, value):
        self.x = value
    @ property
    def x(self)
        return self._x
    @ x.setter
    def x(self, value):
        if '_x' in dir(self):
            raise Exception('Cannot change')

These headers accomplish the same objective as the property function. Now, even the code we have written in the method of class's init gets redirected.

Overall, I believe that I have a strong inclination towards OOP versus Procedural Programming, as I prefer approaching problems by decomposing them into data types rather than decomposing them into functions. Python is an extremely accessible and intuitive programming language that is an excellent introduction to the world of programming.

Week 5: Tracing Recursion

Fortunately, I find tracing recursion (relatively) straightforward to parse. Unfortunately, I find recursive functions extremely difficult to write. In last week's lab, we were introduced to tracing recursive functions in Python. Tracing recursion mentally is a bit of a mess at times, when you're trying to determine the output of a function call. 

For example:

def nested_concat(L):
    """(list or str) -> str

    Return L if it’s a str, if L is a (possibly-nested) str return
    concatenation of str elements of L and (possibly-nested) sublists of L.

    Assume: Elements of L are either str or lists with elements that
            satisfy this same assumption.

    # examples omitted!
    """
    if isinstance(L, str):

        return L
    else: # L is a possibly-nested list of str

        return ’’.join([nested_concat(x) for x in L])

In this function, we pass an argument that can either be a list or a string. If the argument is a string, then then argument is

returned. Else, the join function is used to concatenate all of the elements in the argument. The tricky part is realizing the

recursive bit: essentially, the base case is that the argument should be a single, concatenated string. The function will mutate all of the elements, sub-elements, sub-sub-elements (and so on), until it meets this condition. I've commented the tracing of

two of the example calls posted in the lab below. 

1) nested concat([’how’, [’now’, ’brown’], ’cow’])
# To trace this call: 
nested_concat([[’how’, [’now’, ’brown’], ’cow’]])
# We notice that L is a list: thus the else condition is reached
--> ’’.join([nested_concat(x) for x in [’how’, [’now’, ’brown’], ’cow’])
#We notice that there is a sublist in L, so we concatenate the elements in that list --> ’’.join([’how’, ’nowbrown’, ’cow’]) 
#Now L is a list of str. Let's concatenate! 
 --> ’hownowbrowncow’
 

  
2) nested_concat([[’how’, [’now’, ’brown’, [’cow’]], ’eh?’]]) 
# First, we notice that there are multiple sub-lists --> ’’.join([nested_concat(x) for x in [[’how’, [’now’, ’brown’, [’cow’]], ’eh?’]]# We identify that ['cow'] is the innermost list, and concatenate each element in that list (only 1)# The list containing ['cow'] is ['now, 'brown', ['cow']]
# so we would end up with 'nowbrowncow'
# The list containing 'nowbrowncow' is [['how', 'nowbrowncow', 'eh?']]
 --> ’’.join([’how’, ’nowbrowncow', 'eh?’] 
 --> ’hownowbrowncoweh?’



    

Week 4 : Recursion

In week 4 of CSC148, we have broached the topic of recursion. Recursive functions are functions that call themselves. They have a conditional structure that specifies a base case (or cases): a condition (or conditions) that will stop the function from making calls to itself.  The also have a general case, which specifies the method in which recursive sub-calls will be combined. Essentially, the general case is the part where the function calls itself. It is important that you designate a base case, or the function call will reach a maximum recursion depth, and result in a stack overflow.

What is this legendary stack you speak of? Recursion is actually a method of using stacks to achieve a task. However, call stacks are stored in a computer's memory, and these stacks cannot become infinitely large, as computers do not have an indefinite amount of memory space. Thus, when a recursive function has a bug, and never reaches a base case, or the computer will eventually runs out of memory and crashes the program. This is called a "stack overflow".

If a task can be divided into identical, smaller sub-tasks, this is a good indication that you can perform this task by recursion.

Although I understand the concept of recursion, I am finding it difficult to actually put it into practice. Specifically, I have difficulties selecting and coding the base case and the general case of a recursive function. Parsing and developing recursive functions is something that will take some time to get the hang of. Hopefully I will be able to wrap my head recursion and get a strong handle of this very essential concept.

Also, whimsies left me a nice comment on my last post. I decided to return the favour and leave a comment on her page as well.

Week 3: Why Geeks Need to Write

For week three of CSC148 SLOGs, we have been assigned the topic of "Why Geeks Need to Write". This presents an important topic in computing, as it articulates the necessity of writing and written correspondence.  Writing is a means of delivering information to others, and analyzing your own understanding of a topic.

Knowing is not enough. Communicating what you know is a necessity of life, and english is a medium through which we can deliver this information to others. Whether it be filling out a document, writing a paper for a class, or reporting on a work project; writing never truly disappears from our lives.

Much like syntax is important in our coding, it is also important in our writing. In fact, coding and english are both languages in which we can convey information. Sufficient context, eloquence, and precision are required in both of these languages.

Written information is easily revisited and a great means of recording facts and opinions. The brain is notorious for overwriting and misplacing information that we learn. Graphite, digitized text, and ink are excellent mediums for preserving information that could otherwise be lost. Recording the facts we learn, the concepts we find difficult, and the new information we derived from our learning processes, are methods that can be used to harness our minds.

Often, when attempting to convey information to others, we are able to identify any gaps in our understanding of a topic, or inconsistencies in our theoretical knowledge. Additionally, by conveying information, we are often forced to summarize information in a concise but informative way, thereby helping us to distinguish important information. Learning, and sharing what we have learned, can often be one and the same thing.

A miracle!

I went into the CSC165 exam with a mark in the high 90s, and left the exam completely convinced that I had not managed to achieve a 40% on the exam. Since the course requires you to achieve a grade of 40% on the exam in order to pass the course, I was convinced that I had failed and would be doomed to failure. After an excruciating month of waiting, I received my final grade. An A. I don't think words can describe the simultaneous feelings of relief and inadequacy that flooded over me. Relief, as I had, through some miracle of God, passed. Inadequacy, as I feel that it was most probably a huge fluke. Regardless, I will take what I can get. A new semester has begun. I wish everyone luck =).

I'm back from the dead! But I'm still dead!

Hello, world. I'm posting this blog post after exams, so this post is not really an entry for the course SLOGs.... it's more like a Dear Diary entry where I pour out the contents of my aching heart. A soliloquy of my despair.

I'm currently in a state of panic. I went into the exam feeling fairly confident. I mean, I was able to answer all of the questions from the 2010/2013 exams, how bad could it possibly be? As long as I got  over 40%, I'd still end up with a mark in the 70s. I prepared so much for it. My cheat sheet was crammed full of all of the possible questions from the assignments, tests, and lecture notes.

*echoing* Prepared so much for it. Prepared so much for it. Prepared so much for it *echoing*

On a scale of 1-10, I bombed that exam with a 100. I don't think I could have possibly messed up more than I did on that exam, besides like.... not showing up for the exam at all. All of the questions I thought would be on the exam, all of the questions that I prepared for.... were not on the exam. No halt (!!) , no generic big-Oh, no conversion of statements (Not all, Any). Nope. Nope. Nope.

 I pretty much threw a course worth of achievements (I was so, so proud of my grade in the course... a mark in the high 90s) into a pile of feces.

 I was expecting delta-epsilons to be on the exam, but I wasn't expecting TWO such questions to be on the exam. And they weren't ones I was familiar with. As soon as I saw the two, my mind went blank. Then I realized I couldn't solve both. I entered this state of complete and utter panic. I started sweating. My mind went blank. I'm actually fairly certain I was shaking at one point.

All of the questions I successfully answered, I somehow managed to misread the questions, and actually answer the wrong question. You're not reading that wrong. All of the questions that I SHOULD have gotten right, I somehow managed to  prove something... that didn't even answer the question they asked. So I bombed the exam. Thoroughly.

 How does one do this? How does one throw away a semester's worth of efforts in the matter of 3 hours. I failed that exam, without a matter of a doubt. We will be receiving our marks before Christmas, but I already know the result.

I went into the exam with high 90s, and now I'm not going to meet the minimum requirement for passing the course. I am going to have to repeat this course. I don't think words exist to describe how sad I am right now.

What is life.

That last minute struggle

After creeping and commenting on people's SLOGs over the course of this semester, I have to say that it's remarkable how people have gone from 2 posts all semester long (and this was the case for most people's SLOGs even 2 weeks ago!!!), to walls of texts. Oh, University, how is it that you are able to bring out the procrastinator that lies deep within all of our hearts.

 Overall, I feel that the SLOGs are an excellent way of proving to yourself that you know what you're talking about. It's one thing to understand a concept, and another to demonstrate that you actually do understand the concept that you claim to understand. Was that statement extremely convoluted? Yes. But you know what I mean.

 Throughout this semester, I've often gone from assuming that I understood a concept-- to realizing that I didn't. This was helped in part by reading SLOGs. I found it helpful to utilize other student's SLOGs to gain a better understanding of certain concepts. You often learn more from people who are also learning the material themselves. Good times.

Another thing that I have noticed is that I have spent a disproportionate amount of time in this course convincing others to realize why their proofs are insufficient or wrong. I'm not normally a confrontational person, but it can be a little exasperating at times when you're arguing with group members. You cannot prove a statement by restating it -- and you also cannot prove a statement by cleverly manipulating your proof so that it proves your statement, but only in certain cases. I'm not telling you that my answer is correct, but I'm most certainly pointing out why your proof cannot be correct.

After spending a semester taking CSC165, I have come to the realization that, although I have difficulty actually proving proofs, I have a strong foundation -- I can almost always tell when a proof is insufficient or wrong. I have also done enough practice proofs and studying to ensure that I am able to write proofs for the vast majority of proofs I should encounter in the exam. Hopefully this statement holds true for the actual exam. I also hope that, in the future, I will be able to devise proofs to problems with which I have not had prior experience with. Perhaps hone my intuition and induction skills?

Overall, it's been a great run. I can honestly say that this is most probably the only kind of course in which I would hear two students arguing over office hours with interjections of "BUT MY PROOF IS MORE ELEGANT" <-- legitimately, this was screamed aloud during Larry's office hours. Oh, UofT, you really, truly amaze me sometimes.

Anyways, I would 10/10 take this course again, and I would highly recommend it to any student - regardless of their major. Informative, educational, and enjoyable. Unfortunately, this SLOG will be seeing its imminent demise after the due date tomorrow, but it's been a great run.

 Adieu!

Computability

I promised, and I shall deliver.

When we disprove the existence of a working halt function, what we are doing is claiming that not only has a working function not been written, but that a halt function cannot possibly exist. The disproof outlined in the coursenotes uses proof by contradiction.



First, assume that the halt function exists.

In this example, the author has cleverly constructed a function, confused, where if confused is passed itself as an argument, one can deduce that there will be two cases here: that the function confused(), when passed itself as an argument confused(confused) will either halt, or it will not halt. Now, this is where things were a little confusing. To completely the paradox, one must pass confused as an argument on itself. Not just any two functions will do. By doing so, we arrive at a contradiction.

Case 1: Assume confused(confused) halts:
     Then halt(confused,confused) returns True.
     Then confused(confused) goes into an infinite loop.
So, confused(confused) halts ==> confused(confused) does not halt.

Case 2: Assume confused(confused) does not halt:
    Then halt(confused, confused) returns False.
    Then confused(confused) halts.
So, confused(confused) does not halt ==> confused(confused) halts.

From this, we can conclude that confused(confused) halts <==> confused(confused) does not halt.
Thus P <==> not P. This is a contradiction. Therefore, the halt function is non-computable.

_________________________________________________________________________________

Reductions are a way to prove the non-computability of a function.
















In a reduction, we first assume that our function is computable, and derive a proof by contradiction. By doing so, we prove that if our function is computable, then the halt function is computable. Since we have already proven that the halt function is not computable, we arrive at the contrapositive of our derived implication: that our function must be non-computable. The trick is to create a function f_prime() that utilizes the function f(i) within its body in a cleverly constructed way. If we are able to reduce halt to the meaning of life, we have produced a valid implementation of the halt function using our function. i.e we are able to utilize our function with arguments f_prime and i to determine whether or not a function halts on an input i. We know that this is not possible.

A function f is computable iff it is well-defined and we can tell how to compute f(x) for every x in the domain. In general, a function that remarks on the behaviour of another function will be non-computable.

CSC165 - Using CSC165 outside of CSC165

I have created an account with ProjectEuler (https://projecteuler.net)  in order to utilize the skills that I have learned in CSC165. Attempting to solve challenging mathematic and computational problems outside of the curriculum is actually almost therapeutic and relaxing. Although the algorithms that I have been implementing have been primitive, at best, it has been an educational experience. I hope that, as I progress through the problems, that my inductive reasoning skills will be honed. Endurance! Perseverance! Euler!

On a side note, I have actually come to understanding the halting problem and computability. Huzzah! I will update this blog with a heartwarming tale of an underdog overcoming all odds in order to achieve her dreams. Or, I'll update this blog with an explanation of the halting problem and computability. One of the two. 'Till next time. Adieu!

CSC165 - Bless office hours

We have learned about the halting problem this week and, for the most part, everything has gone in one ear and out the other. Even referring to the course notes and reviewing the lecture notes did not really give me the confidence that I was actually comprehending what I was incessantly studying.

After I requested a last-minute office hour with one of the professors for the course (thank you thank you thank you thank you!!), I can now confidently say that I may or may not understand reductions and computability (haha). Okay, but no, seriously. I now have a much clearer understanding of the halting problem, and what we're trying to prove when we prove that halt is non-computable. I'm also more confident about reductions; where we prove that another function, F, is non-computable by reducing halt to the aforementioned function. In essence, we prove that a function is not computable by implementing a valid implementation of halt using the function F.

In disproving the the halting problem, we perform a proof by contradiction by assuming that the halt function is computable. After we construct a function that contradicts the halt function, we can use proof by cases to show that there exists a function that contradicts itself by halting when it doesn't halt, and doesn't halt when it's supposed to halt.

---Update--
Sadly, despite his excellent explanation and step-by-step guidance... I have come to realize that I still do not understand the halting problem.

Under-estimating and Over-estimating

We have been covering big-oh notation over the past couple of weeks, and I feel that I'm starting to finally understand the basic concepts behind it. Progress? Maybe?

I think the most important realization was that when given a f(n) >= cg(n), that you should approach the problem by "under-estimating" the right and "over-estimating" the left, and ultimately meeting in the middle. Then, choose a c that makes the right-side an upperbound. 

To under-estimate (Right Side)

- remove a positive term 

- multiply a negative term 

To over-estimate (Left Side)

- remove a negative term

- multiple a positive term

We're trying to simplify the function without changing the highest degree. 

Progress has been made, folks. 

Search methods, Sort methods, Big-O

We have been learning about big-oh notation in the last couple of weeks. More specifically, we have been learning about three sets of notations: including O, omega, and theta. These sets encompasses  the sets of function that either grow no faster, no slower, or as fast as various base functions f(n).

Looking up the graphical representations of these functions was actually a refresher; as I have not taken any true math courses for quite a while. Review will be necessary.

It was interesting to think of functions not in run time, but in growth. Rather than assessing a function for its capacity to run within seconds, we look towards the growth in the steps as the input increases, as a means of testing the efficiency of a function. This is certainly a new approach to measuring run times, as someone with limited exposure to programming. I look forward to broadening my knowledge in this area over the course of the next few weeks. 

Hmmmm......

Well, after reviewing the blogs of my fellow classmates, I feel less guilty about not updating my blog more frequently. I have greater than one blog entry. That's a start! What? What's that you say? I shouldn't be comparing myself to others, and the assignment outline details that I should be updating at least once a week? Rubbish!

Just kidding. Please don't hurt me.

Anyways, the midterm is fast approaching, and proofs will be the death of me. Upon reviewing last year's assignment and midterm, I feel fairly confident. But proofs with multiple quantifiers still confound me. Unfortunately, the assignment this year is one that I find (personally) more difficult to parse than last year's version.  My way of approaching proofs with multiple quantifiers, with variables appearing in the statement out of the order in which they have been quantified, is to first pray that it's an epsilon delta proof, and then to assess which variable comes first (epsilon or delta). Whichever variable appears second "wins". That is my only approach. THE END.


... Okay clearly that will not help me. But one can dream.

Claim 1.2 appears to be very similar to a delta epsilon proof. However, the quantifiers are placed out of order, so I'm a little lost

I will update as soon as I figure out what I am doing with my life.

Proving a Proof

Tips and tricks!

Whenever you introduce a let statement in a proof (when you pick a variable), conclude the end of that margin with an existential.
Whenever you introduce a generic variable , conclude the end of that margin with a universal.

Brief review of floors:
- The floor of x is the largest integer that is less than or equal to x.
- The floor of x is not a variable. It is a function, and quantifiers only apply to variables, so you cannot use a quantifier directly on floor.

Definition of floor:
Assume y is an int. Then y is less than or equal to x. Among all ints that are less than or equal to x, y is the LARGEST.

Note that the symbolic definition of floor and the english definition of floor are equivalent; one is just simpler to parse as a native english speaker.