David Weekly's Practical Computer Science Primer
April 14, 2008 onwards: free in-person group study & lectures Monday nights 7-11pm in South Bay, CA. Bring food & drink to share.
This evolving online curriculum is designed for a motivated and intelligent college graduate with no formal training in computer science to efficiently learn CS theory and culture in about a year of part-time study. If this appeals to you, please join the Google Group to discuss, particularly if you are in the San Francisco Bay Area and would like to attend the in-person meetings.
This curriculum is loosely based on the CS core at Stanford but also draws upon MIT's "Course Six" and "post collegiate web CS," such as memcached, MapReduce, and Paxos. Portions of the traditional CS curriculum less relevant to modern practice are deliberately omitted (students will not be required to build their own OS and compiler or build skip lists and red-black trees) and will include some non-traditional curriculum (such as a datacenter tour). The class is being offered without cost, but students are expected to devote meaningful time to study, help fellow students with the curriculum, share notes online, and bring food to the Monday night meetings.
Books are listed below with links to their Amazon pages and current prices; these books are considered canonical in their subject area and students particularly excited by a given topic are encouraged to purchase the textbook, especially as most are very well-written and approachable even from a layman perspective. Students are not expected to purchase all or even most of the books when taking the overview version of the course, as the overview will only quickly touch on the key subjects from each topic. Lectures will be recorded and uploaded in MP3 format as well as being summarized on this wiki.
The pace for the in-person lectures is deliberately aggressive, seeking to compress about a semester's worth of college learning into each 2-3 hour lecture / peer learning experience. This class has a secondary purpose of being a learning lab, experimenting with more effective and efficient ways to educate smart people. David's ultimate goal is to found a university based on the findings from experiments like these. Other classes, such as compressing an MBA into a few weeks of part time study, may be explored in 2009.
"...but why study computer science? There are many other interesting things to study, like French Literature."
Knowledge of practical computer science will let you leverage your ideas and pave your own destiny. There is almost no other field that with basic training and minimal resources will let a person make such widespread, rapid, and effective change in other people's lives. You can take an idea from concept to use by thousands of people in a matter of hours and use by millions of people in a matter of a year. Jobs in computer science typically pay well ($70k-120k a year) and include a wealth of benefits and exciting opportunities. There is a severe and likely long-term shortage of programmers in the US - you'll have your pick of work environments, in addition to the possibility of starting your own venture or joining someone else as a technical co-founder.
"...but I'm not good at math!"
That's okay! Most computer work has very little to do with math. It has everything to do with logic and philosophy. If you can write a recipe and make a good argument from well-stated premises, you've got the right kind of mind for computer science.
BASICS
Why is computer science an interesting field? Where did it come from? Who are the notable figures and what did they do? What is the culture of computer science? While many parts of computer science continue to unfold anew, a surprising breadth of innovation and discovery in symbolic processing began as early as 1822, and most modern computer science theory had been firmly hashed out by the 1970's. Indeed, Douglas Englebart's famous demo, given in 1968, demonstrates many technologies that would still be considered quite modern / advanced.
FIELD TRIP
READING
TOPICS
- "Hello World!"
- Hacking
- A Brief History of CS
- Babbage's Difference Engine (1822) & Analytical Engine (1837)
- Turing @ Bletchley Park (1937)
- Vannevar Bush & "As We May Think" (1945)
- ENIAC (1946)
- The Transistor @ Bell Labs (1947)
- The Xanadu Project (1960)
- Englebart & The Demo (1968) (Alt Link: Video Devided into 35 parts by subject)
- ARPANET (1969)
- Knuth & The Art of Computer Programming
- Altair, MS, Homebrew, PARC, Apple
- RMS, Linus, Open Source
- Modern culture: Slashdot, XKCD, ThinkGeek, Fark, LOLcats
COMPUTER ARCHITECTURE
Most modern computers are made from several silicon chips that interface on a "motherboard". Knowing how these chips operate to perform the function of a computer and the fundamentals of logic involved is important for designing systems that make the most out of their hardware and software working in unison.
READING
TOPICS
- Vacuum Tubes & Transistors
- Logic Gates
- Signal Processing
- Hard drives
- Processors & Cache, Multicore Processors
- Motherboards: North Bridge / South Bridge
- RAID
ALGORITHMS
Algorithms are programming pattterns used to organize, store, and solve certain classes of problems. There are a whole set of different algorithms, for instance, to sort a list of numbers from lowest to highest. They are all correct, but some may be faster than others in certain (or all) circumstances. Knowing what algorithms are out there and when to use each is at the core of a computer scientist's competence.
READING
TOPICS
LANGUAGES & COMPILERS
While CPUs have a native instruction set of 1's and 0's called "machine code", humans communicate more efficiently and naturally with instructions written in a human language. Because human languages can be ambiguous in meaning and overly broad in scope, "computer languages" were invented to allow humans to enter commands for the computer in a human-readable format but one that the computer could also unambiguously interpret. The process of turning a program written in a computer language into machine code is called "compiling" and is usually done by a separate program called a "compiler". Many different computer langauges have been developed, but they generally fall into a relatively small number of families. Understanding the strengths and weaknesses of different languages and language families allows a programmer to correctly select a language for use in a project. A deep enough understanding of the design and implementation of computer languages will allow the student to design their own computer language.
READING
TOPICS
- Overview of Language Families
- direct: assembly, brainfuck
- imperative: C, C++, FORTRAN, Pascal
- message-based: Smalltalk & Objective/C
- interpreted: Perl, Python, Ruby, BASIC, Javascript, Lua
- web-integrated: PHP, Coldfusion, ASP
- managed: C#, ASP.NET, Java
- functional: Scheme, Lisp, Erlang
- domain specific: MatLab, R, Mathematica, SQL, ActionScript
- Frameworks: Rails, Symphony
- Extending Languages: BOOST, CPAN, Prototype
- Grammars & Parsers: lex & yacc, bison
OPERATING SYSTEMS
While historically computers simply ran one program at a time that had access to all of the resources of the computer, it was later found that it would be more useful to have multiple processes that could run at the same time. Advanced techniques were required to keep these processes from harming each other. The "master program" that oversees the running of subprograms is called the "operating system". Operating systems provide a number of useful services to running programs, most notably abstracting away many of the particularities of the computer on which the program is running. This allows the same program to be run on many different computers with different accessories without having to be rewritten. Understanding how operating systems function and allow programs to run is a critical component of a modern CS curriculum.
READING
TOPICS
- The Boot Process
- Schedulers
- ring 0
- prioritization & timeslicing
- drivers
- filesystems
- network filesystems
- virtual memory / swap
- strace
- building a kernel
- processes vs threads
- interrupts & signals
- select(), poll(), epoll
- 32-bit vs 64-bit
- virtualization & virtual machines
- realtime operating systems
GRAPHICS
The main way that people receive information from computers is through visually presentation on a flat, vertical surface in front of the user. It's important for a computer scientist to understand how computers prepare text, pictures, movies, and 3D information for a human user's consumption and at a basic level how display devices work.
READING
TOPICS
- raster versus vector, CRT vs LCDs
- anti-aliasing, shape-drawing, Painter's Method, z-buffering
- fonts & typography, kerning, postscript, ClearType
- camera sensors, RAW format
- perceptual coding & compression
- picture encoding - BMP, GIF, JPG, PNG
- video encoding - MPEG, AVI, MOV
- 3D: raytracers vs rasterizers, shaders
- modern graphics cards
- graphing information
- usability & user-centric design
AUDIO
While graphics form the principal method for computers to present information to humans, most modern computers are equipped with the ability to generate audio. It is useful to understand how computers record, compress, transmit, and play audio.
READING
TOPICS
- MIDI
- WAV, sampling rate / bit depth
- band-pass filters
- basics of perceptual coding
- Fourier transforms
- FFT & DFT, MDCT
- signal processing & compression
- MP3
- Speech compression (ACELP.NET, GSM)
- 5.1 sound
- THX
ARTIFICIAL INTELLIGENCE
While computer intelligence works in a very different fashion than human intelligence, we can teach computers to attack complicated problems in logical ways. We can even teach computers to self-improve, modelling decision functions after neurons. Knowing how to make computers "artificially intelligent" and good decisionmakers is an important tenet of modern computer science.
READING
TOPICS
- Markov Chains
- Bayesian Networks
- A* Search
- Heuristics, Local Minima
- Neural Networks
- Simulated Annealing
- Genetic Algorithms
CRYPTOGRAPHY
While techniques for keeping messages secret and verifying their correctness and authenticity extend back thousands of years, new mathematical techniques have become available in the past few decades that enable much more powerful methods for verifying the identity of someone you've never met before and even exchanging secret information without having to have a meeting in advance to agree on a private protocol. Knowing how data can be made secure against tampering or discovery is a critical component of any system that handles confidential data.
READING
TOPICS
- Caesar Ciphers & ROT-13
- One-time pads
- Hashes (MD5 & SHA-1)
- Symmetric Cryptography
- Public Keys
- Galois Fields & ECC
- Digital Signatures
- Kerberos
- Zero-knowledge proofs
- Mixmasters
- Steganography
SEE ALSO
NETWORKING
Most modern computer owners know that a computer is a lot less valuable when not connected to thet network. The rapid exchange of information, personal connections, and ideas through computer networks allow people to be in touch with each other and participating in a global economy of ideas on a continuous basis. Understanding how different kinds of information are transmitted across a computer network will help students build systems that make effective use of networks and diagnose problems with network applications.
READING
TOPICS
- Ethernet
- OSI 7-layer stack
- Switches, Hubs, Routers & Managed vs Unmanaged
- IP: DHCP & BOOTP
- UDP: DNS & NTP
- TCP: 3-Way Handshake, Windows, Buffers, Nagle's Algorithm, Lingering CLose
- SMTP & Email infrastructure
- HTTP & Proxies
- SSL / HTTPS
- BGP, Routing
SECURITY
Now that you know about how computer systems are designed to operate, it is important to study how accidents (even small things overlooked) in the design of computer systems can lead to their compromise by intelligent attackers armed with tools of increasing sophistication. Attacks are possible on many levels, including physical penetration, social engineering, internal compromise, password guessing, and network-level attacks.
PROGRAMS
- WireShark (sniffer, free download, formerly known as Ethereal)
- Tor (onion router, free download)
READING
TOPICS
- Viruses
- Worms
- Keysniffers & Dongles
- Man in the Middle
- Phishing
- Brute Force Attacks
- Stack Smashing
- Fuzzing
- Phreaking & Redboxing
- Traffic Analysis
- Proxies & Onion Routing, Tor
- Social Hacking
- Sniffers
- IDS
- Tripwire
- Kernel Hardening
- XSS & XSRF
- DNS Poisoning
- Zombies & Botnets
- Hacker culture: IRC, Defcon, 2600
DATABASES
Relational databases like Oracle, MySQL, Postgres, and DB2 underlie nearly every significant information repository on the planet. Understanding how these databases work and how to efficiently store and retrieve data is critical for modern programmers.
READING
TOPICS
MODERN WEB APPLICATION PROGRAMMING
Modern web application programming requires use of new tools and techniques to address the peculiarities of client-server programming in the land of the browser. Browsers are adopting more comprehensive standards of higher quality and are more rigorously adhering to them, allowing developers to make ever-more sophisticated applications available to users.
READING
TOPICS
- The DOM, DHTML, CSS
- Javascript
- AJAX (dojo, mootools, prototype, yui)
- Examining Google Maps & GMail
- Comet
- Widgets (flash, iframe, and js)
- OpenID & OAuth
- webhooks
- RSS & Atom
- Facebook applications
- Standalone: TiddlyWiki
- Offline: Google Gears & AIR
- SEO: sitemaps & robots.txt
GOING BIG: PRACTICAL SCALING
Once an application is built and begins to become popular, the techniques required to make the application available to a large number of people, be resilient to attacks, and maintain a low per-user operational cost comprise one of the most rapidly-evolving fields of computer science.
READING
TOPICS
- loadbalancers
- filers
- hosting & colocation
- distributed transations
- robust queues
- virtualization
- partitioning
- heartbeats / round-robin
- Paxos
- Modern Cluster Tools
- Resisting Abuse
- DDOS Mitigation
- CAPTCHAs
- Reputation Systems
MOBILE APPLICATIONS
Making computer programs available for use on highly portable computers requires knowledge of new protocols and techniques unique to the "cell phone" industry. Learning how to effectively integrate cell phones into an application can greatly enhance your application's reach and usefulness.
TOPICS
- what is spectrum / RF?
- antennas
- bandwidth
- GSM / CDMA
- WiFi / 802.11n / WiMAX
- SMS
- WAP
- Java apps
- iPhone Dev Kit
SOFTWARE ENGINEERING
While Computer Science concerns itself with the theory of software, Software Engineering concerns itself with the real-world pragmatics of building large software systems, attempting to answer the question of how you can build the highest-quality software in the shortest time with the most limited of resources. A programmer is the person who actually implements such systems. By way of analogy to building bridges, the programmer is a metalworker, the software engineer is an architect who designs the bridge and ensures its proper construction, and the computer scientist is the materials scientist who researches better steel.
READING
TOPICS
- Process Development
- Defect Tracking
- Change Management
- Testing (Unit Tests, Whitebox Testing, Blackbox Testing, Load Tests)
- Continuous Integration
- Extreme Programming
- Agile Development
- Scrum
Comments (8)
Eva Holtz said
at 9:48 am on Mar 28, 2008
When do you sleep? :)
btsavage said
at 12:08 am on Apr 1, 2008
man, if only Stanford had covered this ground... So practical...
Kara Murphy said
at 12:19 pm on Apr 1, 2008
This is terrific, David! I'm in, I've always wanted to learn this.
Hiren Patel said
at 9:42 pm on Apr 28, 2008
post hw assignments here :)
marguerite manteau-rao said
at 9:38 am on Apr 29, 2008
Thanks David, everybody in the class, for an exciting evening of learning last night. I feel so privileged to participate.
Ellen said
at 5:38 pm on Apr 30, 2008
Totally fab class, but do you really want to post the address on the world wide internet?
Brian Jones said
at 2:06 am on May 4, 2008
I can't wait until we cover cell phone stuff...
Hiren Patel said
at 7:24 pm on May 7, 2008
I can't wait for more brain food from David whiteboard. ;D
You don't have permission to comment on this page.