Wrapping Up

This blog post will be the final post in this blog. I was skeptical to the use of blogging about CSC165 but in the end it did have a positive effect. Writing is something I already enjoy doing and putting my thoughts and problems into words helped to create plans to tackle these problems head on. It was a pleasure to learn CSC165 under Professor Heap, who is, without a doubt, the best Professor thus far in my university experience. Hoping to learn under him again in the upcoming years! Last week's blog post went over the Penny Piles problem. My initial approach was to construct a program, as seen in the previous post, but after some testing this program was found to be faulty. For example, it would return that it was not possible to reach a pile with only 1 penny. However, consider the following approach, going backwards:

1 63 

2 62 

4 60 

8 56 

16 48 

32 32

64 0

Simply always moving half over to the right pile allows you to reach one. This one counter example causes my program to not be a viable solution. Let's take a look at the problem using a systematic approach, Polya's approach:

Understand the Problem

This problem forces the solver to determine whether it is possible to reach a certain amount in one drawer from a given starting point. On each of the drawers, the following operations may be employed: L: Iff the left drawer has an even number of pennies, you may transfer half of them to the right drawer. R: Iff the right drawer has an even number of pennies, you may transfer half of them to the left drawer.

Devise a Plan

The first idea was to construct a program that can simulate and determine whether scenarios can be reached. As seen in past weeks blog, a program was created but as disproved above, it is not functional. My next option was to run some manual simulations and try and find a pattern. A tree can be created showing all the possible outcomes with the following starting drawers [64, 0].

Carry Out the Plan

The following is a tree constructed starting with drawers [64, 0]:

64
32 32
16 48
40 24 8 56
20 44 52 12 4 60 36 28
10 54 42 22 26 38 6 58 2 62 34 30 18 46 50 14
5 59 27 37 11 53 21 43 13 51 19 45 3 61 29 35 1 63 33 31 17 47 49 15 9 55 23 41 25 39 7 57

Due to formatting issues, the tree is presented left to right. However, this is enough for our needs as we are only worried about whether each tree node is there. If we look through this tree, every value from the range 0 to 64 is present. Anything more than 64 is not reachable only because we only started with 64 pennies, it's not possible to just create more pennies. If you know how, let me know.

Using the hint given on the problem handout, working backwards, we can see the cause of this. This is due to every number being able to be represented in binary or with multiple additions of 2^n, n \in N.

Take for example the number 13:

13 = 2^3 + 2^2 + 2^0 = 8 + 4 + 1 = 13

Conclusion

In conclusion, since we are relying on if a number can be represented in binary, it can be concluded that ANY number can be created when dividing piles with an even number. The only time this is not possible would be when the starting piles are both odd and no operations can be carried out.

It was a pleasure to write these blogs and learn under Professor Heap and TA Lala. I learned a lot and this knowledge will defiantly come into use in my future classes and career. Let's hope second year's professors and classes are as enjoyable as this one. :)

Piles of Pennies

Continuing on from proving or disproving whether functions are upper or lower bounded by other functions, the lectures from the past week have been adding on to such proofs by the introduction of additional implications. Now statements such as those claiming that a function upper bounded by another function implies that a function squared is also upper bounded by the other function squared.

This concept brought back many previously used techniques both from CSC165 and Calculus in order to proceed with proving or disproving the statements. Overall, due to not being completely new material, my understanding of this material is not too bad. It is very similar to proofs done in the past where there are some steps acting as hurdles but everything works, as said by Professor Heap, after one special step due to the inward falling domino structure of the proofs. Assignment #3 should provide sufficient practice on the concept of proofs relating to bounds.

I have also been working on the Penny Pile problem brought up during a lecture. As of now I have not been able to formulate a solution which can easily determine whether a certain result is possible however I have put together a simple Python program to run tests to determine whether a result is possible. The algorithm used may contain some errors at this point, but they will be ironed out as progress on this problem continues.

First of all, let's go over the algorithm I had in mind when constructing this program. Writing down your ideas is always a good way to find mistakes.

1. While the goal has not been reached:
1. Check if either the left or right pile are even numbers. If not, break simulation.
2. If the goal can be reached by moving half of the left pile to the right pile, do so.
3. Else if the goal can be reached by moving half of the right pile to the left pile, do so.
4. Else if the left pile is even, move half of it to the right pile.
5. Else if the right pile is even, move half of it to the left pile.

In the coming week, this algorithm will be tested slowly using smaller sets and comparing its results to ones found by hand. The above algorithm translated into Python, in a very rough stage, is the following:



