CSC148 Marth 30th 2015

In this slog, I will be reviewing my earlier slogs on recursion, as well as how my impression has changed.  When I was first introduced to recursion, and practiced implementing recursive functions on tree structures, I felt like I knew how the concept worked, but trying to put all the pieces together to form a function was still difficult.  At that time, what I did was basically copy the format of examples provided during lectures, and making small modifications so that they would work for the lab problems.  However, most of the time I was really just guessing and checking, and even when I managed to solve the problem, I didn't really understand how or why.  That strategy worked until I encountered problems that required me to add in new things, such as multiple if statements in the recursive step.  I think my moment of clarity came as I worked on assignment 2.  I spent 2 days staring at diagrams of trees of gamestate, trying to figure out the link between each of the nodes, how to get from the root to the leaves, etc.  I ended up writing 3 separate functions, and then trying to put them all together in my attempt at a recursive function.  After reading the assignment sheet again, I started to look at the problem from another approach.  Instead of looking at the entire tree, I decided to only looked at the root and its children.  Doing this allowed me to figure out the base case of minimax, because each children is also a leave.  Then, I added children to the leaves of the original tree, and looked at the relationship between the root and its children, as well as the children and the grandchildren.  This is how I figured out the recursive step, and what helped the most was the realization that whatever the root asks its children, the children will ask the grandchildren.  This simplified by though process A LOT, as I only needed to think about one relation, instead of trying to think about all the possible interactions between every node in the tree.

I also read a few of my peer's slogs, notably Ken's at "http://slogfor148.blogspot.ca/".  Ken's post about recursion gave me a new perspective on how one can approach recursive problems.  Ken wrote that when he encounters a problem, he usually thinks about various code that can be possible solutions, while I tend to first try to figure out what sort of computations a human would do to solve a problem, and then translate that process into code.  Thinking directly in code definitely has its benefits, as there are many shortcuts and functions that can compress the steps that a human mind might take.  Another very important lesson that I learned from his post is how he analysis the data structure of the problem, and how his solutions can be generalized to work with difference scenarios using the same data structure.  This way of thinking will cover any potential holes or bugs that the code might encounter on different objects of the same data structure.

CSC 148 March 27th 2015

Normally I would be discussing this week's material, but I realised that I forgot to write a blog last week so this one will be based on the materials covered in week 10.

In week 10's lecture, Professor Heap showed us his sample solution of minimax, as well as introduced assignment 3.  The sample solution pairs every possible move of a gamestate with a score of 1, -1, or 0, depending on whether or not the move can guarantee a win.  Then, the sample solution will pick a move that has the highest score, and return it.  The sample solution is much shorter and more efficient than my code, because my solution uses two functions instead of one.  One of my function essentially takes a gamestate, and returns a score.  The second function uses the first one to determine the score of the opponent's gamestate, and picks the move that leads to the gamestate with the lowest score.  The main reason I split it into two functions was because when I tried to use max() on a list of tuples, where each tuple had an int representing the score, and a move, I kept getting errors because I didn't implement any methods that compared moves to each other.  The Professor showed us that we can use the max() function on only the first index of each iterable, and I will use this to rework my minimax strategy.  Other than that, we talked about how to create test cases to test our code.  These test cases should include as many possible scenarios as possible.  For minimax, there could be cases where there are no winning moves, gamestates where all moves are guaranteed wins, and gamestates that has a mixture of both.  We also discussed the difference between global and local variables in a tracing exercise, which is similar to questions that were tested on in 108 last semester.  Overall, the content this week was pretty mild, and I look forward to the materials next week.

CSC148 March 16th: Linked List

In this post, i will be talking about linked lists and linked list nodes, which was covered in class a week ago.  Last week was the second midterm of 148, and i think it went pretty well.  The three quests were very similar to tutorial problems that i have solved before, and i was able to breeze through them without many difficulties.  Now, onto linked lists.

I was taught that there are two main approaches to visualizing linked lists.  One is of lists that contained some data, and possibly another linked list.  This way, inside each linked list could be another linked list, and thus the lists are linked.  The other approach is the one that this course will be taking, which is of objects(nodes) that contain some data, and a reference to another object(node).  With this approach, we will need to defined the object(node) as a class, and also a wrapper that contains the linked list as a whole.  This concept was simple enough, however when it comes to implementing methods that manipulates linked lists, things become more complex.  To me, i think of a linked list as a train, with a beginning node, intermediate nodes, and an ending node.  However, these nodes do not have any form of indexing, and so to manipulate a specific node, i must use a loop that moves down the linked list one node at a time, starting from the beginning.  The difficulty of doing this is that you really don't have a way to knowing exactly the location of the current node in the linked list.  All you know is the data that the current node contains, and its previous and next nodes.  That's why when iterating over linked lists, it is important to be able to clearly visualize how your loop will work, so that you don't end up manipulating the wrong nodes, or worse, severing the link of the linked nodes.

