CIS 321: Design and Analysis of Component-Based Software


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.

Course Objectives

Relationship to ABET Criterion 3 Relationship to CSE Program Objectives
a b c d e f g h i j k
1a 1b 1c 2a 2b 3a 3b 3c 4a 4b

Textbooks and Other Required Material


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.