def penny_piles(goal, left=64, right=0):

    n = 0

    failed = False

    print('Left: ' + str(left) + " Right: " + str(right))

    while not(left == goal or right == goal):

        time.sleep(1)                    

        if not(left % 2 == 0 or right % 2 == 0):

            print("Failed.")

            failed = True

            break

        print('Left: ' + str(left) + " Right: " + str(right))

        if right + left // 2 == goal or left // 2 == goal:            

            left = left // 2

            right += left

            print('Adding ' + str(left) + ' to right pile.')

        elif left + right // 2 == goal or right // 2 == goal:            

            right = right // 2

            left += right

            print('Adding ' + str(right) + ' to left pile.')

        elif left % 2 == 0:

            left = left // 2

            right += left

            print('Adding ' + str(left) + ' to right pile.')

        elif right % 2 == 0:

            right = right // 2

            left += right

            print('Adding ' + str(right) + ' to left pile.')

        n += 1

    print('Left: ' + str(left) + " Right: " + str(right))

    if not failed:

        print('Goal reached after ' + str(n) + ' swaps.')

This is a very interesting problem, looking forward to working through, and hopefully solving, it.

So, the marks are here...

The results for both the second assignment and test have been uploaded to CDF. I was very happy with the test result but not so much for the assignment. The assignment was very fair and not too hard but bad time management led to this result. I was not expecting to run into some troubles with LaTeX so I left typing up and finalizing to the last few hours. I should really be more careful and plan ahead when it comes to these kind of technical details.

The main focus in CSC165 has been on algorithm analysis and proving if an equation is within the lower or upper bounds of another. I was quite confused at first but the tutorial has helped to improve my understanding. I still get stuck at times when trying to reintroduce negative terms but I am confident that this can be resolved by going over the annotated slides a couple more times. I wish that the annotated slides for the previous week were available before the test but it is no big deal. The course notes helped to combat this issue.

I have been working on the penny piles problem and am able to determine whether a certain combination is possible regardless of the number of pennies through the use of a simple python program. However, no real pattern has been found as of yet.

Prove or Disprove: Test #2 went well.

I have always enjoyed reading through and working on proofs but have never been very good at them. It is always interesting to see the why behind every what. Simply knowing what is true or false is not good enough for me, I like to know why.

For this reason, I have been enjoying the lectures even more because we are working on the topic of proofs. There have been struggles along the way but after some time spent practicing and reading over past proofs, general strategies have been developed. While these strategies are not algorithms that will work with all proofs, they are similar to the proof structure as in they make up the bulk of the proof and leave you with blanks to fill in.

Many of these strategies are common sense or obvious but having actually thought and making them precise, they make the proof process much more straight forward. One strategy that originated from working on the second assignment is as follows: When possible, always refer back to the definitions relevant to your problem. This is a basic strategy that almost anyone will know to do but having it written down and thought out ensures that it is kept in mind. Writing it down acts similarly to a cheat sheet, it is there when you need it but you do not tend to use it during the test. The cheat sheet does not directly aid individuals but it is the process of creating one that does.

I'm happy to see that a cheat sheet is allowed for the second test. As mentioned in a previous blog post, the cheat sheet for the first test was not used during the test but it still helped to create one. For this reason I will be sure to have one ready for this week's upcoming test. I will include items relevant to the strategies mentioned above meaning items such as definitions, rules, and maybe, however unlikely, past proofs that may prove to be useful.

After the test we'll be able to prove, by example, if the test went well or not.

Prove or Disprove

The second assignment's deadline is creeping up. This assignment is full of proofs which are my weakest point in this course so far. Fortunately Professor Heap spent additional time to slowly go over more proofs which greatly helped to increase my understanding on how to approach proofs.

As far as structuring the proofs goes, I have it nailed down. It is mostly a mechanical process as when you figure out which statement or assumption is associated with each symbol in the statement, it is easy to come up with the structure. The assignment handout does claim to give out substantial marks even if you only provide the proof structures meaning that even if the proofs are not completely correct, it will not be for naught. However, if the incorrect stance is chosen (true or false), no marks will be provided.

The main problem I am having with proofs is actually putting your thoughts down into non-ambiguous statements. In my head I am able to tell if the statement is true or false and even come up with examples as to why. However, I am unable to properly put my thoughts down on paper. Improving on a concept such as proofs takes time and commitment. Therefore, I am hoping by the end of this assignment I have a fair grasp on projecting my thoughts into a written format. Besides, that is the point of this course.

Results are in!