CSC148 March 8th 2015

Much of the focus of this week was on assignment 2, and i must say, the process of writing recursion became a lot more clear to me after figuring out how to implement minimax.  In my last post, i said that to me, writing recursion is just like induction.  First, find the base case, or cases, and then apply the inductive step.  Generally, the recursive step in writing functions is harder than identifying the base cases, but i think have finally discovered a way of thinking that will allow me to arrive at the correct recursive step.  When i worked on recursive functions in previous labs, after identifying the base case, i was often stuck thinking about what steps i need to repeat, and in what order.  Determining where place the recursive call was also difficult, as i end up thinking about too many factors all at once.  However as i worked on minimax, i began drawing my own trees, branching out from a root gamestate.  I knew what the base case of the function was, but i had trouble bringing the base case results from the leaves of the tree all the way back to the root.  After spending hours staring at the tree that i had drawn, i suddenly realized that recursion is much simpler than what i had thought.  Instead of looking at the tree and trying to think of a process that passes information from each of the leaves all the way back to the root, all i needed to do was look at how the information is manipulated between each level of nodes.  I started by looking at only the root and its children.  The root will ask each of its children a question, and then process all the answers into a single answer.  This is basically the recursive step that i was always over thinking about.  As long as i can figure out what the parent should ask its children, and how the parent can process all the answers into one, i can repeat this question on the children of the children, and so on, until the base case us reached.  This way of thinking really made the process of recursion seem much less daunting, and i am sure it will help me in the upcoming midterm.

CSC148 February 29th 2015 Writing Recursion

In this post, I will be writing about object-oriented programming as well as writing recursion, to make up for the blog post that i forgot to write during reading week.

Object-oriented programming is a term that i first heard of near the end of CSC108, as we began learning about writing our own classes.  At that time, my understanding of OOP is simply what my professor had taught me, a way of programming that focuses on objects.  I learned after doing some research that OOP is focused on objects rather than actions, and data rather than logic.  In this model, objects are well defined data structures that can be manipulated through methods, and objects can also interact with each other through methods.  Programs that are built on OOP are essentially objects that interact with one another though logical functions.  Python is a common type of OOP language, as are C++ and Java.

In Python, objects are defined by their class, which may be inherited from another class.  These classes may be modified versions of generic data structures such as lists, and in turn they may be modified into objects such as queues and stacks.  Classes not only represent objects through different data structures and attributes, but also include ways of how these objects can be manipulated.  For example, a class that represents a circle may have methods that adjusts the radius of the circle, as well as tell whether or not two circle objects are the same.  Classes can even represent complex objects such as chess, and different chess strategies.  With creativity, i believe a great deal of both real and abstract objects can be defined by Python classes.

Now onto recursive functions.  The focus of the last two weeks of 148 was the writing of recursive functions.  As i have mentioned in a previous post, the process of writing recursive function is really similar to induction to me.  First i have to find a base case, which in most recursive functions is the basic output on a simple object.  Then, the recursion will repeat a certain process over and over until it reaches the base cases, and then it will perform a boolean function on the base cases.  However, in the last lab, i practiced writing more complicated recursive functions that involved if statements.  Though i was able to figure out how to implement the 4 practice functions, i feel like i still havent grasped the intuition of recursion yet.

CSC148 February 9th 2015

The highlight of last week's CSC148 is the first midterm of this semester.  Having gone to Danny's lecture for 165 last semester, I had a pretty good idea of what I should be expecting, and i was very nervous before the test because truthfully i feel like i haven't learned a whole lot of new stuff since the beginning of this semester.  As i recall, the first 165 midterm was a simple, yet difficult test to me, and i didn't do particularly well on it either.  After reading over the lecture slides as well as the lab handouts multiple times, i felt like i had a good grasp of what will be tested, mainly writing classes and subclasses, and a bit of recursion tracing as well.  The test itself was surprisingly simple, and did not require much "smart" thinking.  Practice from assignment one on writing classes and subclasses certainly helped me feel at home as i worked through questions 1 and 3 on the test.  The recursion tracing bit was also pretty simple, as long as i took the time to write out the steps instead of being lazy and trying to cut corners.  However after writing the test, i realise that i misunderstood a method in the first question, which many cost me a fair bit of points.  The method that Professor Heap intended us to write was one which stores information passed in as arguments into an object attribute.  When i read the question, i thought that i was required to also prompt the user to give an answer as part of the method, and so my code was unnecessarily long.  The lesson that i have learned from this is to read each question description thoroughly, and never assume i know what i am asked to do and skip reading the latter part of the question.

