The Greatest Common Denominator

As part of a problem-solving episode, I want to rehash an interesting topic discussed in Week #6, the greatest common divisor. To quote from the handout, the GCD of two non-negative integers is a non-negative integer that:

1. Divides both numbers
2. Is the largest non-negative number that does so.

Euclid famously discovered an efficient way of finding the GCD of two non-negative integers. Let m and n be the two numbers. It follows from this that:

1. If m is zero, then the GCD is n.
2. Otherwise, replace m with the remainder of n divided by m; replace n with m. Return to step 1.

Sounds a little confusing. The goal of this post is to make sense of this algorithm, and subsequently devise a code in Dr. Racket that carries out this algorithm for any two non-negative integers. Let's do it!

Understanding the Problem

In order to devise a code that calculates the GCD, we have to intuitively understand what the GCD is. Let's start off simple. Take 4 and 6 and feed them through Euclid's algorithm.

1. 4 does not equal 0. Condition is false.
2. 6 divided by 4 is 1 with a remander of 2. Thus, 4 and 6 becomes 2 and 4. Return to Step 1.

1. 2 does not equal 0. Condition is false.
2. 4 divided by 2 is 2 with no remainder. Thus, 2 and 4 becomes 0 and 2. Return to Step 1.

1. The first integer is 0. Condition is satisfied. Thus, the GCD is 2.

Even without carrying out the math, it makes sense because 2 is the largest number that divides both 4 and 6. We now understand that a working Dr. Racket code must take 2 numbers and find the largest number that divides both of them.

From this, we come up with the contract statement.

; GCD : number number -> number

; Take 2 non-negative integers and find the largest common divisor

Devising a Plan

We will attempt to develop the code step by step.

First, we will write two check-expects, then define GCD according to Euclid's algorithm, and finally test it out using some numbers.

Carrying out the Plan

Let's write two check-expects, the first one being 4 and 6 that we have just calculated.

(check-expect (GCD 4 6) 2)

(check-expect (GCD 12 16) 4)

We now move on to define GCD, which is the tricky part. But recognizing that Euclid's algorithm has 2 conditions, we can expect the definition to use cond.

(define (GCD m n)

(cond

  [ ... ]

  [ ... ]))

The first condition is fairly simple. if m = 0, then (GCD m n) = n. We have,

(cond

  [(equal? m 0) n]

  [ ... ])

The second condition is harder to dissect. But recognizing that it sends you back to Step 1, we realize this is a recursive example. Simply put, the definition of the function will encompass the function itself, similar to the palindrome function we learned in class. 

(cond

  [(equal? m 0) n]

  [else

    (GCD (remainder n m) m)])

Note that m has been replaced by (remainder n m), which is the remainder of n divided by m. Also, n has been replaced by m. This is all according to Euclid's algorithm.

Putting it all together, we have:

; GCD : number number -> number

; Take 2 non-negative integers and find the largest common divisor

(check-expect (GCD 4 6) 2)

(check-expect (GCD 12 16) 4)

(define (GCD m n)

(cond

  [(equal? m 0) n]

  [else

   (GCD (remainder n m) m)]))

Run it in Dr. Racket, you get Both tests passed!

Looking Back

The function GCD already passes the two check-expects, but we can further test it with some other numbers.

(GCD 175 600)

(GCD 138 234943)

Dr. Racket produces 25 and 1, respectively, which happen to be the correct answers. We have now successfully devised a working code for Euclid's GCD algorithm. Mission accomplished!

Learning from Test 2

Admittedly, I was overconfident walking into the 2nd midterm. I hadn't studied much, fixed under the false impression that a majority of class material is common sense.

It's not.

You need to put in a fair amount of work to ensure a complete understanding of the course curriculum. I didn't, and as a result I received pretty suboptimal results that I wasn't happy with. It's a great lesson though. I'm definitely going to study harder (and more importantly, earlier) and carry a more humble attitude walking into the Exam Center.

Good luck everybody on the final exam!

Wikipedia assignment completed