Both the assignment and test have been marked and returned. Fortunately I was pleased with the grades of both. They were both marked fairly and all questions were relevant to the given material, no surprises, which was nice. A cheat sheet was allowed, and I prepared one, for the test but did not need to use it at all. The greatest part of the being allowed a cheat sheet is the process to preparing one. When writing out the cheat sheet, by hand, you are forced to sit down and figure out what is important. After writing it all done in a precise and neat manner, the information just stays in your head. The cheat sheet functions as more of a tool to learn than one to aid yourself during the test.

Last week I blogged about difficulties when it comes to proofs. Fortunately this is becoming more and more clear due to continuous examples both in the lectures and tutorials. The tutorial exercises are a great way to increase your understanding and improve your speed on lecture material. Definitely something that should not be forgotten.

After working on more proof problems, reading through course notes, online websites, and aid provided during the tutorial, proofs are not so foreign anymore. The proof structure has been described in a great manner by Professor Heap: Like dominoes falling inwards. Simply complete one step from both sides and you are eventually left with some blanks to fill in. Unfortunately there is no one set plan to get past this final hurdle but a lot of the work has been done and the groundwork has been lain if the proof structure is applied. I will continue to practice proving more statements in hope of improving my speed to fill in the blanks.

There was one slight problem with my test where the answer that I had crossed out was marked instead of the one I meant to be marked. Due to limited time, I was not able to erase my incorrect answer and simply created a new box and wrote the correct answer in that area. After doing so, the old answer was crossed out. The line may have been too faint which led to a TA marking my old answer. Immediately after spotting this error, I took some pictures as proof (best I could do) and emailed the Professor as soon as possible. Hopefully after taking a look at the test, Professor Heap is able to resolve this issue. If not, I'd better get used to crossing out answers in a more obvious fashion.

Tests off the horizon... for now.

The past week has been focused on preparing for the term test not only for CSC165 but for other classes as well. Fortunately, and the reason why I love computer science, the material is not something that must be memorized. You simply need to understand it to a point where it can be applied to any type of problem. You are not simply regurgitating information but applying what you have been taught to new problems.

The main issue with the test was simply the worry about remembering the manipulation rules. They are very similar to other properties in math so the rules were not entirely new. A cheat sheet was allowed and with the help of the summarized rules in the course notes, I wrote down all the manipulation rules on one sheet of paper organized under names of the rules.

The benefit of preparing a cheat sheet is not to have the chance to look over or spend time looking over the written material during the test. Instead, at least for me, it serves as a method to remember information. Throughout the course all lecture notes are provided so writing down notes is not necessary along with being difficult while trying to listen. However, when I write something down I tend to never forget it. Everyone has their ways to memorize material, for me that is writing it down.

Lectures throughout the past week have been covering the methods of proving statements and implications. Proofs have always been the weak point and most difficult portion of any math related course. The tutorial handout is posted and contains proof related problems. I will try my best to work through this handout and with the help provided during the tutorial, both my peers and the TA, the material should begin to seem less foreign.

The main problem with proofs is figuring out where to begin. After the first step, proofs usually move along like dominoes.  I am hoping to find tips, tricks, and suggestions when going over solutions during the TA. Examples and observing how others go through proofs is the most beneficial method to learn proofs.

At least it looks nice...

The past week has been focused around both understanding and completing Assignment #1. The questions on this assignment were short but took a lot of thinking because of the need to be very precise. After consulting the textbook and spending time going through possible answers, the most correct answers were selected and submitted to be marked.

It seems like other students, myself included, tend to not enjoy inserting mathematical symbols through the use of Microsoft Word. In order to combat this issue, save time and frustration in the long run, and the opportunity to learn something new, I took the initiative to learn a new programming language; LaTeX.

This programming language or more correctly document markup language allows programmers to customize and manually create their own documents. Normally, Microsoft Word does all the code portions for the user. In LaTeX, one must specifically input everything to be done ranging from document type and size to line breaks. It might seem like a lot more work to have to do everything manually but those that are efficient with the keyboard can type out the symbol syntax quicker than going through the tedious process that is the insert menu.

For example: $\forall x \in Q$ would lead to replace the \forall and \in to the corresponding symbols.

The language itself is not very difficult to get the hang out, only at the beginning does it seem counter intuitive. LaTeX makes your PDF documents look very nice and professional, definitely going to be used to create my future resume. So it might be wrong, but hey, at least it looks nice!

For those interested in learn LaTeX, the following cheat sheet has proven to be very useful: LaTeX Cheat Sheet

Assignment Deadline Creeping Up

Thankfully the material introduced throughout this weak was clear. All confusions present in the material were resolved by the end of each lecture. However, this cannot be said about Friday's lecture due to my absence. Hopefully the annotated slides are posted within a few days allowing me to catch up on lecture materials. As always, the course notes are a great resource so if the annotated slides are missing, it will be no big deal.