CSC 148 February 1st 2015: Recursion

During this week's lecture, i learned about recursion: what it is, how it looks like in code, and how to trace and understand it.  When the professor opened with the example question of how we can add up integers in an arbitrarily nested list, i thought the solution would be using some sort of while loop, and that recursion was simply repeating the same action many times until the desired result is obtained.  However, instead of using loops, the solution to the problem was a function that calls itself in its body.  At first i thought, will this really work?  Wouldn't Professor Heap just get some sort of name error saying that the function name is undefined?  But it worked, and the idea of a function calling itself confused me to no end.  The only similar thing that i have seen was when Professor Heap introduced the idea of uncomputable problems using halt and naval gaze, and that example was a very confusing one already.  However, after working through some tracing exercise for the example function, i realized that tracing function calls on simple to complicated arguments really helped me understand how the function itself works.  For example, with the problem of finding the sum of integers in arbitrarily nested lists, i started with example calls on ints, then a single list, and then a list of depth 2, and so on, and i found that tracing recursion is much like expanding out a compact mathematical equation.  Starting with the function call on the argument, recursion causes the function to be called on each element of the iterable argument, and then on each element of those, and so on, similar to expanding functions such as (x-3)^3.

During the lab this week, i did some more tracing exercises, and i found that by tracing, i could more or less figure out the gist of a function, however i think that if i were to use tracing to figure out the purpose of a function, i need to come up with relevant examples, for example passing in strings to a function thats meant to work on ints and lists wont achieve much.  Just when i thought recursion was a pretty simple idea, i got stumped on the last exercise of the lab, which was to write the body of a recursive function.  At this point, i knew that i should include an if statement to essentially separate the arguments of the function into two types, one where object type that the function is intended to work on, and the other where basically every other object type is filtered.  The tricky part was implementing the recursion.  The function that i needed to write is supposed to find the maximum length of a list in the argument and return that number as an int.  I knew that i had to work with len() and max(), however i was stuck on which process i should repeat(with recursion).  I knew that i needed to find the length of every list in the argument, and somehow use the max() function to compare them to each other, but there are also other objects such as ints in the argument, and when trying to pass an int to len(), i get an error.  Furthermore, int isn't an iterable object, so i cannot use list comprehension to build new lists with len().  I tried to think about the very basics of this problem.  The recursive part will repeat that section of the code on every list in the argument, but how do i go deeper and look at each element of the list?  In the end i ran out of time before i had to complete my quizz.

At the end of the tutorial, i gave up and asked my T.A. on the possible solutions of this problem, and she showed me a much simpler and different method of implementing this function.  Instead of creating a list where each element is an int that represented the length of each list in the argument, i can simply use the max function to compare the length of the outmost list to the length of every list nested inside of it.  After thinking about it more at home, i finally came up the solution:

return max( [len(L)] + [length(x) for x in L])

CSC148 January 25th 2015: Why Geeks Should Write

Why should geeks write?  The answer to that question varies depending on what kind of a geek you are, but if you happen to be interested in computer science, then this blog is for you.  I started writing this blog at the beginning of September 2014, for my first year computer science course CSC165.  At first, i thought being asked to keep a blog is a simple way for the professors and instructors to see whether or not we are taking our course seriously, as well as to add some additional homework to the sparse amount of work that we have.  However as the semester progressed, i realized that i've begun to use this blog as a way to review the materials that i have learned in the previous week, as well as evaluate my understanding and figure out what topics i still need to study.  Writing the weekly blog has allowed me to remind myself of topics that i need to study further, or to ruminate over problems that i have not yet been able to solve.  To me, i am writing so that i can organize the knowledge that i have gained from my classes, as well as to make sure that i do not become lazy and skip over topics that i can only vaguely understand.  However, this is only one reason for writing.

Being a geek means to be obsessively enthusiastic about topics of interest, and through this enthusiasm, many self discoveries and learning will occur.  As a beginner coder, i have no yet worked on any really useful programs, however from reading the blogs of other programmers, i have learned that keeping a debugging journal is in many ways similar to how ive kept a blog to reflect upon my studies.  Mark Dalrymple, a software developer mentioned in his blog that by keeping a log of bugs that he has found in his code, even if they seem insignificant at the moment, can be the key to debugging errors in the future.

