Wed Dec 16 10:29:14 EST 2009
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:
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, exa, ... 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 how it works, but NOT detailed syntax 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 who is responsible for what services 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, secure hashing 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