Number of Weeks  Topic  Readings 
1.5 
Course introduction;
overview of programming project;
review of computingenvironment tools,
appropriate templates from CIS 222, BigO
notation, and program testing 
[W98] Chapter 7, [W98] various appendices 
1.5 
Sorting_Machine component;
implementations using
insertion sort, quicksort, mergesort, heapsort;
analysis of performance 
Handouts 
1.5 
Introduction to binary trees;
mathematical model for binary trees; specification of and
pointerbased implementation of
Binary_Tree component; time analysis of binary
tree operations; binary search trees and time analysis
of operations; binarysearchtree implementation of
Partial_Map 
[W98] Binary_Tree, Partial_Map 
1.5 
Introduction to formal models of expressions; specification
of software components for formal expressions; binarytree
based implementations of expression components;
operation capabilities for expression components.

Handouts 
2 
Introduction to contextfree grammars and contextfree
languages; sentential forms, derivations, derivation trees;
syntactic specification of expressions using contextfree
grammars; recursive descent parsing and
processing of expressions. 
Handouts 
1.5 
Introduction to lexical analysis; regular expressions
and regularexpression based
specifications of tokenizing; finiteautomata, relationship
to regular expressions, and finiteautomata based
implementations of tokenizing. 
Handouts 
0.5 
Review and exams 