Although writing has many benefits to the writer in the form of reflection and evaluation, but if made public, the contents of these blogs can also share many wonderful problem solving techniques to people all over the web.  Developing further on this notion, one can even write with the sole purpose of guiding or instructing others on how to do certain things.  I know that most of the time when i encounter software issues, such as when programs crash, i often rely on googling for solutions provided by other people.

In conclusion, writing is a wonderful way of communicating both with youself as well as with others, and geeks should keep on writing so that more and more ideas can be shared across the web.

SLOG 11 December 2nd 2014

During the last CSC165 class, I worked on a problem called diagonal with a friend of mine.  The problem involves rectangles that are made of squares with 1 unit area.  The problem is that if a diagonal line cuts a rectangle from corner to corner, how many unit squares within this rectangle will remain intact and how many will be cut?

The first step was to understand all the known and unknown of this problem.  Because the rectangle is made of squares of unit length 1, that means if we know the length and width of the rectangle, we are able to calculate how many squares are in this rectangle.  The problem involves finding two numbers; the number of squares in the rectangle that isn't cut, and the number of squares in the rectangle that is cut.

The second step was to devise a plan.  Initially, the handout had a picture of a 4 by 6 rectangle, and i realized that the line intersects the mid point of the rectangle.  What this helped me realize was that the rectangle can be split into two identical 4 by 3 rectangles, which means if we can find out how many squares are cut in this rectangle, i can just double that number to find the number of squares cut in the 4 by 6 rectangle.  However, after thinking about this plan, i realized that if the rectangle had odd side lengths, then the rectangle cannot be cut into more rectangles evenly.  After this stumbling block, i got stuck on the problem for quite some time, thinking about the possible ways of splitting each rectangle into smaller components.  Then, i suddenly realized that the diagonal line itself splits the rectangle into two identical triangles!  My plan was then focused on trying to use what i know about the triangles to calculate how many uncut squares exist inside.

With the triangle, i know that i can calculate its area, but that wont help me very much because the area represents the entire surface of the triangle, not the area of each square plus the left overs.  After much brainstorming, my friend and i realized that the triangle reminded us a lot about integration.  We drew many triangles of varying base and heights, and then divided the triangle into unit squares to see which squares are cut and which are not.  For example, imagine a triangle of base 4 and height 2.

This triangle can be viewed as 4 columns with a slanted top.  If we can find the height of the shortest side of each column, then we can find out how many uncut squares are in that column.  Then, we just need to add up all of the uncut squares of each column to find the total number of uncut squares in this triangle, and multiplying that number by 2 will give me the number of uncut triangles in a rectangle with width and length equal to the base and height of the triangle.

How can we find the height of each column?  Well since we can calculate the slope of the triangle by (height/base), we can use the slope to find the height!  Referring back to the 4 by 2 triangle, the slope will be 2/4, which is equal to 1/2.  So starting from the right most column of the triangle, this column is actually a triangle itself.  That means its height on the right is (0 X 1/2) = 0, and its height on the left is (1 x 1/2) = 1/2.  So we know the height of the two sides of this column, but neither of them are above one, so we can conclude that there are no squares in this column.  Now lets move onto the second column from the right.  The short side of its height is (1 x 1/2) = 1/2, and the long side of its height is (2 x 1/2) = 1.  We know that one of its side is 1, but the other side is less than 1, so its impossible for a square to be in this column either.  On the third column, the two heights are 1 and 3/2.  Now, both sides have a height greater than 1, so that means there is a square in this column!  On the last column, the two heights are 3/2 and 2, and since the shorter side is greater than 1, that means there exists another square in this column.  That means the 4 by 2 triangle has 2 uncut squares, which means a 4 by 2 rectangle will have 4 uncut squares, and that (8-4) = 4 squares are cut by the diagonal line.

To summarize this solution, we have come up with a formula that has been tested with numerous triangles and have worked in all cases tested so far.

What we discovered was that if knowing the longer height of a column will give us the number of squares in the next column, because in the next column, this height will be the shorter of its two heights, and if this height can be rounded down to a whole number, then that number represents the number of squares in the next column.  In the formula above, l represents the length of a rectangle, which is the same as the base of the triangle cut from this rectangle.  W represents the width of the rectangle, which is also the height of the triangle.  (w/l) is the slope of this triangle, and i represents the the distance from the tip of the triangle to the next column height.  The floor rounds the height down to a whole number, and the summation adds up all of the number of squares.  The reason why i only goes up to the second last column height is because we only need the previous height to know the number of squares in the next column.

The blog of the student i worked with can be found here:
http://kenguoslog165.blogspot.ca/

His latest blog should be an account of how we solved this problem in his point of view.  Its worth checking out, as thought we arrived at the same conclusion, we had different approaches and methods that helped us get there.

