I. Prerequisite Skills:

1. Two courses in C++ programming skills (CIS 67, and 68) or the equivalent. In particular:
   1. Working knowledge of the C++ programming language.
   2. Working knowledge of the basic ideas of procedural and data abstraction and how to put these ideas to work in solving problems of moderate complexity.
   3. Ability to use and implement simple user-defined data types using classes.
   4. Ability to design small programs using an object-oriented approach.
   5. Some skill in the manipulation of basic data structures -- arrays, linked lists (stacks and queues), trees -- construction, adding, deleting, modifying, searching, sorting, etc.
   6. Some experience in character manipulation: conversion of internal modes of data representation, etc.
   7. Introductory backgound in solving problems using recursion.
   8. Introductory understanding of the run-time support mechanism for Pascal or C: run-time stack, heap, etc

2. One semester of assembly language programming (CIS 072 or the equivalent), especially: the basic concepts of one and two-pass assemblers.

3. At least one semester (preferably two) of discrete math, such as CIS 66, MATH 141, or equivalent

II. Catalog Description:

III. Course Objectives:

The principle programming language of implementation is C++. For the most part, C++ will be introduced by example, as it is anticipated that students will have already been programming in C++ (for at least two semesters). Programs involving the use of data structures and algorithms and emphasiz-ing software design approaches using abstract data types and object-oriented paradigms will be required. At least two group projects will be assigned.

This is a University Writing Course. Students will be asked to produce written, coherent program documentation and may be asked to write 3 to 4 short papers and/or group project progress reports. Grades on all written work will be based both on technical content and quality of presentation.

IV. Texts:

• Carrano, Frank M., Data Abstraction and Problem Solving with C++: Walls and Mirrors, Benjamin-Cummings. (Primary Text)
• CIS 223, Anthology of Readings and Examples, Spring, 1996 (purchase from Sixth Floor Copy Center, Conwell Hall).

V. Other Reading:

***** BOOKS *****

• Bergman, S. and S. Bruckner, Introduction to Computers and Computer Programming (Addison-Wesley)
• Friedman, F., and Koffman, E., Problem Solving, Abstraction, and Design using C++, Addison-Wesley (FIRST EDITION).
• Headington, M. R., and D. D. Riley, Data Abstraction and Structures using C++ (D. C. Heath).
• Kernighan, B. W. and D. M. Ritchie, The C Programming Language, Second Edition (Prentice-Hall)
• Knuth, D., The Art of Computer Programming, Vol.I (A-W)
• Wirth, N., Algorithms + Data Structures = Programs (Prentice- Hall) NOTE: The Pascal version of this book is preferred to the newer Modula-2 version. (This book is NOT on reserve)

VI. Course Outline: and Reading Summary

Programming, Software Engineering, C++ Classes (1 week)

• 0. Course orientation -- emphasis on data and dynamic modeling of problem domain spaces
• 1. Problem solving and software engineering
• 2. Modular and object-oriented design
• 3. Key issues for programmers
• 4. More on data types
• 5. Introduction to abstract data types and abstraction-based approaches to program design
  1. Specification of ADTs
  2. Hidden (private) data
  3. Public and private operations on hidden data
• 6. Implementation of ADTs -- classes
  1. Definition vs implementation sections
  2. Private vs public data and functions
  3. Class documentation

Assigned Reading:

• Carrano: Preface, Chapters 1 and 3; Appendixes A-C.
• Anthology: Secs. 1-2, 3 (if needed)and 4.
• Web information on the Robot Simulator

Exercises and Programming Problems:

• Assignment Number 0: Robot Simulator and Palindrome Problems
• Assignment Number 1: Dice Simulation Problem

Review of Some Key Issues in using C++ (1.5 weeks)

• 1. Constructors (default constructors; copy constructors)
• 2. Dynamic memory allocation; dynamically sized arrays
• 3. Destructors
• 4. Templates
  1. Case Study 1: Stack class template -- with elements of type T.
  2. Case Study 2: Hash table -- multi-level hierarchy with unspecified table element structures. In depth look at structures
• 5. Overloaded operators
  1. overloaded assignment
  2. overloaded arithmetic
  3. overloaded i/o
• 6. Collections of varying sizes of data elements of varying types

Assigned Reading:

• Carrano: Chapter 6 (pp. 248 - 269), Chapter 7 (pp. 306-324)
• Headington and Riley, Chapter 7 (7.5 through 7.8)
• Friedman/Koffman, Chapter 12 (Sections 12.1 through 12.3)
• Anthology: Secs. 1-2, 3 (if needed)and 4.
• Web information on the Robot Simulator

Exercises and Programming Problems:

• Assignment Number 2: Money and Fractions
• Assignment Number 3: Data Collections

Covering the Basics of C -- argument passing and input/output (2.5 weeks -- including lectures on the Assembler)

• 1. Argument passing in C
• 2. Fundamentals of I/O in C
• 3. Introduction to the first project -- Assignment 7A: Assembler
• 4. Hashing
  1. Choice of function
  2. Aproaches to handling collisions

Assigned Reading:

• Carrano: Chapter 12 (pp. 591-608 on Hashing ONLY)
• Headington/Riley and/or Friedman/Koffman - review material on templates
• Any good UNIX manual (on-line or otherwise); separate compilation using the “make” utility
• Kernighan and Ritchie: Chapters 1 (Secs. 1.1 - 1.6) and Chapters 2-7 (light reading), 8 (scan it so that you know what is there), Appendix B (B.1-B.5 only), pp. 114-116; 160- 162. FEEL FREE TO SUBSTITUTE ANY OTHER GOOD BOOK ON C -- BE SURE TO READ ABOUT C I/O AND ARGUMENT PASSING IN C.
• Anthology: Sections 5 and 6.

Exercises and Programming Problems (Part B):

• Assignment Number 4: Quick Sort Problem
• Assignment Number 5: (Group Project 1)

***** FIRST EXAM (1/2 week) *****

Recursion (2 weeks)

• 1. Recursive solutions
  1. Computing, counting, and searching for things
     • Review: run-time stack analysis in terms of some simple problems such as Character-Integer Conversion, Factorial
     • Common sense, surface analysis of recursion
     • An in depth, detailed analysis of recursion
  2. Doing things
     • Towers of Hanoi
• 2. Applications: recursion as a natural means of expressing algorithms for solving certain kinds of problems
  1. Backtracking techniques
     • Eight queens problem
     • Maze walk, Knight's tour problems
     • Methods ("operations") on stacks and queues
  2. Defining languages
     • Evaluating postfix expressions
     • Converting infix expressions to postfix
     • Arithmetic expression evaluation from syntax diagrams
• 3. Recursion and Mathematical induction

Assigned Reading:

• Carrano: Chapters 2 and 5.
• Friedman/Koffman, Chapter 15 (review)
• Anthology: Sec. 9

Exercises and Programming Problems:

• Assignment Number 5: (continued - due at the end of this section)
• Assignment Number 6: Towers of Hanoi (hand trace)
• Assignment Number 7: Expression Evaluator

The Object Oriented Paradigm -- Inheritance, Virtual Functions (2.5 weeks)

• 1. Inheritance - membership categories of a class
  1. Hierarchies of user defined types
  2. Subclassing for specialization and for specification
• 2. Types of inheritance - public, private, protected
• 3. Is-a, Has-a, and As-a relationships
• 4. Virtual functions and late binding
• 5. An introduction to the Project (Monopoly)
  1. Case Study 3: Three level hierarchy with specified table element structures; virtual functions -- spaces on the monopoly board.

Assigned Reading:

• Carrano: Chapter 8
• Friedman/Koffman: Chapter 11 (Section 11.5); Appendix E
• Anthology: Sec. 8 and 10

Exercises and Programming Problems:

• Assignment Number 8: Monopoly Simulation (Group Project 2) Work on project expected to extend through the end of the semester. Much of the problem analysis and software system design will be done in class. Groups will be responsible for completing and documenting the analysis and design work and for the implementation, component and integration testing of the software.

***** SECOND EXAM (1/2 week) *****

Dynamic Data Structures -- Lists (1 week)

• 1. In depth look at dynamic data structures - allocation/deallocation of memory
• 2. Programming with linked lists
• 3. Variations of the linked list -- circular and doubly linked lists
• 4. Stacks and applications
• 5. Queues and applications

Assigned Reading:

• Carrano: Chapters 4, 6 (finish it), and 7 (finish it)
• Friedman/Koffman: Chapter 16, Secs. 1-3

Exercises and Programming Problems:

• Assignment Number 9

Searching and Sorting with an object-oriented flavor (1.5 weeks)

• 1. Measuring the efficiency of algorithms
• 2. Searches
  1. Linear search
  2. Heuristics for improving linear search
  3. Binary search
• 3. Sorting
  1. Review straight sort techniques: Insertion, Selection, and Exchange
  2. Improvements on straight methods: Shell Sort, Quick Sort, Heap Sort
  3. External Sorts

Assigned Reading:

• FK: Chapter 9 (Sec. 9.5)
• Carrano: Chapter 9.
• Anthology: Sec. 7.
• Wirth, Chapter 2 (optional)

Exercises and Programming Problems:

• Assignment Number 10

More on Dynamic Data Structures -- Trees (2 weeks)

• 1. Multi-linked structures - lists and binary trees
  1. Basic concepts review
  2. Binary trees: representation and operations
  3. Binary search trees: Tree balancing
• 2. The concept of a table ADT
  1. Sorted array implementation of a table
  2. Binary search tree implementation of a table
  3. Priority queues and heaps
  4. Balanced search trees
  5. AVL trees

Assigned Reading:

• Carrano: Chapters 10-12 (omit section in Chapter 12 on Hashing)

Exercises and Programming Problems:

• Assignment Number 11: (to be decided)

Graphs (if any time remains)

• 1. Terminology
• 2. Traversals
• 3. Applications

Assigned Reading:

• Carrano: Chapter 13

Exercises and Programming Problems: (none)

***** FINAL EXAM *****

Return to Previous Page