Computer Science – Matt Chung

Masters in CS paying off

November 15, 2019 itsmemattchung

Taking computer science courses are already paying off in my career. Nothing too significant (yet) but I am witnessing small wins.

For example, this past summer I suffered through HPCA (high performance computing architecture), a course historically only offered in the longer semesters (e.g. fall, spring). In the course, I learned a lot of theory: barrier synchronization, processing pipelines, instruction scheduling, multi level caches, branch predicators, cache coherence protocols, and much more (many of which I have already purged from my memory). However, since most of that knowledge was primarily theory, very little of it I’ve been able to directly apply to my day to day job.

Until a couple days ago.

While at work, my co-worker had pointed out that the unlikely C function calls were sprinkled throughout our code base, used for branch prediction. And thanks to theory, I was able to describe to another co worker how the compiler (with its understanding of the underlying CPU architecture) will rearrange the assembly (or machine code) in order to avoid a branch prediction miss: if the wrong instruction is fetched, the processing pipeline must flush all the previous instructions queued in the pipeline, temporarily halting the pipeline, which ultimately reduces the throughput.

And this is just one example of how taking my masters had paid off. There have been a number of other situations (like understanding shared memory and interprocess communication) that I’ve been able to apply theory from academia to practice at work.

Thanks to the program, I’m feeling much more competent and confident working as a software developer at Amazon Web Services.

Week 1 of master’s in computer science

January 22, 2019 itsmemattchung

January 7th, 2019 marks the first day of my computer science master’s program through University of Georgia Tech. The week leading up to the first day was somewhat stressful since I was mid flight (returning to Seattle from London), my plane hovering over the massive blue sea, while I frantically typed away on my keyboard trying to register for a course in my allotted time window. Because of the spotty internet connection on the airplane, it took me about an hour and half to register for my course and by that point, the open spots filled up so fast that I positioned 100+ on the wait list (which I discovered, later on after reading online posts, that 100+ wait list is normal and that I would like get get into the course, which I did).

Anyways, despite all that headache, I’m officially enrolled in a course that I’ve wanted to take for a very very long time: Introduction to Operating Systems. So far, although it’s only been 1 week, I love the course, for multiple reasons.

First, I love the collaborative and sense of community of the program. Before getting into this master’s program, I was taking a handful of undergraduate computer science courses (e.g. computer organization, discrete mathematics, data structures) from University of North Dakota and University of Northern Iowa, two excellent schools that offered courses through their Distant Learning platform. Now although I learned a lot from the courses, I always felt like I was working in isolation, by myself, my only interaction was through a few short threaded e-mails with the professors. But now, with this course, there’s an online forum (i.e. Piazza) and chatty chatroom (via Slack, which was paid out of pocket by one of the TA of the course), where students fire off questions and comments (especially random comments in the #random slack channel). So in a sense, despite never meeting these folks, there’s a sense of comradery, a shared a goal.

Second, I’m learning a ton of material that’s not only applicable to my day to day job (as a software engineer) but material that I’m genuinely interested in. For the first week, the professor of the course has us reading a 30 page white paper (titled “Introduction to Threading”) written in 1989, a seminal piece of work (on threads and concurrency) that gives me perspective and appreciation of my industry. In addition to reading the white paper, I’m watching lectures covering fundamental operating system concepts (e.g. processes, virtual memory) and above all, writing C code! A ton of C code!

The project has us writing code for a multi-threaded client and multi-threaded web server (think implementing HTTP protocol) that’s intended to teach us how to write safe, concurrent systems that utilize the threading facility offered by the operating system.

The beauty of dynamic programming

June 1, 2018 itsmemattchung

I just discovered dynamic programming and damn, I’m blown away by the concept. The other day, hile working through a homework assignment, I compared the run times between two python functions that I wrote, one function written recursively and the other written in a dynamic programming fashion. Starting with the recursive solution, I arrived at the following:

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

def fibonacci(n):

if n == 0:

return 0

if n == 1:

return 1

return fibonacci(n-1) + fibonacci(n-2)

That’s a fairly standard implementation of Fibonacci. There are two base cases; n=0; n=1. So when n is either of these two numbers, the function simply returns 0 or 1, respectively. But for any other number, the function recursively calls itself until reaching the aforementioned base cases.

So far so good, right? And for calculating small values of n, this implementation doesn’t really present a problem. But say we want to calculate fibonacci when n equals 40. How long does this take? Alarmingly, this computation hovers around 45 seconds:

./fibonacci.py 40
fibonacci(40) = 102334155 took 45.22154 seconds

1 2	./fibonacci.py 40 fibonacci(40) = 102334155 took 45.22154 seconds

Now, what if we run the same calculation. But this time, we run it using a dynamic programming technique? How much time does that shave off?

./fibonacci.py  --dynamic-programming 40
fibonacci(40) = 102334155 took 0.00002 seconds

1 2	./fibonacci.py --dynamic-programming 40 fibonacci(40) = 102334155 took 0.00002 seconds

What ?! From 45 seconds down to under a millisecond ?! How is that possible?

def fibonacci_dynamic_programming(n):
    fibonacci = [0,1]
    for _ in range(0, n):
        fibonacci.append(fibonacci[-1] + fibonacci[-2])
    return fibonacci[n-1] + fibonacci[n-2]

def fibonacci_dynamic_programming(n):

fibonacci = [0,1]

for _ in range(0, n):

fibonacci.append(fibonacci[-1] + fibonacci[-2])

return fibonacci[n-1] + fibonacci[n-2]

As you can see from the code above, instead of recurisvely calling fibonacci, we iteratively calculate all the values. In other words, this implementation runs linearly (i.e. direct proportion to n), unlike the first, recursive implementation, which runs exponentially.