SLOG 10 November 23rd 2014

During this two lecture week, I learned about the existence of problems that cannot be solved through algorithms.  During the first lecture, the professor introduced the problem about finding out whether or not a program will halt, or stop, either because it has completed its task, or due to some error.  We can't simply run the code and determine whether or not it will halt, because we cannot determine whether the program is taking a long time or if it is stuck in an infinite loop that will never end.  However, there is a function called halt which is able to return a boolean representing whether or not the function being tested will halt.  One of the problems that the professor introduced to us is about the function naval gaze.  What naval gaze does is that it calls halt upon halt, and the conclusion is that the results are always contradicting what the function is supposed to do.  I did not understand exactly how this concept worked, and i was planning on studying the notes this weekend, however the course website is not yet functioning, and all of the links of the cache didn't work, so I'm planning on going to the professor's office hours next week in order to get a better idea of why some probems can't be solved through computations.

SLOG 9 November 17th 2014

During last week's CSC165, I learned about what big O and big Omega meant, and how the functions look like graphically, as well as how to prove that some functions are of big O or big Omega of others.  I learned that a big O function of a function f is a function that always produces a y value greater than f(x) when x is greater than a certain value.  This value is denoted as B, the break point.  The value c in the definition of a big O function is essentially the multiplier that makes the big O function greater than f.  Big Omega is basically the same as big O, except big Omega is a function that is always below function f after the break point.  What below means is that every y value that big Omega returns is less than f(x).  Then, knowing the full definition of big O and big Omega, the professor showed us a number of new relationships that about big O and big Omega.  I learned that when attempting to prove these relationship, it is much easier to first picture the relationship in my head.  For example, if the statement is something such as ' if f is O(g) and g is O(h), then f is O(h)'.  Thinking about this scenario graphically, i realise that f is bounded above by g, which is bounded above by h, so f is also bounded above by h.  I think that the difficult part of these proofs is not finding the c value, but locating the correct B, because the value c's relationship to the functions is directly shown through the definitions of big O and big Omega, but B is only found when we start creating boundaries of n through our manipulations.  Therefor, it is sometimes hard for me to keep track of all of the boundaries that i have set for n through my proof.

SLOG 8 November 9th 2014

During this week's CSC165, i was primarily focused on studying for the second term test on proofs.  Prior to the test, i had just finished assignment 2, and felt pretty confident about proving universal and existential claims, as well as how to write the format of proofs in general.  I studied last year's test, and found it to be very easy, especially since there were only 3 questions.  After writing the test, i found question 1 and 3 to be very standard, however question 2 was not as easy.  For question two, i was asked to disprove a statement, so i took its negation and began attempting to prove it.  However, due to my being conditioned to relate variables e and d to limits, it took me a long time to understand the actual statement and its negation, and even then i made the mistake of defining one of my variables d as e times 2 instead of e plus 1.  This lead to many problems as i continued my proof, and only did i realize my error when time was up.  Alas, i had written the proof structure so hopefully i wont lose too many marks on that question.  Before this week, i was also quite confused about the 'steps' and big O notation that we had been covering in class, but after the tutorial exercise that focused on counting the steps of an algorithm, and finding its worst case scenario (which is when every loop is evaluated for the maximum number of times).  On Friday, the professor showed some more proofs of how some functions are of big O notation, and from these proofs, i learned that there is much more freedom in manipulating variables and inqualities when proving big O.  For example, when showing that 3n^2 + n is of On^2, the professor showed that we can simply turn n into 2n^2, because 2n^2 is always bigger than n, and then express 3n^2 + n with an less than inequality as 5n^2.

SLOG 7 November 4th 2014

The focus of this week's CSC165 was on assignment 2.  There were a total of 6 statements that were in assignment 2, which needed to be proved or disproved.  The first question involved using the floor, which was something that had been covered in class previously.  However, upon starting question one, i realized that the statements were actually quite difficult to prove fully.  For the first statement, i attempted to use part of the definition of the floor of x, which was that if a natural number z is less than or equal to x, then z is less than or equal to the floor of x.  I wanted to split the antecedent,  which was: if z ≤ x, into a disjunction of z less than x or z equal to x, and then use one part of the disjunction to prove the statement. However, my partner said that I can't just split the less than or equal to sign into a disjunction, so we ended up spending a lot of time thinking up an alternative solution. In the end, we came up with a solution which involved introducing new variables into the proof after talking to Professor Heap to make sure we can do it. The second and third statements were the most difficult of this assignment. The hardest part was to first figure out whether or not these statements are true. From calculus, i recognized 1.2 and 1.3 as definitions of limits, and so i wrote the statement in its limit format, which was: the limit as x approaches w of floor of x is equal to the floor of w. After figuring out the meaning of the statement, i drew the graph of the floor of x, and quickly realized that the statement was false. The disprove of this function involved finding the negation of the statement, which had 3 existential quantifiers. At first i wanted to pick a value for each of the existential quantifiers, but then i realized because there is also a universal quantifier before the last existential, i can only write the last existential(which is w) in terms of the universal (which was d).

