I have come to the end of another school year and another SLOG. I really can't believe that I'm almost finished my first year of university. I still think that it's 2010 sometimes and that I never really left middle school.
I really hope I did well on assignments 2 and 3. It's really hard writing and handing in an assignment when I don't know the marks for my SLOG or previous assignment. I think that I did well on assignment 3, but it seemed to be a little too easy. I did part B, and while it took a lot of helper functions, I finished it rather easily. Some other students really struggled with part A. I hate when this happens because I always think that I did something wrong, but we'll see how it goes.
I learned a lot in this course, and I am really happy with it. I rarely feel like I actually learn anything from a course I take. At the end of most school years I often end up feeling like I just memorized a bunch of facts, spit them out on tests, and then I forget everything. I think that what I learned in CSC148 will stick with me for a while to come. I think that I now have a much better grasp of recursion, and I now really understand abstract data types. I see some of the practical applications of what I learned in CSC165 and I am finally starting to think about the more abstract science part of computer science instead of just programming. I have also learned the importance of doing stuff on paper as I commented here.
Tuesday, 7 April 2015
Monday, 30 March 2015
CSC148 Lecture Week 11
Looking Back
As I was studying for midterm number 2 I realized that the code I came up with for lab 6 and documented in my SLOG was actually quite redundant.
In lab 6 my solution to the list_longest_path function looked like this:
if node is None:
return []
elif is_leaf(node):
return [node.data]
I didn't really need all those nested if statements and the second if statement also was not necessary. I managed to come up with some simpler, easier to read code:
if node == None:
return []
else:
right = [node.data] + list_longest_path(node.right)
left = [node.data] + list_longest_path(node.left)
return right if len(right) > len(left) else left
I think that this SLOG entry and my SLOG overall really shows how I have learned and grown throughout the course. As another slogger has said, practice makes perfect. I have spend a lot of time practicing new recursion techniques and I think that I have a much better grasp of it now. I'm also really missing the labs that were cancelled due to the TA strike. They were a great place to practice and as another slogger points out, they were all about practicing our coding skills, and we never wasted time on pointless name games or team building activities.
As I was studying for midterm number 2 I realized that the code I came up with for lab 6 and documented in my SLOG was actually quite redundant.
In lab 6 my solution to the list_longest_path function looked like this:
if node is None:
return []
elif is_leaf(node):
return [node.data]
else:
if not node.left == None:
left = list_longest_path(node.left)
else:
left = []
if not node.right == None:
right = list_longest_path(node.right)
else:
right = []
return [node.data] + left if len(left) > len(right) else [node.data] + right
if not node.left == None:
left = list_longest_path(node.left)
else:
left = []
if not node.right == None:
right = list_longest_path(node.right)
else:
right = []
return [node.data] + left if len(left) > len(right) else [node.data] + right
I didn't really need all those nested if statements and the second if statement also was not necessary. I managed to come up with some simpler, easier to read code:
if node == None:
return []
else:
right = [node.data] + list_longest_path(node.right)
left = [node.data] + list_longest_path(node.left)
return right if len(right) > len(left) else left
I think that this SLOG entry and my SLOG overall really shows how I have learned and grown throughout the course. As another slogger has said, practice makes perfect. I have spend a lot of time practicing new recursion techniques and I think that I have a much better grasp of it now. I'm also really missing the labs that were cancelled due to the TA strike. They were a great place to practice and as another slogger points out, they were all about practicing our coding skills, and we never wasted time on pointless name games or team building activities.
Monday, 23 March 2015
CSC148 Lecture Week 10
This week we discussed testing. Specifically, we focused on testing the minimax strategy. If we were to test minimax with subtract square, there are certain test cases that would not help at all. There are a few numbers that will always result in a loss no matter what number the player picks. Wikipedia calls there 'cold numbers'. When coming up with test cases, cold numbers such as 10 or 15 would not be useful at all. Numbers such as 9 also may not inspire much confidence when used as test cases. If there are more winning moves then there are losing moves, then the random strategy would still work more than 50% of the time. Therefore when picking test cases, we would have to carefully consider the outcome of each case.
Monday, 16 March 2015
CSC148 Lecture Week 9
Last week we covered linked lists in class. Linked lists can be though of a tree with airity of one. Each node has a value and a reference to another node or None if it is the end of the list. A wrapper class can then be used to keep track of the size of the list, the front node and the back node. Recursion can be used to traverse linked lists, but due to the more linear nature of the lists iteration works just as well. A while loop or for loop can be used to step through the list until you get to the desired node. The basic structure would look something like this:
cur_node = lnk.front
while cur_node:
cur_node = cur_node.nxt
I liked going back to iteration. It was nice to be able to use loops again and not have to think in a recursive manner. Working with linked lists also involves mutation. It is important to change things in the correct order so that you don't lost data. I found this part of linked lists to be manageable. What I found difficult was remembering to change the front, back and size data in the wrapper. I created a check list for the test, so hopefully I did everything properly on the test.
Saturday, 7 March 2015
CSC148 Lecture Week 8
Assignment 2 was due this week, and I am very glad that I was able to finish it. When I first looked over the assignment, I though that it would be pretty easy so I didn't start anything until the Saturday before it was due. Coding TippyGameState was relatively easy. winner() and rough_outcome() were pretty long since my group just did that by brute force. On Piazza, Danny answered a question about winner() and said that there was no really elegant way for it to be implemented, so just decided to go through the whole board and check for all four possible tippies.
What really cause me trouble was minimax. My whole group had a lot of trouble with it and we came up with some really complicated methods that did not work. After taking a step back and rereading the assignment page, I realized that we were probably over-complicating it. The assignment handout pretty much gave us the exact algorithm for the minimax strategy:
What really cause me trouble was minimax. My whole group had a lot of trouble with it and we came up with some really complicated methods that did not work. After taking a step back and rereading the assignment page, I realized that we were probably over-complicating it. The assignment handout pretty much gave us the exact algorithm for the minimax strategy:
I then worked on translating this algorithm to code. I had trouble pairing the moves with their scores, but that was fixed with the help of a helper function (they're so helpful aren't they?).
The final problem was that minimax worked with subtract square and not tippy. It took a lot of tracing through the Wing debugger, but we eventually realized that apply_move() in TippyGameState was changing the original game state. This was fixed with the use of deepcopy() (Thanks again to Piazza).
Friday, 27 February 2015
CSC148 Lecture Week 7
I would like my summary of Object Oriented Programming concepts to be graded.
Lab 6 this week is the first lab that I really struggled with. The function list_longest_path asked us to write a function that would find the longest path in a binary tree and return that path. The starter code came with the following docstring examples:
>>> list_longest_path(None)
[]
>>> list_longest_path(BTNode(5))
[5]
>>> list_longest_path(BTNode(5, BTNode(3, BTNode(2), None), BTNode(7, BTNode(4, BTNode(9)), BTNode(6))))
[5, 7, 4, 9]
The first two examples give us the two base cases for the algorithm. When there is no tree at all, the longest path contains nothing. When only the root is present, the longest path is obviously just the root itself.
Translated into code this would be:
if node is None:
return []
elif is_leaf(node):
return [node.data]
The recursive case was what I really struggled with. I couldn't figure out how to keep track of all the data because we couldn't just find all possible paths, store them in a list and then look through that list, which is the type of recursion that we had been doing before. What really helped was one of my partner's ideas and actually drawing out the tree itself.
My partner, Wendy, realized that at each node we would need to look at the right node and the left node and then compare them. I then started walking through the tree starting at the root. Node 8 would ask Node 7, "What is your longest list?", then it would ask Node 1, "What is your longest list?". This would continue until a leaf was reached. The leaf would then know right off the bat that its longest path was itself. This information would then be sent back up the tree. The final piece of the puzzle was realizing that we would have to concatenate the data of the node itself to the data it was getting from it's children. This then lead to the final solution:
else:
if not node.left == None:
left = list_longest_path(node.left)
else:
left = []
if not node.right == None:
right = list_longest_path(node.right)
else:
right = []
return [node.data] + left if len(left) > len(right) else [node.data] + right
Another slogger also has a great explanation of recursion here.
Lab 6 this week is the first lab that I really struggled with. The function list_longest_path asked us to write a function that would find the longest path in a binary tree and return that path. The starter code came with the following docstring examples:
>>> list_longest_path(None)
[]
>>> list_longest_path(BTNode(5))
[5]
>>> list_longest_path(BTNode(5, BTNode(3, BTNode(2), None), BTNode(7, BTNode(4, BTNode(9)), BTNode(6))))
[5, 7, 4, 9]
The first two examples give us the two base cases for the algorithm. When there is no tree at all, the longest path contains nothing. When only the root is present, the longest path is obviously just the root itself.
Translated into code this would be:
if node is None:
return []
elif is_leaf(node):
return [node.data]
The recursive case was what I really struggled with. I couldn't figure out how to keep track of all the data because we couldn't just find all possible paths, store them in a list and then look through that list, which is the type of recursion that we had been doing before. What really helped was one of my partner's ideas and actually drawing out the tree itself.
My partner, Wendy, realized that at each node we would need to look at the right node and the left node and then compare them. I then started walking through the tree starting at the root. Node 8 would ask Node 7, "What is your longest list?", then it would ask Node 1, "What is your longest list?". This would continue until a leaf was reached. The leaf would then know right off the bat that its longest path was itself. This information would then be sent back up the tree. The final piece of the puzzle was realizing that we would have to concatenate the data of the node itself to the data it was getting from it's children. This then lead to the final solution:
else:
if not node.left == None:
left = list_longest_path(node.left)
else:
left = []
if not node.right == None:
right = list_longest_path(node.right)
else:
right = []
return [node.data] + left if len(left) > len(right) else [node.data] + right
Another slogger also has a great explanation of recursion here.
Tuesday, 17 February 2015
CSC148 Lecture Week 6
Object Oriented Programming Summary
Object Oriented Programming is a style of programming that involves grouping similar idea into classes. These classes are then used as blueprints that can be used to create instances of objects that have methods and attributes associated with them. Objects can then manipulate their attributes and use their methods to perform tasks.
Self
For all methods associated with a class, the first parameter is always the object itself. By convention this parameter is named self. This then allows you to call the method using syntax like this:
object.method()
which is equivalent to:
method(object)
Inheritance
The major idea that we covered in object oriented programming is the concept of inheritance. Sometimes classes will have many similarities and repeated code. Instead of copying and pasting code, which can cause many problems, inheritance is a much better solution. Copying and pasting code would force you to change many files every time you changed your design. With inheritance, a parent class has all the attributes and methods that are common to all the similar classes. For example, if you were designing a program to manipulate shapes, you would have a general shape parent class and child classes for specific shapes like triangles and squares. The parent class would have general attributes like side length, and general methods like find area. The child classes would inherit all this.
The parent class can implement some methods, but it might not actually know the specific details about methods like find area. In this case, it is not meant to be instantiated, so a NotImplementedError would be raised if the parent class' method was called. The child class would have a proper implementation that overrides the parent class method. Code that uses these classes would then be written for any general shape. It would not need to know what specific shape that it is dealing with and this allows for more flexibility.
Object Oriented Programming is a style of programming that involves grouping similar idea into classes. These classes are then used as blueprints that can be used to create instances of objects that have methods and attributes associated with them. Objects can then manipulate their attributes and use their methods to perform tasks.
Self
For all methods associated with a class, the first parameter is always the object itself. By convention this parameter is named self. This then allows you to call the method using syntax like this:
object.method()
which is equivalent to:
method(object)
Inheritance
The major idea that we covered in object oriented programming is the concept of inheritance. Sometimes classes will have many similarities and repeated code. Instead of copying and pasting code, which can cause many problems, inheritance is a much better solution. Copying and pasting code would force you to change many files every time you changed your design. With inheritance, a parent class has all the attributes and methods that are common to all the similar classes. For example, if you were designing a program to manipulate shapes, you would have a general shape parent class and child classes for specific shapes like triangles and squares. The parent class would have general attributes like side length, and general methods like find area. The child classes would inherit all this.
The parent class can implement some methods, but it might not actually know the specific details about methods like find area. In this case, it is not meant to be instantiated, so a NotImplementedError would be raised if the parent class' method was called. The child class would have a proper implementation that overrides the parent class method. Code that uses these classes would then be written for any general shape. It would not need to know what specific shape that it is dealing with and this allows for more flexibility.
Thursday, 5 February 2015
CSC148 Lecture Week 5
The first few weeks of class have been OK. Object oriented programming is a topic that I rather like. I have previous OOP experience in Java, so the fact that Python has no real concept of privacy is rather surprising. Using property in Python is interesting. It really makes me think about the public client interface of code vs the private implementation of code and I think that it is a really good idea. When I use built in functions like sort on a list for example, I don't really care what algorithm is being used. I just expect it to be fast. If a better way of sorting a list is discovered, it's good to know that my code will not be affected if the function is changed.
I'm liking the way that we trace recursion in class. It is helping me understand recursion a little better. I like having a visual representation of recursion since I am a visual learner. It was hard for me to picture what was going on with recursive functions, but I now have a better tool for helping me.
What I'm disliking about the lectures so far is their focus on the assignments. I think that it's really helpful for the professor to give tips on assignments and take questions during lecture time, but it always seems to end up eating up a massive amount of the lecture time. I want to learn concepts during lecture time and then apply them to assignments. A lot of the questions asked are being repeated or are asking for what seems like hand-holding. Asking assignment specific questions wastes the time we could spend learning general concepts that will be applicable to future situations.
I'm liking the way that we trace recursion in class. It is helping me understand recursion a little better. I like having a visual representation of recursion since I am a visual learner. It was hard for me to picture what was going on with recursive functions, but I now have a better tool for helping me.
What I'm disliking about the lectures so far is their focus on the assignments. I think that it's really helpful for the professor to give tips on assignments and take questions during lecture time, but it always seems to end up eating up a massive amount of the lecture time. I want to learn concepts during lecture time and then apply them to assignments. A lot of the questions asked are being repeated or are asking for what seems like hand-holding. Asking assignment specific questions wastes the time we could spend learning general concepts that will be applicable to future situations.
Thursday, 29 January 2015
CSC148 Lecture Week 4
Ah, recursion, my old enemy, we meet again. I am actually so glad that university terms are only 12 weeks long. I can only maintain good study habits for a few months at a time before I need a break, and in high school, by the last month, I was just out of gas. That was the month that we learned recursion and I just gave up, although now that I think about it, I don't think that the Waterloo Canadian Computing Competition recursion questions that my teacher gave us were suited to our skill level.
The basic recursion we did in class with one base case and a very simple recursive statement, I can understand. Recursion is a type of algorithm where within a function, the function calls itself as a helper function. Recursion is best used on problems that can be broken down into smaller version of the same problem. One basic application of recursion is the factorial function shown to us in tutorial. For example, 6! can be broken down into 6 x 5!, which is then 6 x 5 x 4! and so on until you get to 1! which is just 1. Every factorial can eventually be broken down until 1!, so that is the base case which terminates recursion. The recursive call is then to call the function on n-1. Tracing recursion has been a good experience. I think I have a better grasp on exactly how recursion works now.
The basic recursion we did in class with one base case and a very simple recursive statement, I can understand. Recursion is a type of algorithm where within a function, the function calls itself as a helper function. Recursion is best used on problems that can be broken down into smaller version of the same problem. One basic application of recursion is the factorial function shown to us in tutorial. For example, 6! can be broken down into 6 x 5!, which is then 6 x 5 x 4! and so on until you get to 1! which is just 1. Every factorial can eventually be broken down until 1!, so that is the base case which terminates recursion. The recursive call is then to call the function on n-1. Tracing recursion has been a good experience. I think I have a better grasp on exactly how recursion works now.
Monday, 19 January 2015
CSC148 Lecture Week 3
And here I was thinking that I had written my last SLOG. But now I am back to the wonderful world of blogging for class.
This week's topic is: Why do geeks need to learn how to write? My answer is pretty simple: Documentation. In the wise words of the Mythbusters, "The only difference between science and screwing around it writing it down". Programming and computers may seem highly individual, but in reality they require a lot of teamwork. The apps, websites, and programs that we use everyday were not built by one person. Programmers need to be able to communicate ideas and tell each other how their code works. This requires us to be able write clearly and concisely in a way that another human being can understand.
I for one hate writing comments, but no one (at least I'm assuming) likes to read uncommented code. I can't read the mind of whoever wrote the code. The code could be the most innovative amazing thing ever, but if I can't understand it, it is of no use to me. My human brain needs some plain English to process what it going on.
As another blogger points out, knowing how to write also helps us understand the problems we are trying to solve. Computer programming is fundamentally about solving problems, and we have to know what we are trying to solve before even attempting to do something about it.
This week's topic is: Why do geeks need to learn how to write? My answer is pretty simple: Documentation. In the wise words of the Mythbusters, "The only difference between science and screwing around it writing it down". Programming and computers may seem highly individual, but in reality they require a lot of teamwork. The apps, websites, and programs that we use everyday were not built by one person. Programmers need to be able to communicate ideas and tell each other how their code works. This requires us to be able write clearly and concisely in a way that another human being can understand.
I for one hate writing comments, but no one (at least I'm assuming) likes to read uncommented code. I can't read the mind of whoever wrote the code. The code could be the most innovative amazing thing ever, but if I can't understand it, it is of no use to me. My human brain needs some plain English to process what it going on.
As another blogger points out, knowing how to write also helps us understand the problems we are trying to solve. Computer programming is fundamentally about solving problems, and we have to know what we are trying to solve before even attempting to do something about it.
Monday, 1 December 2014
CSC165 Lecture Week 12
So this is my last SLOG. I wish I could say that I'm sad, but I'm really not.
I actually really liked assignment 3. I finally understand what the point of all those limit proofs were. For the limit of a function as x goes to infinity, if that limit is infinity, then the output of the function can be larger than any given number past a certain breakpoint for the input. For the limit of a function as x goes to infinity, if that limit equals to zero, then the output of the function can be smaller than any given number after a certain breakpoint for the input.
The zero limit also really helped in my understanding of infinity. No matter how small a number I can think of between 0 and 1, there will always be a real number that is smaller than the number I've come up with. I'm also glad, I finally managed actually apply the limits and derivatives that I have spent the past year and a half learning.
After reading some other SLOGs, I've found a couple that have good summaries of computability, which I think was the hardest of the topics that we covered:
http://fromatothis.blogspot.ca/
http://mrbunnyua.blogspot.ca/
I actually really liked assignment 3. I finally understand what the point of all those limit proofs were. For the limit of a function as x goes to infinity, if that limit is infinity, then the output of the function can be larger than any given number past a certain breakpoint for the input. For the limit of a function as x goes to infinity, if that limit equals to zero, then the output of the function can be smaller than any given number after a certain breakpoint for the input.
The zero limit also really helped in my understanding of infinity. No matter how small a number I can think of between 0 and 1, there will always be a real number that is smaller than the number I've come up with. I'm also glad, I finally managed actually apply the limits and derivatives that I have spent the past year and a half learning.
After reading some other SLOGs, I've found a couple that have good summaries of computability, which I think was the hardest of the topics that we covered:
http://fromatothis.blogspot.ca/
http://mrbunnyua.blogspot.ca/
Friday, 21 November 2014
CSC165 Lecture Week 10/11
This is technically just for lecture week 10, since we won't be having a lecture week 11 for the Tuesday evening class, but anyway, onto the SLOG.
This week in lecture we learned about computability. First let's talk about a few definitions. A function is considered to halt when it eventually stops. For some functions we can write a function halt(f, n) that can tell us whether or not the passed function f will halt with the given input n, but we cannot write a universal halt(f, n) function for all possible inputs.
A function is well defined if and only if we can tell what the output is for every input in some domain. A function is computable if and only if it is well-defined and we know how to compute the output for every input in some domain. By these definitions halt(f, n) is non-computable.
We can prove that a function is non-computable by using reductions. If a function, f, can be implemented by using another function g, that function reduces to g. If g is computable, f is also computable and by the contrapositive, if f is non computable, g is also non computable.
This week in lecture we learned about computability. First let's talk about a few definitions. A function is considered to halt when it eventually stops. For some functions we can write a function halt(f, n) that can tell us whether or not the passed function f will halt with the given input n, but we cannot write a universal halt(f, n) function for all possible inputs.
A function is well defined if and only if we can tell what the output is for every input in some domain. A function is computable if and only if it is well-defined and we know how to compute the output for every input in some domain. By these definitions halt(f, n) is non-computable.
We can prove that a function is non-computable by using reductions. If a function, f, can be implemented by using another function g, that function reduces to g. If g is computable, f is also computable and by the contrapositive, if f is non computable, g is also non computable.
Tuesday, 11 November 2014
CSC165 Lecture Week 9
This is my problem solving session. I will be attempting to solve the Free Lunch problem on the problem solving wiki.
Understand the Problem
Devise a Plan
Go through the first couple of natural n by hand and see if a patter emerges.
Carry out the Plan
Look Back
An obvious pattern has not revealed itself. I will take a look at another possible source of a patter: what number each of the people say.
Understand the Problem
You are part of a
group of friends who choose which to treat to lunch in the following manner:
1.
They arrange themselves in an (approximate) circle.
2.
They begin reciting the positive natural numbers, in order, in a
counter-clockwise direction (viewed from above), starting with the friend at
the northern extreme of the circle (who utters "one").
3.
As a friend utters an even number, he or she is eliminated from the
counting (and consideration for lunch). The counting "wraps around"
so that those who avoided one of the dreaded even numbers on the first round
may be exposed on subsequent rounds.
4.
The last person left is treated to lunc.
For example, if there
are friends f1, f2, f3, f4, and f5 arranged counter-clockwise, with f1 at the
northern extreme, the first round would eliminate f2 and f4. Then f1 and f5
would be eliminated in the next round, leaving f3 to enjoy the free lunch.
If there are n friends, where should you position
yourself to get the free lunch? Do you have a technique that will work for any
positive natural number n?
This picture helps illustrate the problem. Basically, you don't want to ever say an even number.
Devise a Plan
Go through the first couple of natural n by hand and see if a patter emerges.
Carry out the Plan
n
|
Iterations
|
winner
|
1
|
F1
|
F1
|
2
|
F1 f2
|
F1
|
3
|
F1 f2 f3
F1 f3
|
F3
|
4
|
F1 f2 f3 f4
F1 f3
|
F1
|
5
|
F1 f2 f3 f4 f5
F1 f3 f5
|
F3
|
6
|
F1 f2 f3 f4 f5 f6
F1 f3 f5
F1 f5
|
F5
|
7
|
F1 f2 f3 f4 f5 f6
f7
F1 f3 f5 f7
F3 f5
|
F5
|
8
|
F1 f2 f3 f4 f5 f6
f7 f8
F1 f3 f5 f7
F1 f5
|
F1
|
9
|
F1 f2 f3 f4 f5 f6
f7 f8 f9
F1 f3 f5 f7 f9
F3 f7
|
F3
|
10
|
F1 f2 f3 f4 f5 f6
f7 f8 f9 f10
F1 f3 f5 f7 f9
F1 f5 f9
F1 f9
|
F1
|
11
|
F1 f2 f3 f4 f5 f6
f7 f8 f9 f10 f11
F1 f3 f5 f7 f9
f11
F3 f7 f11
F3 f11
|
F3
|
12
|
F1 f2 f3 f4 f5 f6
f7 f8 f9 f10 f11 f12
F1 f3 f5 f7 f9 f11
F1 f5 f9
F1 f9
|
F1
|
Initial observations:
It’s pretty obvious that you don’t want to be an even numbered
friend. F1 wins all of the even numbered n except for 6. (Realized that I made
an error once I looked back)
Look Back
An obvious pattern has not revealed itself. I will take a look at another possible source of a patter: what number each of the people say.
n
|
Iterations
|
winner
|
1
|
F1
1
|
F1
|
2
|
F1 f2
1 2
|
F1
|
3
|
F1 f2 f3
F1 f3
4 5
|
F3
|
4
|
F1 f2 f3 f4
F1 f3
5 6
|
F1
|
5
|
F1 f2 f3 f4 f5
F1 f3 f5
6
7 8
|
F3
|
6
|
F1 f2 f3 f4 f5 f6
F1 f3 f5
7 8
9
F1 f5
10 11
|
F5
|
7
|
F1 f2 f3 f4 f5 f6
f7
F1 f3 f5 f7
8 9
10 11
F3 f7
12 13
|
F7
|
8
|
F1 f2 f3 f4 f5 f6
f7 f8
F1 f3 f5 f7
9 10 11 12
F1 f5
13 14
|
F1
|
9
|
F1 f2 f3 f4 f5 f6
f7 f8 f9
F1 f3 f5 f7 f9
10 11 12 13 14
F3 f7
15 16
|
F3
|
10
|
F1 f2 f3 f4 f5 f6
f7 f8 f9 f10
F1 f3 f5 f7
f9
11 12 13 14 15
F1 f5 f9
16 17 18
F1 f9
19 20
|
F1
|
11
|
F1 f2 f3 f4 f5 f6
f7 f8 f9 f10 f11
F1 f3 f5
f7 f9 f11
12 13 14 15 16 17
F3 f7 f11
18 19 20
F3 f11
21 22
|
F3
|
12
|
F1 f2 f3 f4 f5 f6
f7 f8 f9 f10 f11 f12
F1 f3 f5 f7 f9 f11
13 14 15 16 17 18
F1 f5 f9
19 20 21
F1 f9
22 23
|
F9
|
Initial observations:
I actually made one error in finding out who won, so I should
really double check my work.
Winner
|
1
|
2
|
3
|
1
|
3
|
5
|
7
|
1
|
3
|
1
|
3
|
9
|
# said to win
|
1
|
1
|
5
|
5
|
7
|
11
|
13
|
13
|
15
|
19
|
21
|
23
|
Look Back
Still no obvious pattern. I am out of ideas at this point,
and will continue on later and look for more complex patterns.
Wednesday, 5 November 2014
CSC165 Lecture Week 8
This week the most interesting things that we learned was how to count steps and analyze algorithms. I now know that nesting loops is inefficient. Insertion sort with one nested loop has a worst case time complexity of O(n^2). A maximum slice algorithm with three nested loops has a worst case time complexity of O(n^3). Nesting loops greatly increases the number of steps needed to do something.
I also found it really interesting that for upper bounds you can overestimate them because they're upper bounds. A function is upper bounded by another if it grows no faster than that other function, so if that function happens to grow a lot faster, it doesn't matter because it is still an upper bound. Also, you can underestimate them because they are lower bounds. A function is lower bounded by another function if that other function grows slower than the first one. If the other function grows a lot slower it also doesn't matter because it is still a lower bound.
Wednesday, 29 October 2014
CSC165 Lecture Week 7
I have always wondered what something like O(nlogn) meant after my brief foray into reading about sorting algorithms on Wikipedia. Now I know. O() is the notation for asymptotic upper bound. Efficiency is very important in computer programming. Computing time takes up money and resources. Asymptotic notation allows us to analyze the efficiency of functions.
When we say running time, we don't actually mean running time. We mean the the number of steps (lines of code) that need to be executed in order to run a function. With asymptotic upper bound, we focus on the worst case scenario. So if you are searching for an something in the list, the worst case scenario is when that thing does not appear in the list at all. This would require the largest number of lines to be run. As well with asymptotic notion, we do not care about constant terms, and only the highest order term matters. So everything from n^2 to n^2 + 3n + 4 to 109352543n^2 + n + 43243 all belong in O(n^2).
When we say running time, we don't actually mean running time. We mean the the number of steps (lines of code) that need to be executed in order to run a function. With asymptotic upper bound, we focus on the worst case scenario. So if you are searching for an something in the list, the worst case scenario is when that thing does not appear in the list at all. This would require the largest number of lines to be run. As well with asymptotic notion, we do not care about constant terms, and only the highest order term matters. So everything from n^2 to n^2 + 3n + 4 to 109352543n^2 + n + 43243 all belong in O(n^2).
Monday, 20 October 2014
CSC165 Lecture Week 6
This week I learned how to prove a statement about a non-boolean function, how to disprove something and how to prove a limit.
For non-boolean functions, the most important thing for you to do is write down the definition of the function in a logical way. The definition will be used in the proof and it is much easier to use if you have a clear logical statement. To actually figure out the path to the proof, you should try to change the statement to match something in the definitions of the function.
It seems pretty simple to disprove a statement. All you have to do is prove the negation of the statement. It is of course often easier said than done. You still have to prove some statement. To disprove a universal quantifier, the negation is an existential quantifier, so a single example is needed to disprove it. To disprove an existential quantifier, the negation is a universal quantifier, so you need to prove the negation by using some generic element of the sets in question.
I am actually still having some trouble with limits. I've have four midterms this past week, but now that they are over I plan to spend some time practicing limit proofs and looking at some more examples. I get the basic gist of a limit statement.
If epsilon is picked first, there has to be a delta for which the implication holds true. I still am a bit confused as to how you are supposed to find a delta in relation to epsilon for which the implication is true. Once again, I'm probably just going to have to practice, practice, practice.
For non-boolean functions, the most important thing for you to do is write down the definition of the function in a logical way. The definition will be used in the proof and it is much easier to use if you have a clear logical statement. To actually figure out the path to the proof, you should try to change the statement to match something in the definitions of the function.
It seems pretty simple to disprove a statement. All you have to do is prove the negation of the statement. It is of course often easier said than done. You still have to prove some statement. To disprove a universal quantifier, the negation is an existential quantifier, so a single example is needed to disprove it. To disprove an existential quantifier, the negation is a universal quantifier, so you need to prove the negation by using some generic element of the sets in question.
I am actually still having some trouble with limits. I've have four midterms this past week, but now that they are over I plan to spend some time practicing limit proofs and looking at some more examples. I get the basic gist of a limit statement.
Tuesday, 14 October 2014
CSC165 Lecture Week 5
I had my first ever university
midterm this past week and I think I did well. What really surprised me about
this midterm was how easy it was for me to understand the questions. I remember
that during my first lecture we were given a Python function that read
something like this:
def q0 (s1, s2)
return
all ([x not in s2 for x in s1])
It was so confusing at first. I did have some previous
programming experience before taking this class, and I just could not
understand how you could write a line like this in Python. If I wrote this in
Java or Turing like I’ve been taught previously, it would take many more lines.
Something similar was on the midterm and now, I can just read that as a simple logical statement. If we define S(x) to mean that x is an element of s2, that line of code can be written as:
for all x in s1, not S(x).
It is much easier for me to evaluate this simple logical
statement. I am now starting to see why this course is required for computer
science.
Saturday, 4 October 2014
CSC165 Lecture Week 4
This week’s lecture has me extremely worried. We started on proofs, and we were given two examples in class. I understand the basic structure of proofs, but they still honestly look like magic to me.
Assume some condition
Assume P(x)
Then R(x)
Then R2(x)
…
Then Rn(x)
Then Q(x)
Then P(x) implies Q(x)
Then P(x) implies Q(x) for some condition
This basic proof structure, for the most part, makes sense to me. I can see that we are simply just linking two statements together in a neat and organized manner. It's the actual proofs that really stump me. It's like having to learn trig identities all over again, only it's even worse this time. There were only so many trigonometric identities to choose from. Now I have to choose from what seems like every theorem to ever exist in mathematics. I just find it really difficult to jump from one thought to another.
I eventually did learn how to prove trig identities and now I'm actually pretty good at them. That came with pages and pages of practice, so I guess I'm just going to have to practice, practice, practice.
Assume some condition
Assume P(x)
Then R(x)
Then R2(x)
…
Then Rn(x)
Then Q(x)
Then P(x) implies Q(x)
Then P(x) implies Q(x) for some condition
This basic proof structure, for the most part, makes sense to me. I can see that we are simply just linking two statements together in a neat and organized manner. It's the actual proofs that really stump me. It's like having to learn trig identities all over again, only it's even worse this time. There were only so many trigonometric identities to choose from. Now I have to choose from what seems like every theorem to ever exist in mathematics. I just find it really difficult to jump from one thought to another.
I eventually did learn how to prove trig identities and now I'm actually pretty good at them. That came with pages and pages of practice, so I guess I'm just going to have to practice, practice, practice.
Wednesday, 24 September 2014
CSC165 Lecture Week 3
I was always told that university would come with a lot of new challenges, and I think I faced my first one this week. In high school I grasped most topics very quickly and very easily. The only thing I really struggled with were proofs in math, but we didn't have to know them for tests, so I am ashamed to say that I pretty much just ignored them. Now that I actually have to learn this stuff, I have to figure out how to approach these problems. The tutorial exercise for this week took me two hours to do and I had to have a lot of outside help. Hopefully, in the future I will get better at this kind of problem solving.
Question 2 from the tutorial:
To help me solve answer this question, I first went to the CS help centre. I got two bits of information that helped me. First the x on the left and within each set of brackets is not necessarily the same x, but they could be the same x. I also figured out from looking at the online notes that (a) and (b) are actually laws and they are called quantifier distributive laws.
I then Googled quantifier distributive laws to see if I could get a different perspective that would help me. This website http://goose.ycp.edu/~dbabcock/PastCourses/mat235/lecture/lecture06.html, gave me concrete definitions of the predicates, which helped me to finally solve the problems. Let D be the set of people. Let P(x) mean x likes pie and Q(x) mean x likes cake.
Three things to keep in mind:
1. An implication can only be proven false if the antecedent is true while the consequent is false.
2. Or (V) is true when one statement is true and false when both statements are false.
3. And (^) is true when both statements are true and false when one statement is false.
And now my answers to the questions:
(a) is true in both directions. Translating it into English makes it obvious. Everybody likes pie and cake, therefore everybody likes pie and everybody likes cake. Everybody likes pie and everybody likes cake, therefore everybody likes pie and cake.
(b) is always true from left to right. When someone likes cake and pie (proving the right true), that same someone likes pie and that same someone likes cakes, so the left cannot be false. The other way however is sometimes false. Let's say person A likes pie and person B likes cake (proving the left true). There does not have to exist a single person C who like both (proving the left false). The antecedent can therefore be proven true when the consequent is false.
(c) is always true from right to left. Everyone likes pie (proving the left true), therefore everyone likes pie (proving the right true). The other way is false because everyone likes pie or cakes could mean that, for example, half of everyone likes pie while the other half only like cake (proving the right true), therefore there may exist some person A who does not like pie and some person B who does not like cake (proving the left false).
(d) is true in both directions. It's the same as saying: someone likes pie/cake therefore someone likes pie/cake, which makes both sides true.
These are, of course, not formal proofs and I can't Google around for answers on assignments and test, but I'm hoping that this was a decent first step. I learned some new strategies for understanding problems (rewording into something I understand, coming up with concrete examples) so I'm getting better at this.
Now I shall move onto my next challenge of learning to do laundry because I cannot take it home this weekend.
Question 2 from the tutorial:
To help me solve answer this question, I first went to the CS help centre. I got two bits of information that helped me. First the x on the left and within each set of brackets is not necessarily the same x, but they could be the same x. I also figured out from looking at the online notes that (a) and (b) are actually laws and they are called quantifier distributive laws.
I then Googled quantifier distributive laws to see if I could get a different perspective that would help me. This website http://goose.ycp.edu/~dbabcock/PastCourses/mat235/lecture/lecture06.html, gave me concrete definitions of the predicates, which helped me to finally solve the problems. Let D be the set of people. Let P(x) mean x likes pie and Q(x) mean x likes cake.
Three things to keep in mind:
1. An implication can only be proven false if the antecedent is true while the consequent is false.
2. Or (V) is true when one statement is true and false when both statements are false.
3. And (^) is true when both statements are true and false when one statement is false.
And now my answers to the questions:
(a) is true in both directions. Translating it into English makes it obvious. Everybody likes pie and cake, therefore everybody likes pie and everybody likes cake. Everybody likes pie and everybody likes cake, therefore everybody likes pie and cake.
(b) is always true from left to right. When someone likes cake and pie (proving the right true), that same someone likes pie and that same someone likes cakes, so the left cannot be false. The other way however is sometimes false. Let's say person A likes pie and person B likes cake (proving the left true). There does not have to exist a single person C who like both (proving the left false). The antecedent can therefore be proven true when the consequent is false.
(c) is always true from right to left. Everyone likes pie (proving the left true), therefore everyone likes pie (proving the right true). The other way is false because everyone likes pie or cakes could mean that, for example, half of everyone likes pie while the other half only like cake (proving the right true), therefore there may exist some person A who does not like pie and some person B who does not like cake (proving the left false).
(d) is true in both directions. It's the same as saying: someone likes pie/cake therefore someone likes pie/cake, which makes both sides true.
These are, of course, not formal proofs and I can't Google around for answers on assignments and test, but I'm hoping that this was a decent first step. I learned some new strategies for understanding problems (rewording into something I understand, coming up with concrete examples) so I'm getting better at this.
Now I shall move onto my next challenge of learning to do laundry because I cannot take it home this weekend.
Wednesday, 17 September 2014
CSC165 Lecture Weeks 1 and 2
This is my first post for CSC165, so just a quick housekeeping note. This used to be a physics blog for physics class, but from this point forward all posts will be dedicated to CSC165.
Learning about mathematical expression and reasoning or logic is pretty much the same as learning a new language. Instead of learning new words we are leaning new symbols such as ∀ for universal quantification and ∃ for existential quantification. Instead of learning grammar, we are learning new, more precise ways to interpret the English language. Surprisingly, I am actually really enjoying this course, which is odd since I hated those years where I was forced to learn French.
The first week’s topic was very intuitive for me. Universal quantifiers like ‘all’ and ‘every’ can only be proven by looking at every element in the set, and can be disproven by one counter example. Existential quantifies like ‘some’ and ‘there exists’ can be proven by one example and disproven only by looking at all the elements of a set. I think this duality is really elegant and really makes sense in everyday English.
On the other hand, the topic from the past two weeks that I have found most interesting is the vacuous truth and it seems very counter intuitive. It’s pretty weird to think that a statement such as, ‘If the sun does not rise, then pigs will fly’, is true. In everyday English, this whole sentence is absurd. None of these things will ever happen, so it would seem as if this sentence where completely false. Although, once I think about it, the fact that this statement is true starts to make a lot more sense. If P, then Q implications can only be proven false if there is an example where P is true but Q is false. In the case of the statement above, P is never true, so this statement can never be proven false, and is therefore true. I really like how precisely this the rules for implication are defined. It definitely trips me up sometimes, but I do often find everyday English to be too loose and ambiguous, so maybe that’s why I’m liking this course.
Subscribe to:
Posts (Atom)