10/5/07
Lecture 14. Boolean functions and Boolean expressions concluded;
gates and circuits begun.
Boolean bases: {AND, OR, NOT}, also {AND, NOT} and {OR, NOT},
(but not {AND, OR}.)
Single gate bases: {NAND} and {NOR}.

Gates and circuits:
a model of computation of Boolean functions.
Basic gates: AND, OR, NOT, XOR, NAND, NOR and circuits
constructed of them.
Combinational circuits have no "loops" of wires;
computing the outputs given certain inputs.

10/8/07
Lecture 15. Gates and circuits, continued.
We designed a simple circuit to sound an alarm
(in an auto) if the key is in the ignition and the door
is open, or the key is in the ignition and the seat belt is not
fastened.

We also considered the task of designing a circuit to
compute z, where z = 1 if and only if x1 = y1 and x2 = y2 and
x3 = y3 and x4 = y4.
Gate delays and faster and slower circuits for this.

As another example of designing a circuit, we considered the
problem of binary addition of two n-bit quantities to find an (n+1)-bit
sum.

10/10/07
Lecture 16. Gates and circuits, continued.
We continued and completed our design of a 4-bit binary addition
circuit taking two 4-bit numbers (x3,x2,x1,x0) and (y3,y2,y1,y0)
to their sum (z4,z3,z2,z1,z0).

10/12/07
Lecture 17. Gates and circuits, continued.
Circuits with feedback loops:
the design of an RS-latch using two cross-coupled NOR gates,
capable of storing one bit.
A D-flipflop stores
one bit and has an enable signal.

10/15/07
Lecture 18. Memory.
The D-flipflop, registers, a random access memory.

10/17/07
(No Lecture: Exam 1.)

10/19/07
Lecture 19. Architecture of the TC-201.
A summary of the TC-201 architecture and instructions
is available on the course web page.
Von Neumann (stored-program)architecture.
The fetch-decode-execute cycle described at the register-transfer level.
The ACC, PC, MAR, MDR, and IR.

10/22/07
Lecture 20. The TC-201 continued.
We continued on the architecture and instructions of the TC-201,
first writing and simulating a program at the machine language
level, and then moving up to the assembly-language level.
Description of a simple two-pass assembler.

10/24/07
Lecture 21. The TC-201 continued.
We wrote a self-modifying (!) program to read in a zero-terminated
sequence of numbers and store them in consecutive memory locations.
We then rewrote the program using the new instructions: loadi (load indirect)
and storei (store indirect).

10/26/07
Lecture 22. The TC-201 concluded; start of regular expressions.
Further explanation of loadi (load indirect) and storei (store indirect).
Procedures read, display and newline, and their use in implementing
the read and write instructions of the TC-201.
A sample procedure to read in a number, print it out, and return its value:

Three possibilities for computer arithmetic when we want positive, zero
and negative numbers: (1) sign/magnitude (this the the choice in the
TC-201 this year), (2) two's complement (this is typical for real machines)
(3) one's complement (less typical, but has been used.)

Example of the use of the unix utility egrep and regular expressions
to search for occurrences of caar, cadr, cdar, cddr, caaar, etc.
in a set of files.

10/29/07
Lecture 23. Regular expressions and finite state machines.
Recursive definition of the syntax of regular expressions
and the languages they denote.

10/31/07
Lecture 24. Regular expressions and finite state machines.
Definition and examples of finite state machines.
A language is accepted by a finite state machine if and only
if it is denoted by a regular expression.

11/2/07
Lecture 25. Context-free grammars and languages.
Definitions and examples of context-free grammars
and languages.

11/5/07
Lecture 26. Context-free grammars and programming languages.
We wrote a context-free grammar for
the set of all strings over the alphabet {a, b} that contain
an equal number of a's and b's.

In computer science, one practical use of context free grammars
is in specifying the syntax of programming languages.
The notation called "Backus Naur Form" (or BNF) is an alternate
notation for specifying context free languages.
We looked in some detail at the BNF specification of the programming
language Pascal.

