year++

The B.S. in Computer Science progress matrix:
--------.-Summer---Fall---Winter--Spring--.
Year 1: | [ q01 ] [ q02 ] [ q03 ] [ q04 ] |
Year 2: | [ q05 ] [ q06 ] [ q07 ] [ q08 ] |
Year 3: | [ q09 ] [ q10 ] [ Now ] [ -?- ] |
Year 4: | [ -?- ] [ -?- ] [ -?- ] [ -?- ] |
--------'---------------------------------'


63779 247478627

^- It says "Merry Christmas" in T9 text code.

This is what I'm working on now:

 .-----.-----.-----. 
 |  1  |  2  |  3  | 
 |     | ABC | DEF | 
 +-----+-----+-----+ 
 |  4  |  5  |  6  | 
 | GHI | JKL | MNO | 
 +-----+-----+-----+ 
 |  7  |  8  |  9  | 
 | PQRS| TUV |WXYZ | 
 '-----'-----'-----' 


The next 303 assignment from last quarter: converting numbers into words just like how they would if you entered them into a cellphone (unless of course, you happened to have an iPhone, which has it's own m4d sk1||z text prediction algorithm). Pretty much finished off all the extra credit options for the last assignment today.

This T9 text thing is really fun. The trick is how to make it "adaptive" (one of the extra credit options).

Cabin Fever?

Above Uwajimaya

Right. This super snow is ruining my research at CSE. UW is closed again tomorrow, and the day after is XMas eve. Not fun. Seattle was so unprepared it was unbelievable.

So rather then let such lulz take over, I spent my time reading the C Reference Manual and the Linux Pocket Guide at Chinatown (was stuck there for 5 days or so). That was productive. Right now I'm *almost* done with the C Reference Manual, and about 33% more to go with the Linux Pocket Guide. Very useful stuff.

In other news I also finished the first CSE 303 C assignment from last quarter. It wasn't particularly hard but I took great care to adopt good style and use of preprocessor macros / etc. It's probably been about 8-9 years since I wrote my first C program. And on top of that it was in 2003 that I last wrote a C program (a log file parser). So it's been a while. I've used a lot of programming languages, and I must say, C is still the best for writing fast programs close to the processor.

There's going to be more snow tonight, so I'll probably go finish off the extra credit options for that assignment tomorrow (50% done, only the easy ones left). I'm doing the C assignments from last quarter so I get a feel for C once again. With any luck I'll be able to start work on the T9 cell phone "numbers to words" C program tomorrow. That one is fun and useful.

lol check this out

Snapped this on the way to Elsha & Michelle's place. Apparently those
two coaches got a bit too lulzy and almost ended up on northbound I-5.
Posting this via iPhone too.

Snow, has, a YOU.

Hmm. Stayed over for 2 nights at the "Sky City" in Chinatown. Cool stuff.

In other news, I'm almost 200 pages into the C reference manual and very much impressed. Never have I seen a programming language that allows you to control so much. Ironically C was the language I began programming with many many years ago. But over time this was diluted as I shifted primarily to various scripting languages and C#, which then was culminated with my formal training in Java (Yay for CSE 142 and 143).

If you're looking for a good book in C, well, this is it. I've read 2 books on C before but they never delved into the language in as much detail as this book does. Surprisingly though, this "reference manual" is incredibly easy to read and the explanations makes a ton of sense.

Some of the discussions in the book require some knowledge of the underlying hardware (CSE 370 -> two's complement!) to understand but its great that it goes into that much detail. A programmer must at least have an abstract understanding of what his code is doing at the hardware level. C is by far *the* programming language that lets you take control of the underlying memory itself (well, except for Assembly of course, but thats a different story).

Quite a bit more to cover in the book before I get down to writing some code. Amazing stuff. I've already come up with 5 or so ways to read a file and search for stuff within it, along with the various trade-off considerations. Can't believe how much I was missing in Java. You can do some pretty crazy stuff in C that isn't even imaginable with Java (not to mention way more efficient/fast).

The Sky City

Well, otherwise known as Elsha & Michelle's new apartment above Uwajimaya in Chinatown. It's within walking distance of all the major restaurants like Jade Garden and what not. What makes this apartment stand out is that its a gated community isolated from everything else below. The interior of their apartment is really cozy too.

With any luck IKEA will happen tomorrow. The weather here just took a turn for the lulz, with a massive snowstorm in the works tonight as you can see:

On top of that its already 32ºF right now and tonight will see a drop to the high 20s lasting through tomorrow. This means that all the stuff on the roads are turning to this thing called ice, which isn't going to go away at all tomorrow because temperatures will stay below freezing.

Unless, of course, WSDOT manages to defrost the roads somehow.

The Beauty of C

I've been messing around in C trying to figure out an efficient way to reverse strings and so far I've got this (along with a few other recursive versions that are not as efficient):

// In place reversal (Call by Reference)
// PreCondition: [str] is a pointer to a null-terminated string
// PostCondition: The contents of the string pointed to by [str] have been reversed.
void inPlaceReversal(char* str) {
    char* begin_index           = str;
    char* null_terminator_index = begin_index + strlen(str);
    char* end_index             = null_terminator_index - 1;

    // Perform an inward moving swap of the contents of the begin and end indices
    while (begin_index < end_index) {
        *null_terminator_index  = *begin_index; // Use the null-index as a cache
        *begin_index            = *end_index;
        *end_index              = *null_terminator_index;
        
        begin_index++;  // Move left pointer inward.
        end_index--;    // Move right pointer inward.
    }
    *null_terminator_index = '\0'; // After it's use as a cache, reset it to null.
}

Pointer arithmetic is ridiculously powerful. Here I am swapping the string right in its memory position, using the memory location for the null termination as a cache to perform the swap. I'm not consuming any extra memory to perform the entire reversal operation, with the exception of the 3 pointers to the beginning, ending, and null-termination locations of the string.

No wonder C is sometimes referred to as "High Level Assembly".

CSE321 Final (Fall 2008)

strcpy(cse321, "Epic Fail.");

Right. At least I'm totally done with this class now. They should have called it "Voodoo" instead of "Discrete Mathematics". Rather than rant about the class, consider this scenario instead:

You want to use this simplification in your production code:

Hihi(n+1) = SumFrom(i=2)to(n)[ DoWant(n) ]

(I'm not posting the exact question on the final since the 2nd section is still having their exam right now)

Okay. So we show that that above equation is true by mathematical induction. Okay. Fair enough. That wasn't too hard. Oh, but, wait again, now let's do it again by a "combinatorial argument"! Yay. How fun ... not.

So that basically sums up the "most failest of the fail" from all the questions. I really felt like writing something like this:

Okay. So we want to use that in our production code. Our production code only uses values of n up to at most 20 due to the fact that calculating large combinatorial functions take up way too much CPU time [Also, 20! is the most we can fit into 64 bits]. (We want to show that is true so we can use the more efficient function on the left)

1. Write a small program that tests Hihi(n+1) = SumFrom(i=2)to(n)[ DoWant(n) ] with values from 2 up to 20.
2. Observe that the program determines that the equation is true for all those values of n.
3. Therefore it is good enough for our use (Because the result must fit in a 64 bit number!). Done.

Okay. So here we go (In C code):

#include <assert.h>
#include <stdio.h>
#include <time.h> // To calculate execution time.

#define TEST_FLOOR      2
#define TEST_CEILING    20

// Returns n! as a 64bit number
// PreCondition:  0 <= n <= 20
// PostCondition: n! is returned.
unsigned long long factorial(int n) {
    assert(n >= 0 && n <= 20); // Enforce precondition
    if (n == 0)
        return 1;
    else
        return n * factorial(n-1);
}

// Calculates the combinatorial (n choose r)
// PreCondition:  0 <= n <= 20 AND 0 <= r <= n
// PostCondition: Returns (n choose r) as a 64 bit number
unsigned long long choose(int n, int r) {
    assert(n >= 0 && n <= 20); // Enforce preconditions
    assert(r >= 0 && r <= n);
    return factorial(n) / factorial(r) / factorial(n-r);
}

// Calculate the sum of a function from j to n recursively
// PreCondition: 2 <= n <= 20
// PostCondition: Calculates and returns the sum from j to n of (j choose 2)
unsigned long long sum(int n) {
    assert(2 <= n && n <= 20);
    if (n == 2)
        return 1; // (2 choose 2) == 1  
    else
        return choose(n, 2) + sum(n-1);
}

// Test Module for ((n+1) choose 3) == Sum((j choose 2), j=2, n)
// PreCondition:  2 <= n <= 19
// PostCondition: Test case information is printed to the console.
void performTestCase(int n) {
    unsigned long long lhs = choose(n+1, 3);
    unsigned long long rhs = sum(n);
    printf(" (%2d+1 choose 3) = %4lld, ", n, lhs);
    printf("SumFrom(j=2)to(%2d) = %4lld : ", n, rhs);
    printf("%s\n", (lhs == rhs) ? "Passed." : "Failed.");
}

int main() {
    clock_t begin = clock();
    printf(" ==== RailGun's Proof By Computation ==== \n");
    int i;
    for (i = TEST_FLOOR; i <= (TEST_CEILING-1); i++)
        performTestCase(i);
    printf("Execution Time: %f milliseconds\n", (double)begin-(double)clock());
    return 0;
}

And the execution:
$ ./CombiProof
==== RailGun's Proof By Computation ====
( 2+1 choose 3) = 1, SumFrom(j=2)to( 2) = 1 : Passed.
( 3+1 choose 3) = 4, SumFrom(j=2)to( 3) = 4 : Passed.
( 4+1 choose 3) = 10, SumFrom(j=2)to( 4) = 10 : Passed.
( 5+1 choose 3) = 20, SumFrom(j=2)to( 5) = 20 : Passed.
( 6+1 choose 3) = 35, SumFrom(j=2)to( 6) = 35 : Passed.
( 7+1 choose 3) = 56, SumFrom(j=2)to( 7) = 56 : Passed.
( 8+1 choose 3) = 84, SumFrom(j=2)to( 8) = 84 : Passed.
( 9+1 choose 3) = 120, SumFrom(j=2)to( 9) = 120 : Passed.
(10+1 choose 3) = 165, SumFrom(j=2)to(10) = 165 : Passed.
(11+1 choose 3) = 220, SumFrom(j=2)to(11) = 220 : Passed.
(12+1 choose 3) = 286, SumFrom(j=2)to(12) = 286 : Passed.
(13+1 choose 3) = 364, SumFrom(j=2)to(13) = 364 : Passed.
(14+1 choose 3) = 455, SumFrom(j=2)to(14) = 455 : Passed.
(15+1 choose 3) = 560, SumFrom(j=2)to(15) = 560 : Passed.
(16+1 choose 3) = 680, SumFrom(j=2)to(16) = 680 : Passed.
(17+1 choose 3) = 816, SumFrom(j=2)to(17) = 816 : Passed.
(18+1 choose 3) = 969, SumFrom(j=2)to(18) = 969 : Passed.
(19+1 choose 3) = 1140, SumFrom(j=2)to(19) = 1140 : Passed.
Execution Time: 0.000000 milliseconds

Less than 1 millisecond of computer time. There you go.

Last Stand Of The 321...

From the movie 300:

It's been more than thirty years since the wolf and the winter cold. And now, as then, it is not fear that grips him, only restlessness. A heightened sense of things. The seaborn breeze, coolly, kissing the sweat at his chest and neck. Gulls cawing, complaining, even as they feast on the thousands of floating dead. The steady breathing of the 300 at his back, ready to die for him without a moment's pause. Everyone of them ready, to die.

2 hours to the 321 final...

2 Down; 1 More to go

Philosophy down today.

The day of reckoning is about to dawn... CSE 321 (Discreet Mathematics) final in 12 hours. The final for this class is notoriously known as the "Destroyer of Worlds".

Yay

CSE 370 final down. That was an awesome class. I never thought that I would like hardware that much. Verilog HDL is a beauty.

CSE 321 final in 2 days...

Philosophy 346A final tomorrow (Epic Fail?)...

The Proving Grounds

3 days to the CSE 321 final...