hn-classics/_stories/2008/6100034.md

---
created_at: '2013-07-25T00:03:54.000Z'
title: A Practical Computer Science Primer (2008)
url: https://learn-cs.pbworks.com/w/page/15774601/FrontPage
author: barce
points: 66
story_text: ''
comment_text: 
num_comments: 8
story_id: 
story_title: 
story_url: 
parent_id: 
created_at_i: 1374710634
_tags:
- story
- author_barce
- story_6100034
objectID: '6100034'
year: 2008

---
**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](http://groups.google.com/group/learn_cs) 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](http://www.stanford.edu/class/cs106x/) but also draws upon
MIT's "[Course
Six](http://courses.csail.mit.edu/6.01/spring08/general-information.html)"
and "post collegiate web CS," such as
[memcached](http://en.wikipedia.org/wiki/Memcached),
[MapReduce](http://en.wikipedia.org/wiki/MapReduce), and
[Paxos](http://en.wikipedia.org/wiki/Paxos_algorithm). 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](http://david.weekly.org/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. 

 

****

1.  [BASICS](#BASICS)
2.  [COMPUTER ARCHITECTURE](#COMPUTERARCHITECTURE)
3.  [ALGORITHMS](#ALGORITHMS)
4.  [LANGUAGES & COMPILERS](#LANGUAGESampCOMPILERS)
5.  [OPERATING SYSTEMS](#OPERATINGSYSTEMS)
6.  [GRAPHICS](#GRAPHICS)
7.  [AUDIO](#AUDIO)
8.  [ARTIFICIAL INTELLIGENCE](#ARTIFICIALINTELLIGENCE)
9.  [CRYPTOGRAPHY](#CRYPTOGRAPHY)
10. [NETWORKING](#NETWORKING)
11. [SECURITY](#SECURITY)
12. [DATABASES](#DATABASES)
13. [MODERN WEB APPLICATION
    PROGRAMMING](#MODERNWEBAPPLICATIONPROGRAMMING)
14. [GOING BIG: PRACTICAL SCALING](#GOINGBIGPRACTICALSCALING)
15. [MOBILE APPLICATIONS](#MOBILEAPPLICATIONS)
16. [SOFTWARE ENGINEERING](#SOFTWAREENGINEERING)

  

# 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

 

 

# 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 & Tansistors
  - 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

Variable Types

  - arrays
  - hash tables
  - floating & fixed point

Lists, queues, stacks & circular buffers

  - adding & deleting
  - sorting

Trees

Relational Databases (more later)

Indexes

[State Machines](http://en.wikipedia.org/wiki/Finite_state_machine)

[Big O Notation](http://en.wikipedia.org/wiki/Big_O_notation)

[Dynamic Programming](http://en.wikipedia.org/wiki/Dynamic_programming)

[Dijkstra's
Algorithm](http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) 

 

# 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**](http://en.wikipedia.org/wiki/Imperative_programming):
    [C](http://en.wikipedia.org/wiki/C_%28programming_language%29),
    [C++](http://en.wikipedia.org/wiki/C%2B%2B), 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

  - matrix transforms

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
  - Baysian 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](http://www.wireshark.org/) (sniffer, free download,
    formerly known as Ethereal)
  - [Tor](http://www.torproject.org/) (onion router, free download)

 

## READING

 

## TOPICS

  - Viruses
  - Worms
  - Keysniffers & Dongles
  - Man in the Middle
  - [Phishing](http://en.wikipedia.org/wiki/Phishing)
  - Brute Force Attacks
  - Stack Smashing
  - [Fuzzing](http://en.wikipedia.org/wiki/Fuzz_testing)
  - Phreaking &
    [Redboxing](http://en.wikipedia.org/wiki/Red_box_%28phreaking%29)
  - Traffic Analysis
  - Proxies & Onion Routing, [Tor](http://www.torproject.org/)
  - Social Hacking
  - Sniffers
  - IDS
  - Tripwire
  - Kernel Hardening
  - [XSS](http://en.wikipedia.org/wiki/Cross-site_scripting) &
    [XSRF](http://en.wikipedia.org/wiki/Cross-site_request_forgery)
  - [DNS Poisoning](http://en.wikipedia.org/wiki/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

  - Examining Meebo

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](http://en.wikipedia.org/wiki/Paxos_algorithm)

Modern Cluster Tools

  - LJ: mogilefs, memcached, perlbal
  - GOOG: [BigTable](http://labs.google.com/papers/bigtable.html),
    [GFS](http://labs.google.com/papers/gfs.html),
    [MapReduce](http://labs.google.com/papers/mapreduce.html),
    [Chubby](http://labs.google.com/papers/chubby.html)
  - AMZN: [EC2](http://aws.amazon.com/ec2),
    [S3](http://aws.amazon.com/s3)
  - YHOO: [Hadoop](http://hadoop.apache.org/core/)

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