• If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

View
 

FrontPage

Page history last edited by David Weekly 3 years, 11 months ago

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

 

 

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
    • 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
  • 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
    • 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
  • 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.