Project Euler

I started working on Project Euler since I had some down time during spring break.

I started working yesterday evening and did some more problems this morning. I've solved the first 10 but still am not even halfway to completing 'Level 1.' The good news is that most of the problems don't take longer than 10 minutes to start to finish, especially when using Python. Generators, list slice assignments and list comprehensions made things like iterating Fibonacci sequences and computing prime numbers fast and easy.

What I've learned in each course this quarter

Networks:

Now that I've taken Networks, I believe I could describe, at some points in excruciating detail, everything that occurs when a user clicks 'Go' to load a webpage, to the page displaying on their screen.

This includes all the Operating System considerations, sockets, threading, buffering, packets/segments, error detection schemes, framing, Ethernet, DHCP, ARQ, NAT, STUN, TCP, IP, reliability, ordering, congestion control, routing, forwarding, heterogeneity of network topology, BGP; plus real-time application support, wireless protocol, and RFID thrown in just for fun.

Things we didn't learn about: DNS. But I can fill in most of the blanks on this one myself. And we didn't spend much time on application layer protocol such as HTTP, though we touched on SMTP some.

We covered so much in this class that my understanding of network principles didn't congeal until it was time to review for the final.

Algorithms:

We surveyed a suite of useful problems solved using Greedy algorithms, Divide and Conquer techniques, and Dynamic Programming. We also learned how to show that a problem is NP complete or prove that an algorithm is correct and/or efficient.

Key takeaways: the incredibly useful technique of dynamic programming to exploit redundant subproblems to solve a larger problem efficiently, and firm understanding of the definition of NP and NP-complete.

Technical Communication:

This class sharpened my understanding for and gave me practice with presenting technical information. Still, the one liner for this class remains:
Tell them what you're about to tell them, tell them, then tell them what you just told them.

Warfare and network algorithms

How much does computer science owe to the military?

Well let's see...

• The Department of Defense basically invented the internet, and with it "our entire field" to paraphrase the UW CSE department chair during one of the lectures he gave...on operating systems.


• The Ford-Fulkerson network flow algorithm used to route traffic through nodes was invented in 1956. Not for sending oil along pipelines or routing civilian traffic--to determine if the Russian military could successfully move enough troops into neighboring countries using the roads currently in place to successfully invade them. The Cold War is responsible for so much useful science!


• The limitations of reliable communication with TCP were known long before, based on the notion of two separate armies coordinating an attack on a territory from two fronts. If only one attacks alone, devastating losses are incurred. If both strike simultaneously, the territory is easily conquered. The only problem? Trying to agree on a time to strike, with an unreliable messenger running back and forth "routing" messages between the two on horseback or foot. What protocol would you use?

It's nice to think that most of the early computer science leaps and bounds were born out of the circle surrounding the hippie 60's XEROX PARC culture, but the truth is far more...crew cut.

Write-Only Memory

It is real.

Here it is, in all its Wikipedia glory

Out of frustration with the long and seemingly useless chain of approvals required of component specifications, during which no actual checking seemed to occur, an engineer at Signetics once created a specification for a write-only memory and included it with a bunch of other specifications to be approved. This inclusion came to the attention of Signetics management only when regular customers started calling and asking for pricing information. Signetics published a corrected edition of the data book and requested the return of the 'erroneous' ones.

And here is the April Fool's prank pulled by Signetics: