Lectures, Handouts, and Readings
(For reading pdf files, you need Adobe
Acrobat, and for reading postscript files, you need ghostview)
September 24, 2002
Administrivia; Introduction to important concepts in computer science;
Example of anagram listing program
October 1, 2002
Structure of the Web graph; Discussion of the bowtie model; Introduction
to graphs;
Graph traversals
October 8, 2002
Navigating through a maze with pennies; Introduction to search engine
architectures;
Google's PageRank algorithm
October 15, 2002
Review of Quiz 1; Discussion of computer chess; Recursion and induction;
Fibonacci numbers, different definitions, correctness and efficiency
October 22, 2002
Two programs for computing the nth Fibonacci numbers; Comparison
of efficiency;
Plots to relate running times; Relation to golden ratio; Relative
and absolute notions
of efficiency; Factoring; Public Key Cryptosystem
October 29, 2002
Introduction to Cryptography; Private-key and public-key cryptosystems;
RSA cryptosystem
November 5, 2002
The RSA algorithm; Factoring and primality testing; Powering through
repeated squaring and
using the binary representation of the power; Notion of polynomial-time;
Size of problem
November 12, 2002
Review of Quiz 2 and Homework 5; Discussion on the notion of an interpreter;
Interpreter as a program;
A program as an interpreter of a language; Example applications;
Syntax and semantics of programming
languages;
November 19, 2002
Quiz 3; The Java virtual machine; Scanners and parsers; Abstract
syntax trees; Discussion of an interpreter
for an arithmetic expression language
November 26, 2002
Review of Quiz 3; Two software bug incidents: Microsoft & Beth
Israel Deaconnes; Virtual machines, stacks, heaps;
The buffer overrun problem; Automatic memory management; Garbage
collection
December 3, 2002
Discussion of Ken Thompson article; Proof of unsolvability of the
Halting Problem; Impossibility of the
distributed coordinated attack problem
December 17, 2002 (after classes)