It took a great deal of willpower but I managed to finish the third part of the Wikipedia assignment several days before it's due.The only problem I encountered was with images. I had hoped to add an image to enhance the page I was editing, but doing so required a minimum of 10 previous contributions. So I guess I didn't have the pedigree :(

But I do feel fantastic, not only because I conquered procrastination but also on the pure notion of having contributed to the world's largest encyclopedia and improve its quality of information.

Preparing for Midterm #2

Admittedly, I started studying for this test a bit later than I would have liked. Nevertheless, better late than never!

My study sessions have 3 basic components to them:
1. Review the lecture notes on algorithm, hardware, operating system, and networks.
2. Reacquaint myself with all the Dr. Racket programming taught in the past few lectures.
3. Inspect the past term test provided on the course website.

Most of my time is dedicated toward #1: reviewing all the basic computing theory. At times, I find concepts difficult to grasp because of the lack of empirical evidence. For example, it's harder to appreciate the numbering and sequencing of operations back in the early ages (due a lack of multi-tasking provided by operating systems) because you didn't live during that time period.

The different configurations of computer networks also prove quite challenging to understand. I know the three basic types are ring, star, and bus. There also happens to be other names for them, for example Ethernet refers to bus topology. What I'm struggling with is intuitively understanding the strengths and weaknesses of each set-up. This is pretty much all I know:

Ring - if one machine fails, messages may not be transferred to its recipient because it goes around the "ring".
Star - if the main machine (hub) fails, then messages cannot be transferred at all.
Bus- one machine failing is generally inconsequential, however, if too many messages are being sent at once, then they will clash and get sent back.

I'm sure I'm missing some details, but that's all I understand at this point.

The HTML stuff is also quite confusing, the way I see it: it's simply a source code that a browser deciphers and then displays to its user.

There's a lot of stuff to be figured out, I guess I'll come to Dr. Heap's office hours right before the test.

My enduring battle with assignment 1

Assignment 1 has been a great challenge for me. Upon opening the initial clock.rkt, I had very little idea of what to do. In fact, it took me several moments to figure out what the program was even supposed to accomplish. Safe to say I felt an insurmountable task ahead to me.

I began chipping away little by little. I made the easy corrections first and in doing so, I gained a better understanding of the program and also the confidence to rectify this cacophony of words, symbols, and functions.

I started tackling the more difficult check-expects and definitions. My corrections were mostly futile as the program still encountered many errors. But the more you work at something, the clearer it becomes.

My friend was also willing to give me hints here and there, I'm really grateful for that.

My T.A. Omar was also tremendously helpful in helping me figure out clarify-image.

I worked away at it some more. I could finally get the program to run but it passed only a few of the check-expects. This frustrated me and gave me the urge to throw things across the room. I didn't though :)

Finally, I went to office hours for more help. With the help of T.A. Khaled, I realized what I was doing wrong. A common mistake I made was trying to force c into the check-expect by using a number, when in fact I had to create a color myself using the appropriate function. Same with clocktime, I kept on trying to input a number when the program expected a clocktime in the format of hours minutes seconds stop/go.

When you understand the meaning behind the code (that is, what a specific line is supposed to accomplish), it becomes a lot easier to fix it. In the beginning, I was trying to fix the program without an actual understanding of the program itself. We all know how that turned out. But as soon as I tried to see the program for its purpose rather than its mistakes, I gained the clarity and understanding I needed to perfect the lovely clock. I also couldn't have done it without my friend and my T.A.s, you guys are great.

Consider this a battle won! Wikipedia, you are next.

Struggling with Course Material

I'm going to be completely honest here, the past week I've had to deal with a string of midterms and essays. To accomodate this busy schedule, I spent less time reviewing this course's materials and doing the tutorial exercises.

At the same time I realize it's my responsibility to stay on top of my work. I would like to succeed in this course, and this is my plan to catch up:

1. Review past lecture slides and clarify any confusions with my T.A. and the prof.
2. Do the tutorial exercises and get a better understanding of Dr. Racket programming.
3. Get started on Project #1 and the Wikipedia assignment.

Time to get to work! :)

Fun with Big Bang

In last week's lecture we continued our development of the barracuda clock, adding more functions to the big bang model. It's fascinating seeing all the concepts we've learned over the weeks slowly coming together as we try to develop very basic working programs.

As I worked through the Picturing Program exercises, I was intrigued by other ways in which you can use the Big Bang model. For example, suppose you want to create a square that starts at width length 10 and gets larger by the second.

; square-of-width : number (width) -> image

(check-expect (square-of-width 7)
                       (square 7 "solid" "red"))

(define square-of-width (square n "solid" "red"))

(big bang 15
       (check-with number?)
       (on-draw square-of-width 100 100)
       (on-tick add1 1))

This program creates a red square with side width 15 on a 100 by 100 window, and the square gets larger by the second!

I realize Dr. Racket is much more versatile than I originally thought. When you're willing to explore, the possibilities are endless. I'll be taking more time this week to play around with big bang.