743 lines
18 KiB
Markdown
743 lines
18 KiB
Markdown
---
|
||
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
|