The biggest lesson i learned from doing assignment 2 is that before i attempt to jump into the proof, i should first make sure i understand exactly what it is saying, and try to visualize the relationship. I realized as i were doing assignment 2 that often times i get stuck because i dont see the relationship between the numbers and variables, however after i visualize the statement graphically, i can figure out whether the statement is true of false much quicker

SLOG 6 October 27th 2014

During last week's lectures, we finished covering methods and formats of proofs and moved onto discussing algorithms.  We reviewed some main strategies that we should employ when starting proofs.  For example, to prove universal, we show that there are no counter examples, to prove existential, we just have to find one example.  For implication, we start with the assumption and try to reach the conclusion.  For and statements, we must show that both propositions are true, and we can do this by tackling each proposition independently and then checking to see if both are true.  For or statements, we can also tackle each proposition individually, and as long as one is true, the claim will be true as well.  I learned that these links can also be used to introduce new claims or objects into the proof.  For example, if we know that an implication is true, then we can introduce the consequent when we reach the antecedent in the proof.  Then, we can use the consequent as the antecedent to introduce other implications to eventually reach what we want to show.

We started algorithms by talking about sorting algorithms, which are algorithms used to sort/organize data.  We talked about the the number of steps, or actions that each algorithm takes to complete its task.  When analyzing the speed of algorithms, I can look at their average speed, best case speed, and worst case speed.  For now, I learned that we should focus on looking at algorithms based on their worst speed, because the best speed is not 100% consistent and won't tell us much, and the average speed will take far more effort to calculate.

Lastly, on Friday I worked on a problem involving two drawers and 64 pennies.  To begin, all 64 pennies are in one drawer.  As long as the number of pennies in a drawer is even, I can take half of that number of pennies and move it to the other drawer.  The opening question is to find a way to have 48 pennies in a drawer.  I realized that because I am always splitting the number in half, then the number of pennies in each drawer will always be a combination of some exponent of 2.  For example, 64 is 2^6, which splits into 2^5 and 2^5, which can then split into 2^5+2^4 and 2^4.  2^5+2^4 is 48, so I solved the opening problem without much difficulty.  However the real question was whether or not I can get all numbers from 1 to 64.  When I started thinking about this problem, I realized that since there are two drawers, and the sum of pennies in both is always 64, then if I can get numbers 1 to 32 to show up in one of the drawer, then 32 to 63 will be in the other drawer.  My plan was to create a diagram showing all possible combinations of sums of exponents of 2, and showing that it can represent all 64 numbers, but I was very time and space consuming and I was unable to solve it yet.  I think professor Heap showed this question to us because it is similar to algorithms; though many do the same job, some do it much quicker and require much less space.

SLOG 5 October 20th

Last week I only had 2 lectures of CSC165 because of Thanksgiving, and the focus of the two lectures were on the structure of proofs.  Professor Heap repeated the the structure of proofs on a few different examples, such as proofs involving floors and limits.  I learned that the beginning of each proof always starts by defining the main variable as part of the set of real, integers, natural, and etc.  The second step is to assume the antecedent, which is pretty easy to identify when it comes to limit proofs because of the implication.  However when doing proofs about the floor of a variable, it is also crucial to put its definition in the proof.  Essentially, I learned that I should put all of the conditions that I know is true as an assumption before I begin the thinking part of the proof.  After finishing the assumptions, the next step is to somehow arrive at the consequent from the antecedent.  The difficulty of this step varies greatly.  For example, with a limit proof, it was quite easy for me to complete the thinking part as I have done limit proofs in math.  However with floor proofs, I often get stuck about how I should proceed.  However with more practice, I believe that I will be able to arrive at the fundamental insight that will allow me to complete the proof quicker in the future.  After arriving at the consequent, the last section of the proof is to finish the assertions made earlier.  The middle section of the proof will have proved that because of the assumptions made, the consequent that we arrived at is true, so the last section is basically re writing the first section.

SLOG 4 October 13th 2014