The main focus during this week was put on Assignment #1. The questions were foggy at first but after covering new material this week, they do not seem to be too bad. Still, one should never underestimate material that is to be marked. You can never know how you will do until you get it back.

My aim, after learning from the first semester, is to finish every assignment one day before it is due. This way, a lot of stress can be avoided and mistakes are less likely to be submitted. Therefore, I have rationed my days to allow for completion of the assignment by Tuesday. A low mark at the beginning of the course can be discouraging so I will try my best to ace this assignment. Besides, the material will only get harder; might as well build a base.

I have been looking at blogs posted by other students and have noticed that my thoughts tend to be very long winded and verbose. I should probably cut down on the length to save the TAs time as it is not only my blog which will be read.

The Week of the First Quiz

The second week of CSC165 flew by. This is the point where shoppers tend to drop courses and open up space for those genuinely interested in the course. It is also the week in which the first graded material is given out; the quiz along with an assignment.

The concept of universal and existential quantifiers was easily understood but the idea of expressing these statements using functions and list statements in Python was confusing at first. Luckily, Python syntax tends to relate to English very closely so very often simply reading the lines of code will explain what it does. The only problem with these functions is knowing which set goes where. Do we check for S1 in S2 or S2 in S1? In order to improve my understanding, I will start to use these statements more often and even force myself at times just to get used to the syntax. Being able to quickly recognize what the code does instead of having to go over it one piece at a time is very valuable when writing time constricted pieces such as the exam.

When it came to stating quantifiers as claims about sets, I was confused at first but going over the examples together proved to be very useful. After working on all four examples together, this concept is now clear. Hopefully the teaching method of going over examples together as a class continues to be used. Simply learning theory and not going over examples can lead to very confused students.

The tutorial this week was what I was looking forward to. I was interested in seeing how it is carried out and if it will be worth sticking around instead of simply writing the quiz. The tutorial problems are done in groups while the TA walks around to aid confused students. This tutorial went really well and ended with a very easy quiz. This quiz was closely related to the tutorial problems so it seems like if you work on these problems beforehand and clear up any confusion during the work time, the quizzes should all continue to be easy. At least that is my hope.

So far the class has been going very well but my only issue is the randomness of the availability of annotated slides. The lectures are very well done and seem more beneficial to listen to than potentially miss verbal information due to focus being put on taking notes. If the annotated slides were available for all lectures, there would never be the worry to quickly jot down notes and answers to the examples and would also help for missed lectures. However, this issue is not very serious as course notes are already available in a very well written format. 

Another main event in the second week of CSC165 was assignment #1. At this point all of the questions are not very clear to me but this will hopefully change at the end of week 3. One reason for some questions seeming unclear is due to my absence during the Wednesday lecture due to medical reasons. As mentioned above, course notes are provided which should quickly allow for clarification on all unclear portions of this assignment. The tutorial is also coming up so any concerns may also be addressed at that point because of the assigned tutorial problems. Unfortunately, I have not been able to review all material covered in week 2 due to catch up required in other classes but I am aiming to be on schedule by the end of next week. 

Being my first blog, I am worried about the quality of posts and am looking forward to comments providing feedback.

First week: Check.

The first week back from the winter break quickly flew by. I had luckily kept my sleep schedule intact over the break so drowsiness was not an issue. However, it was tough at first to be actually doing work and commuting instead of just lying around and playing Dota 2. But enough of that, let's move on to what is important; CSC165.

I have always been fond of all computer science courses and CSC165 or Mathematical Expression and Reasoning for Computer Scientists was no exception. Prior to coming to class, I had been informed by friends that the course can be difficult to wrap your head around at first, which is true for all math related courses. Everything just clicks and seems easy after lots of work is put in, or like for most people, after you are done with the material. With this in mind, keeping up with material and practice exercises will be essential to doing well.

After the very boring and repetitive but necessary introduction to the course was out of the way, the course material covered quickly gained my interest. Being able to understand and solve problems is very important but the ability to document and express your process and results is equally so. In the first week only the very basics have been covered. Coupled with D. Heap's personality, this has resulted in a very relaxing and entertaining couple of lectures.

It wasn't the first week's lecture material that gained my interest but was due to the course notes. On the bus ride home, I decided to read through the course notes and managed to read ahead of what was covered so far (this was after the second lecture). Section 1.4 in the notes, linked above, shared some very interesting and fun problems. The statement claiming that one should be able to solve these problems after completion of this course has given me something to look forward to.

It probably was not necessary to blog or SLOG about the first week's classes but being my first blog, I decided to test out the system beforehand. The blog title could use some work and is tentative at this point.

Hello World!

Hello World.