Bitter, Sweet Moments of CSC165

Hello everyone! As we all know finals are coming up and we are at the end of CSC165. I must say there were many bitter sweet moments of this course. This course has challenged me more than anything I have ever faced so far. It is a tough course with many trials and tribulations that allowed me to explore the world of weird logic. A part of me will miss it but a part of me will be set free before the exam is over, provided that I do not die during the examination of course. I have faced some disappointments and some successes with both assignments and midterm tests. Guess what! You will never learn once you do not have some failures. I enjoyed the problem solving work sheets Professor Heap used to give us. I thought he was a good lecturer in my opinion as well as my TA, Madina. Some of the simplest scenarios can have some of the most “complex” algorithms to create. Who knew folding paper and counting pennies can have algorithms? That is the beauty of Computer Science; you never know what problem you are going to be presented with next. Last but not least, we have the almighty proofs. That was the most frustrating topic that I have ever done. Actually solving the proof was probably the best part.

Good luck for the rest of the year! Thank you for reading my blog!

                               

The CSC165 is almost over expression

Halting Struggles

Today, we are going to discuss the topics of halting and computability. This topic in particular has my mind wrapped up in spirals of confusion but I will still try to decode its meaning. From what I have read in the slides, we have to be able to look at a code, decipher an algorithm to decide if it halts without actually running. There are two possible things that can occur with the code, it can either halt or do not halt. A simple solution most people would rely on is to run the code to check if it halts or not. Unfortunately for us, it is not as simple as that. This particular topic has so many mysteries that are need to be solved that even expert programmers have been baffled in trying to prove if a code will halt at every input or loop infinitely. It shows that it is almost impossible for all problems to be solved with algorithmic developments (not computable).Wow! I think that I am having a speechless moment right now. How wonderful! The almighty computer cannot solve all our problems, I concur that we are doomed!

This is the collatz code that was presented to us in the lecture slides. The problem here is that it quite difficult to prove that this code would not loop forever. How this code works is that it stops at every natural number. The question is how far would it go? If only I knew the answer, then world would be at peace.

def collatz(n) :

      while n > 1 :

            if n % 2 == 0:

                   n = n / 2

           else:

                  n = 3*n + 1

return "Reached 1…”

Secondly, I do not get how infinity does not equal infinity? I always knew math was strange.

If we could only halt like Keanu Reeves, then problem solved !

                           

Linear Searching

In this slog we shall talk about counting steps and worst case scenarios for Big-Oh. This is the topic in which we have to actually understand how each line in python works. This particular topic was quite difficult for me to understand in the lectures. I had trouble grasping the concept of which lines have to be executed one after the next. However, Madina, my TA, made it a bit easier for me to understand this particular topic.

We were presented with this question for the quiz.

This was the code given to us for sum_up

   

def sum_up (n): 

    i = 0

    s = 0

    while i < n:

        j = i

        while j>= 0:

            s = s + 1

            j = j - 1

        i = i + 1

    return s

At first I had no idea really how to start with this question. However, I tried to remember the steps Madina showed us in how to read and understand each line. The first question was, what do sum_up(0), sum_up(1) and sum_up(2) return?

For sum_up (0), it returns 0

For sum_up (1), it returns 1

For sum_up (2), it returns 3

The general expression for what sum_up (n) returns is (n (n+1))/2

We were required to write steps to explain our thinking.

The outer while loop iterates i < n for the values i = 0 …..n = n-1 and the inner while loop iterates for values j = i ……0. Thereby, s would keep going through the sums on each of the iterations once it is satisfied.

Therefore n-1

                   Σ     (i  + 1) = (n(n + 1))/2

               i < n
I have also browsed through many different slogs in which I though all of them were so unique filled with so many great ideas, creativity and interpretations in problem solving for this course. However, I found one that stood out impeccably for me. Take a look!

http://www.soohamrafizslog165.blogspot.ca/

Week Nine Stresses

Welcome fellow CSC165 bloggers or sloggers! Week nine was crazy, assignment 2 was due and then a term test 2 the next day. This is university life; I have to keep reminding myself. Assignment 2 was quite a struggle I must say. Luckily we have fellow group members to share these struggles. The assignment that we were given was to prove or disprove proofs. Some of them were quite obvious to determine whether they were true or false.  I believe it was question 1.2 that took days to solve. My group members and I felt as if all hope was lost, that we were slowly dying inside. Giving up was a plan but that “function”was never executed, thankfully.

