COS 109 Summary: 2008

Tue Dec 9 10:08:30 EST 2008

This is a rough summary of the topics that we have covered in class. It doesn't include material in problem sets or labs. You are responsible for important ideas and facts in those as well, but not for detailed trivia like how to write syntactically correct HTML or Javascript or how RSA really works. The same goes for the readings.

On exams, the emphasis is meant to be on understanding, which is usually tested through problems that require you to think and reason about something new or unfamiliar that is based on material covered. Often that reasoning is quantitative; the theory is that if you understand the material, you will be able to do the right computation to demonstrate your understanding. Sometimes the reasoning requires recognizing that some unfamiliar system or artifact is analogous to one seen in class. Sometimes it's just applying common sense and some of what you've learned.

Broadly, these are the kinds of topics that I hope you understand well enough to answer questions about:

  • How computers work and are organized architecturally.
  • How various components and devices are constructed, and their main physical characteristics.
  • How information -- numbers, characters, colors, instructions, and so on -- is represented, stored, and processed digitally.
  • How many bits it takes to encode or enumerate things; how many things can be encoded or enumerated with a given number of bits
  • Basic ideas of storing numbers, characters, instructions, etc.
  • How fundamental algorithms work, and how fast they run, as a function of how much data they have to process.
  • How fast area, volume, connections, combinations, etc., grow in proportion to size measures.
  • Fundamental capabilities and limits of digital computation.

  • How we tell computers what to do.
  • How programming languages work and their main characteristics.
  • How languages are processed.
  • How we express computations in programming languages.
  • Fundamental software systems.
  • What an operating system does, and how.
  • How file systems store and retrieve information.
  • How software is organized and developed.
  • Legal issues around software.

  • How networks work; major networking technologies and their properties.
  • How the Internet works.
  • How Internet applications work.
  • Threats and risks on the Internet and how they work.
  • Defenses and how they work.

  • How secre/symmetric key and public key cryptography work and how they are used. What each is best suited for, and why.
  • How compression works for various kinds of information.
  • How error detection and correction work.
  • How peer to peer networks work.
  • How wireless communications systems work.
  • How search engines work.

  • Major intellectual property and other legal issues for digital technology.
  • Other social, economic, and political issues.

  • Some sense of the history and evolution of all of the above.
  • The role of a few crucial and/or well known people.

     

    Here's the approximate outline of what we covered:

    HARDWARE
    
    logical/functional organization of a computer
    physical structure
    major pieces: cpu, memory, disks, peripheral devices, etc.
    acronyms and numbers: MHz, GHz, MB, RAM, ROM, Kbps
    prefixes: pico, nano, micro, milli, kilo, mega, giga, tera, peta, ...
    
    bits, bytes, representation of information
    analog versus digital
    binary numbers and arithmetic
    	hexadecimal notation
    	powers of two and powers of ten
    meaning of bits depends on context
    	numbers of various sizes
    	characters in various scripts
    	machine instructions and addresses
    	ascii and unicode
    color encoding and representation
    
    CPU operation
    	arithmetic, memory access, decision making, control
    different processors
    	intel vs powerpc (old mac) vs palm pilot vs ...
    instructions; toy machine
    	branching & conditional instructions
    	be able to accurately follow the steps of a program
    fetch / decode / execute cycle
    	instructions in same memory as data
    computer architecture
    caching in CPU and elsewhere
    von Neumann model of computer
    Turing equivalence of all computers
    integrated circuit fabrication
    Moore's law, exponential growth
    Rule of 72
    
    other kinds of computers
    
    SOFTWARE
    
    algorithms: defined operations, defined steps, terminates
    linear-time algorithms
    	searching, selecting, summarizing
    log n algorithms:
    	binary search; divide and conquer
    sorting
    	quadratic (n^2), quicksort (n log n)
    complexity of algorithms (log n, n, n log n, n^2, n^3, ..., 2^n)
    	what these complexity formulas mean
    	towers of hanoi, traveling salesman problem, hard problems, P vs NP
    
    evolution of programming languages
    	machine and assembly language
    	high level languages: Fortran, C, C++, Java, Javascript, ...
    	languages vs programming languages
    	compilers, compilation
    	executable files; interpretation and simulation
    Javascript
    	variables and expressions
    	assignment statements, alert, prompt, etc.
    	if-else for making decisions
    	while loop for repeating a computation so long as a test succeeds
    	functions
    	how it works, but NOT detailed syntax
    		be able to accurately follow the steps of a program
    		be able to identify and fix simple errors
    
    operating systems
    	history
    	what they do: manage memory, run programs, file system
    	applications vs operating systems
    	system interface: system calls, APIs
    	platforms, middleware, virtual machines
    	device drivers
    	bootstrapping
    file systems
    	directories/folders and files
    	logical structure vs physical implementation
    	file system implementation
    		blocks, allocation table, free list
    	finding files
    	file open, save, delete, etc.
    	what's remembered where for how long
    	network file systems
    	other file systems
    Unix / Linux
    	and open source software
    programming in the real world
    	bugs
    patents & copyrights
    	intellectual property issues for software
    
    COMMUNICATIONS
    
    history
    ethernet, broadcast media
    Internet structure
    names, addresses, routing, protocols
    	traceroute
    domain names, DNS, root servers
    	caching
    IP addresses
    	dotted decimal notation, net id's vs host id's
    IP protocol
    	unreliable datagrams
    packets
    TCP protocol
    	reliable streams
    higher-level protocols: SSH, SMTP, HTTP
    	layering, encapsulation
    bandwidth
    	communications technologies
    Web
    	url, http, html, browsers
    	client-server
    	forms and cgi programs
    risks
    	cookies, spam
    	viruses, spyware
    	active content, Javascript, Java, ActiveX
    	attacks on clients, servers, networks
    		denial of service
    	defenses
    cryptography
    	history
    	secret key crypto: DES, AES
    	public key crypto, digital signatures
    	how clients & servers do key exchange
    intellectual property
    	patents & copyright
    	DMCA, test cases
    	net neutrality
    compression
    	lossless LZ
    	lossy JPEG, MPEG, MP3
    error detection & correction
    	checksums, parity
    peer to peer networks
    	torrents
    wireless systems
    	cell phones; other radio devices
    search engines
    legal, economic and political issues for communications and case studies