Number of Weeks | Topic | Readings |
1.5 |
Course introduction;
overview of programming project;
review of computing-environment tools,
appropriate templates from CIS 222, Big-O
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
pointer-based implementation of
Binary_Tree component; time analysis of binary
tree operations; binary search trees and time analysis
of operations; binary-search-tree implementation of
Partial_Map |
[W98] Binary_Tree, Partial_Map |
1.5 |
Introduction to formal models of expressions; specification
of software components for formal expressions; binary-tree
based implementations of expression components;
operation capabilities for expression components.
|
Handouts |
2 |
Introduction to context-free grammars and context-free
languages; sentential forms, derivations, derivation trees;
syntactic specification of expressions using context-free
grammars; recursive descent parsing and
processing of expressions. |
Handouts |
1.5 |
Introduction to lexical analysis; regular expressions
and regular-expression based
specifications of tokenizing; finite-automata, relationship
to regular expressions, and finite-automata based
implementations of tokenizing. |
Handouts |
0.5 |
Review and exams |
|
Week | Lab Topic |
2 |
Implement Sorting_Machine component using heapsort |
3 |
Implement Atomic_Query and Query_Expression components |
4 |
Implement Assertion_And_Query_Machine component (1st version) |
5 |
Implement Parsing and Get_From for Query_Expression component |
6 |
Processing atomic queries; implement Make_Instantiated_Copy |
7 |
Processing general queries; implement Union for Set component |
8 |
Implement Partial_Map over Binary_Tree |
9-10 |
Implement Binary_Tree using "raw C++" pointers |