Proving a statement I realize, takes absolute dedication. It is something that takes a lot of practice and patience. Each of us in our group gave our own ideas and ways how to tackle and solve the proof. Once we submitted assignment 2, it was like a breath of relief (exhales). However, the stress did not stop there, midterm test time the next day. On the bright side, after doing all those proofs for assignment 2, we would have had proofs literally stuck in our heads. I was confident that I understood most of proving statements until the exam “proved” me wrong. However, I was pretty sure I did better in this test than the first one, I hope. Good luck to everyone and have a great week!

Penny Piles Problem

The daily lives for computer scientists are to create solutions to problems. The name of our problem that we were presented in class was called “Penny Piles”. My understanding of the problem is that the left draw contains 64 pennies and the right draw contains 0 pennies. Thereby, the goal was to arrive at 48 pennies in one draw. However, there were two rules in which we were given and they included:

        

          a) If the left draw has an even number of pennies, half of them can be transferred to the right draw. If     the left draw ends up with an odd number of pennies then operation l is disallowed.

b)   If the right draw has an even number of pennies, half of them can be transferred to the left draw.If      the right draw ends up with an odd number of pennies then operation r is disallowed.

I worked with one of my friends to tackle this problem since we were suggested to do so.  We started with the 64 pennies in the right draw and 0 in the left. We divided 64 by 2 since it was even and got 32 pennies to transfer to the left draw. This resulted in both draws having 32 pennies. We divided 32 by 2 once again and transferred the 16 pennies into the right draw. This resulted in 48 pennies in the right draw and 16 in the left. We repeated this method until we arrived at odd numbers of pennies in both draws, 63 in the right and 1 in the left draw. Even though we arrived at the desired 48 pennies in one draw at the beginning, the problem was not totally solved.

We tried different numbers in the range [0,64] in which all of them seemed to work. We tried the different numbers on both sides and we concluded that it did not matter which side we started from the left or the right because we arrived at the same answer. If you notice the algorithm, l(left draw) + r(right draw) = 64(total number of pennies)

Comment on how your solutions were like! Have a great week!

Introduction to Proof Structure

Welcome to the world of proofs! This week, we were introduced to the structure of how to compose a proof. We are given a statement and required to write a specific step by step structure that demonstrates how we are supposed to carry about writing the proof itself. Comments were also required to show that you have understanding of the claims that you are making in the proof.

Below, I will demonstrate with an example on how a proof structure is to be written for this course with a few additional comments.

             

(for all)x E R, (for all)y E R, x<y => (there exists)z E R, x<z and z<y

Assume x E R, y E R   # this is the domain assumption (can only be made for universal quantifiers)

     

   Assume x < y # antecedent

      

      Let z’ …… # since the value of z has not been determined yet, it is z prime.

                       # this assumption depends on the values of x and y.

     [proof of z’ E R]

   

     Then z’ E R # this is written once this statement is actually proven

   

     [proof of x<z’ and z’ < y]

    

     Then x < z’ and z’ < y

   

     Then (there exists) z E R, x < z and z< y # introduce (there exists symbol)

     Then x < y => ex z’ E R # intro =>(implication)

Then (for all)x E R, (for all)y E R, x < y => (there exists)z E R, x<z and z<y #intro (for all)

Midterm Examination Day

We had our first midterm test for this course and my first midterm test overall in my university career so far. I could not have been more nervous because it felt as if it was a matter of life or death at that point. I literally saw the tension and pure anticipation pasted on everyone`s faces while awaiting entry into the examination room. The examination room itself was intimidating due to the vastness of the room. What caught my eye was seeing the “infinite” rows of desks placed so neatly that it seemed as if it was not even an inch out of place. Now for sure I accepted the fact that I am not in high school anymore.

Having the midterm test placed in front of me waiting to be opened, was the most anticipating feeling because everyone wants to know if the material inside would make us or break us. Once I opened the booklet, the structure of the test was almost identical to the sample test we were given before the midterm. I was happy at first and then realized that I should have just written the sample test as my cheat sheet. As I was going through the first question, I definitely had an idea how to tackle the question since I studied the sample test.

Unfortunately for me, I had moments of self-doubt and changed my answers in which I believe was the biggest mistake I made. From assignment 1, I had learnt a lot but I allowed my nerves to get the best of me after a long time of writing examinations. However, I have learnt from this experience by understanding that there will be moments of self-doubt in examinations sometimes, but learn to have confidence in the materials you have studied. Yes, I am disappointed in myself, however, I know that there will be other opportunities in this course in which I can make up for my lost marks.

Share your exam experience and comment below!