During the two lectures of this week's CSC165, I learned more about proofs, and also went through some examples of how to prove universal and existential claims.  From what I've learned during the first few weeks of class, proving a universal claim means to show that there are no counter examples, and proving an existential claim is showing one example.  Because of this, proving an existential claim seems easier because i just need to find a number or a set the matches both the antecedent and consequent of the claim.  Proving universal claim is much more difficult, as it involves defining the antecedent, and then trying to turn the antecedent into the consequent through mathematics.  Writing proofs is something that I have been learning in my MAT137 class for the past few weeks as well, and learning how to write proofs in CSC165 has actually helped me understand the proofs in MAT137 more clearly.  This is most likely because we used simpler examples, and Professor Heap went through the thought process of each step.

Although this week's class wasn't difficult, the midterm on Wednesday told me that I have much to learn in this class.  Prior to the midterm, I have felt very confident about 165, since I was able to almost all of the tutorial problems and have gotten full marks on every quiz.  I looked over some rules about symbolic expressions and studied last year's midterm as well as the assignment 1 answers.  However on the midterm, though i was able to breeze through question 1 and 2, i got stuck on question 3 for a very long time, and in the end handed in my test before i was able to come up with an answer.  When i first looked at question 3, and the complicated statement 3, i automatically assumed that i need to transform it into its contrapositive or a simplified version, and so i began doing that, thinking the answer will eventually become evident.  It did not, and only after the exam did i realise that i should have just focused on understanding the two original statements instead of trying to transform them into some other form.  This exam taught me to not assume anything about the questions on an exam, and hopefully i will be able to do better on the next one.

SLOG 3 October 4th 2014

In this week of CSC165, I learned about transitivity, the importance of the order of quantifiers in a statement, and the guideline to proofs.  However, the majority of the focus during this week of CSC165 was on the assignment that was due at the end of the week.  For this assignment, I worked with 2 other students in a group of three to produce the best answers that we could come up with.  Our method of ensuring that we all share the work load equally was by completing the assignment individually, and then comparing and merging our ideas and answers to produce a final version.  I felt that of the 5 questions in the assignment, the difficulty level of the questions increased from question one to questions five.  The first question was fairly basic translation of sentences to its symbolic form, and then negating the symbolic statements.  This section was mostly applying the correct negation methods and understanding the sentences properly, which did not cause me a lot of trouble. 

For question 2, I realised that I could substitute some of the predicates such as honor and persistent into one, which simplifies the statement and made comparing it to the original much easier.  It was the method we agreed to use to explain whether the statement is the converse, contrapositive, or the negation. 

The third question became a bit trickier, as it involved creating sentences myself to match the description of the questions.  My plan was to simply translate the sentences to its symbolic counter parts and vice versa, but soon I encountered statements that required complicated construction of quantifiers, predicates, and relationships.  The most difficult question in part 3 was to express that Zorn was enrolled in all courses but Zukes.  I spent a lot of time thinking about how to create the expression ‘there exists only one’ symbolically, and my initial answer was to say that for all x of classes that Zorn is enrolled in, there exists a set y of class that Zorn is not enrolled in, if x is in the set of classes that Zorn is enrolled in, then x does not equal y, and y is equal to Zukes.  At first I thought this answer was sufficient, however later I discovered that I merely said that Zorn in not enrolled in Zukes, meaning I had failed to express that Zorn is enrolled in all other classes.  After discussing with my partners, they showed me that if I said for all x, if x is a class and x is not equal to Zukes, then Zorn is enrolled in x.  This statement expressed that Zorn is enrolled in all x that is not the course Zukes. 

Question 4 was short, but although I knew that there are differences between conjunctions and implications, I had difficulty coming up with exact examples to prove one wrong and the other right.  However after thinking back to the rules about proving and falsifying universal and existential quantifiers, I remembered that to prove a universal wrong, all I needed was to show a counterexample, and to prove an existential wrong, I needed to show that there are no examples.  The final answers and the explanations are too long for me to put into this blog, but the main idea is that for implications to be wrong, P must be true and Q must be false.  However for conjunctions to be wrong, either one being false will do the trick. 

For question 5, my way of finding which implies which was to create truth tables.  I viewed each statement as a predicate, and then created a truth table to see if the second statement is true or not depending on the antecedent statement.  This question took me the longest to solve however because I did not know exactly how I should be finding out which statement implies which.

All in all, I know that I have answered the questions and shared my reasoning with my partners as best as I can, and I am confident with the results of this assignment.  

