CIS 321: Design and Analysis of Component-Based Software

Description

Binary tree components and binary search trees; context-free grammars; regular expressions; parsing and tokenizing components; formal expression components; sorting components and sorting algorithms.

Level, Credits, Class Time Distribution, Prerequisites

Level	Credits	Class Time Distribution	Prerequisites
U	4	Three one-hour lectures, one one-hour lab	CIS 222 and a minimum CPHR of 2.00. Prereq or concur: Math 366

Quarters Offered, General Information, Exclusions, Cross-Listings, etc.

Au, Wi, Sp, Su
C++ is used.

Course Objectives

Master using the computing environment to complete programming projects and to communicate electronically;
Master using RESOLVE/C++ class templates and classes, and related RESOLVE/C++ principles for clients and implementers, to build new components with layered data representations;
Master writing programs using dynamic storage and pointers to create "raw C++" data representations;
Master using simple techniques to test implementations of class templates including developing and carrying out simple specification-based and code-based test plans;
Master using simple techniques to debug implementations of class templates;
Master using Binary_Tree template as a client and as an implementer;
Be familiar with using layering of software components to implement a large programming project;
Be familiar with using conventions ("representation invariants") and correspondences ("abstraction relations") to reason about layered data representations;
Be familiar with using the RESOLVE/C++ principles for interface designers to guide the choice of mathematical model and operation behavior of a new software component;
Be familiar with using formal models of expressions, and software components for formal expressions;
Be familiar with using context-free grammars and languages to specify syntax;
Be familiar with using recursive descent to process context-free languages;
Be familiar with using state-transition diagrams to tokenize languages;
Be familiar with using tokenizing software components and their implementations;
Be familiar with implementing insert, delete, and search algorithms for binary search trees;
Be familiar with using Sorting Machine template as a client and as an implementer;
Be familiar with important classical sorting algorithms as implementations of Sorting Machine template;
Be familiar with using basic algorithm analysis techniques and notations to analyze and express execution time;
Be familiar with working as part of a team to implement a large programming project.

Relationship to ABET Criterion 3

Relationship to CSE Program Objectives

a	b	c	d	e	f	g	h	i	j	k
XX	X	XX	XX	XX	X	X		X		XXX

1a	1b	1c	2a	2b	3a	3b	3c	4a	4b
XXX	XX	XXX		XX	X		X	X	X

Textbooks and Other Required Material

CIS 221 and CIS 222 Course Notes, a.k.a. Weide, B.W., Software Component Engineering, OSU Reprographics, 1999.
CIS 321 Course Notes, OSU Reprographics.

Topics

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

Representative Lab Assignments

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

Grading Plan

Midterm Exam	Final Exam	Homework Assignments	Closed Lab Assignments	Lab Assignments
20%	25%	11% (total of many)	8% (8 @ 1% each)	36% (8 @ 4.5%)

Important Note: A passing grade on the final exam is required in order to receive a passing grade for the course.

Preparer Information and Date: Syllabus prepared by Timothy J. Long, last modified 31 March 1999.