11/7/07
Lecture 27. Compilers.
We considered two computational problems related to
context free grammars and languages: the parsing problem
and the equivalence problem.
Compiling: the lexical analysis phase (which breaks up the input
string of characters into tokens, for example, numbers, variables,
keywords, symbols), the syntactic analysis phase (which parses the
stream of tokens into a parse tree) and the semantic analysis phase
(which "decorates" the parse tree with semantic information, for
example, types and values), the optimization phase and the code
generation phase.

We also considered the problem of testing a context-free grammar
for ambiguity.

11/9/07
Lecture 28. Compilers, continued.
We considered the problem of translating a parse tree into
an assembly-language program, by recursion on the structure
of the tree.
Homework #7 gives a grammar for the tiny higher level
language THL.

11/12/07
Lecture 29. Mutators, environments, objects, counters, and stacks.
We looked at the mutator set! and how it may be used in conjunction with the
behavior of Scheme environments, procedure values and procedure calls
to implement objects such as counters and stacks.

11/14/07
Lecture 30. Mutators and queues.
The mutators set-car! and set-cdr! change the car field of a cons
cell and the cdr field of a cons cell, respectively.
Implementation of a queue data structure using set-car! and set-cdr!

11/16/07
Lecture 31. Depth-first search and breadth-first search of trees using
stacks and queues.
We considered the task of visiting the nodes of a rooted, ordered binary
tree in depth-first order using stacks (both the implicit stack of
procedure calls in Scheme and an explicit stack data structure) and
in breadth-first order using a queue.

We defined a tree data structure to represent rooted ordered binary
trees, constructors: empty-tree, make-tree; predicates and selectors:
empty-tree?, root-label, left-subtree, right-subtree.
And considered depth-first and breadth-first searches of such trees.

11/26/07
Lecture 32. Circular lists; Searching a table.
The mutators set-car! and set-cdr! give us the ability
to construct relatively arbitrary data structures with pointers.
Example of creating a circular list.
Testing whether two variables point to the same cons cell with eqv? and eq?

Searching for a value in a table of n elements.
Linear search: Theta(n)
Binary search, when the elements of the table are sorted: Theta(log n).
Hashing gives a practical method with expected constant time lookup: Theta(1).
For these methods, Scheme's vector type gives constant time access
to an element of an array, given the numeric index of the element.
Another data structure is a binary search tree: Theta(d), where
d is the depth of the tree.  If the tree is balanced, d is Theta(log n).

Lecture 33. Sorting, Analysis of Algorithms.
Definition of the sorting problem: sort a list of numbers into nondecreasing
order.
Insertion sort: the procedure (insert item ls) inserts an item into
an already-sorted list.
At most n comparisons suffice to insert an item into a list of length n.
Its time is O(n).
Insertion sort repeatedly uses insert to insert the next element into
the sorted list of elements so far.
Scheme implementation: isort.
In the worst case, it uses n(n-1)/2 comparisons to sort a list of length n.
Its worst-case running time is Theta(n^2).

Every algorithm that sorts using pairwise comparisons must
use at least Omega(n log n) comparisons in the worst case.
The information theoretic lower bound uses decision trees whose
internal nodes are comparisons.

Big-Oh, big-Omega, and big-Theta are used to express upper, lower
and upper/lower bounds up to constant factors.

11/30/07
Lecture 34. Sorting, Analysis of Algorithms, Recursion and Memoization.
The procedure merge to merge two sorted lists.
Bound of m+n-1 on the number of comparisons to merge lists of lengths m and n.
A Scheme implementation of merge sort.
Argument that it uses O(n log n) comparisons.

Memoization is the idea of saving argument/value pairs of a procedure
to avoid repeatedly recomputing them by looking them up.
Example of the Fibonacci numbers: (1.618)^n to O(n) procedure calls.
Dynamic programming can be thought of as building the table "bottom up".