SLOG 2 September 27th 2014

               In this week of CSC165, I learned about conjunction, disjunction and negation.  The conjunction and disjunction were very similar to the ‘and (n)’ and ‘or (u)’ used in sets and Venn diagrams, and so it was fairly easy for me to understand what they mean.  Disjunction and conjunction are also identical to the “and” and “or” commands in Python, which I had learned in CSC108 already, so I was able to understand how they are used to evaluate statements and implications.  Basically, conjunction is used when the conditions on either side of the sign must all be true in order for the statement to be true.  For disjunction, only one of the condition being true will satisfy the requirement for the statement as a whole to be true.  However, the use of brackets can modify which requirement comes first, whether conjunction and disjunction, and during the tutorial this week I went over some example statements that gave me a better grasp of how conjunction and disjunction is used.  To not be confused by the order of the requirements, I like to underline parts of statements that need to be considered first.  For example, if the statement was (P n Q) u R, I would draw a line under (P n Q), and another under R, so I know which two objects I’m looking at and whether disjunction or conjunction is the main requirement of the statement. 

I also studied negation during in this week, and over negation wasn’t a difficult concept to grasp.  It is basically the opposite of what is being said.  That means if a statement is true, then its negation is false.  However, one problem I tend to have when dealing with negation is that I often confuse them with contrapositives.  What I mean by this is that when I try to find the negation of a statement, I end up finding the contrapositive instead.  To prevent this problem from reoccurring repeatedly in the future, I realised that the negation is the opposite of the statement, so if I put another negation sign in front of the negated statement, then I would get the contrapositive. 

Lastly, during the class on Friday I had the opportunity to work with my friend on a problem which involves finding and expressing the patterns of up and down creases of a paper strip folded n number of times.  I devised a plan to first observe the first 4 folds and discover the basic relationships between the number of folds n, the number of layers after being folded n times, and the number of creases c.  We found that the number of creases can be calculated using the formula 2^n – 1, which helps us understand how many creases there are.  However the problem of how the pattern of ups and downs go still remain unsolved.  We drew a diagram depicting the ups with arrows pointing up, and downs with arrow pointing down, and discovered that there exists a central crease which remains the same at all time.  Every time the paper is folded, new creases are generated on either side of existing creases, and the new creases have an alternating orientation of ups and downs.  The biggest issue we encountered was to express this pattern mathematically.  This was the most frustrating because although we know the pattern, we could not express it in a way that the pattern of creases for any number of folds can be calculated.  After doing some research about the problem at home, I learned that a type of function called recursive function can be used to predict the pattern.  This is because recursive functions are basically looping functions that uses the output as the input, thus if we can enter the basic pattern of how the creases are added, then the final crease pattern can be predicted with the function.  

SLOG1 September 17th 2014

In this week of class, I learned how to understand ideas that are expressed in various mathematical and linguistic forms.  During the first week of class, I was introduced to the basic if and then expressed as events P(x) and Q(x).  It was easy to memorize all 4 different combinations of truths and false of P and Q, but I had a hard time understanding why the if and then statements are true even when P is false.  Besides the if and then statements, I also had a difficult time visualising the all and any statements, and I had a lot of trouble when I had to work on some problems in class.  In the following classes during the first week, I was taught about the universal and existential quantifiers.  Unlike the if and then statements, I have never seen the two types of quantifiers before, and so I didn’t really understand what was going on in class, especially when the professor gave examples of statements that are expressed with the quantifiers, and what they meant in each scenarios.  All I could do during lectures was memorize and copy down as much material as possible, and try to think about them after class.  However, during my MAT137 class, I was taught about universal and existential quantifiers with much more detail, and I realised that the quantifiers are essentially just another way of expressing if and then statements without using P(x) and Q(x).  I also learned about vacuous truths in math, which helped me understand why if and then statements are true even if P is false. 

One of the most important thing I learned in class which really helped me understand the different ways of expressing implications was the rules to verifying and falsifying universal and existential claims.  I learned that:

-        To verify a universal claim, show that there are no counterexamples

-        To falsify a universal claim, show at least one counterexample

-        To verify an existential claim, show at least one example

-        To falsify an existential claim, show that there are no counterexamples

With these rules in mind, I began to translate if and then statements into their universal and existential forms, and by using the rules, I was able to figure out what needs to be true and what needs to be false in order for the statement to be true or false.  The tutorial exercise which involved expressing if and then statements with venn diagrams gave me a stronger visualisation of what is being described by if and then statements, and which areas must be empty and which areas must be occupied for various statements to be true.  I also found out after examining the 4 rules above that verifying a universal claim is the same as falsifying an existential claim, and falsifying a universal claim is the same as verifying an existential claim.  It is then that I saw the connection between universal and existential claims.  By the end of this week, I believe I have a good understanding of what has been covered in lectures and tutorials, and I am confident that my level of understanding increase as the weeks pass.