18 KiB
| created_at | title | url | author | points | story_text | comment_text | num_comments | story_id | story_title | story_url | parent_id | created_at_i | _tags | objectID | year | |||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2013-07-25T00:03:54.000Z | A Practical Computer Science Primer (2008) | https://learn-cs.pbworks.com/w/page/15774601/FrontPage | barce | 66 | 8 | 1374710634 |
|
6100034 | 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 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
- COMPUTER ARCHITECTURE
- ALGORITHMS
- LANGUAGES & COMPILERS
- OPERATING SYSTEMS
- GRAPHICS
- AUDIO
- ARTIFICIAL INTELLIGENCE
- CRYPTOGRAPHY
- NETWORKING
- SECURITY
- DATABASES
- MODERN WEB APPLICATION PROGRAMMING
- GOING BIG: PRACTICAL SCALING
- MOBILE APPLICATIONS
- SOFTWARE ENGINEERING
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
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
- 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
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
- 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
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