CIS 083
Internal Data Structures and Algorithms
Course Syllabus

Spring, 1998

Frank Friedman
Wachman Hall 303

I. Prerequisite Skills:

 One course in C++ programming (CIS 067 or 081) or the equivalent.
  1. Introductory knowledge of the C++ programming language.
  2. Working knowledge of the basic ideas of procedural abstraction and elementary data abstraction and how to put these ideas to work in solving problems of moderate complexity.
  3. Ability to write small program components using decision and loop structures and nested structures.
  4. In-depth understanding of call-by-reference and call-by-value argument passing mechanisms.
  5. Ability to design and implement systems of small programs using collections of short functions having clean and concise interfaces.
  6. Considerable skill in the manipulation of arrays, structs, and arrays of structs, including elementary searching and sorting.
  7. An understanding of the basic elements of C++ stream input and output including the use of the standard streams and external files.
  8. Some knowledge of the very basic elements of pointer manipulation.
  9. Awareness of the importance of component reuse and of the contents of the C and C++ libraries available on your computer system.
  10. Knowledge of the basics of the Unix Operating System.

II. Catalog Description:

Program style, organization, and design with an emphasis on the use of abstract data types and the object-oriented program design paradigm in the construction of larger-scale programs. Choices and analysis of algorithms and data structures. Topics include program modularization techniques, an introduction to object-oriented programming, recursion, searching, sorting, string manipulation, linked lists, binary trees, and hash tables. Group work will be required.

III. Course Objectives:

In this course we examine a number of data structures and associated algorithms that are fundamental to the study of computer science. The analysis of the efficiency of algorithms is also discussed. Algorithm and data structure choices will be discussed and there will be a heavy emphasis on program modularization and the use of abstract data types and object-oriented design in writing good programs. Students will study examples of programs developed using abstract data types and the object-oriented approach, and will be expected to develop their own small to medium size programs as well.

The 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 one semester. Programs involving the use of data structures and algorithms and emphasizing software design approaches using abstract data types and object-oriented paradigms will be required. A half-dozen small prorgamming assignments and one to two larger group projects will be assigned.

IV. Required Texts:

Headington, M. R., and D. D. Riley, Data Abstraction and Structures using C++(D. C. Heath).

V. Other Reading:

The Friedman/Koffman and Savitch are books used in CIS 067 and 081, so you should already own one or the other. The other books should be on 2-hour /overnight reserve in the reserve section, basement level of the Paley Library. (If some are not yet there, please let me know, and be patient -- they may still be on order.) If you used a non-C++ text in CIS 081 you may want to buy either Savitch or Friedman/Koffman for reference.

***** BOOKS

VI. Course Outline: and Reading Summary (Yes I know it is 16 weeks)

  1. Review of C++ (1 week)
    1. Introduction to data types
      1. Primitive data types/standard primitive types
      2. Structured data -- arrays and structs
      3. User-defined data types at work -- streams, strings, and money
    2. Control structures
      1. Decision structures
      2. Repetition structures
    3. Functions
      1. Parameters (in, out, inout)
      2. Decomposition using functions
      3. tyle: function documentation
      4. Scope rules
      5. Local data (avoiding use of globals, an introduction)
    4. More on data types
    5. 5. Fundamentals of I/O
    6. Arrays and Structs Assigned Reading:
      Anything you need to read for review (things you cannot remember).
      H & R: Chapter 4 (4.1 - 4.4), Chapter 5 (5.1 - 5.3)
      Anthology: Sections 1 - 4.

      Note: You are expected to do this reading and come to class with questions. I don't expect to spend much class time on this material. I will be covering much of the Part B. material while you are reviewing C++.

      Exercises and Programming Problems (see also Section 4 in Anthology):
      Assignment Number 0: Robot Simulator / Palindrome Problem
      Assignment Number 1: Monopoly Simulation -- getting familiar with the game

  2. Procedural Abstraction, Top-Down Design, Modularization -- Software Components, Reuse (1 week)
    1. Course orientation -- introduction to data modeling and dynamic modeling
    2. Top down design and procedural abstraction
    3. Correctness -- assertions
    4. All about program components
    5. Maxmimizing the use of libraries
    6. A taste of data abstraction -- working with money, streams, and character strings

      Assigned Reading:
      H & R: Chapters 1 and 2.

      Exercises and Programming Problems:
      Assignment Number 2: Processing streams, strings and money
      Assignment Number 1: (continuation)

  3. Abstract Data Types, Classes, and the Object Oriented Paradigm (2 weeks)
    1. Introduction to abstract data types and abstraction-based approaches to program design
      1. Implementing ADTs without language help
      2. The concept of hidden (private) data
      3. The concept of public and private operations on hidden data
    2. Introduction to the C++ class feature
      1. Implementing ADTs with language help
      2. Definition vs implementation sections
      3. Private vs public data and functions
      4. Class documentation
    3. Object-oriented terminology and more on approaches to program design
      1. More on information hiding
      2. Methods (or messages) vs operations as applied to class data
    4. Constructors - a first visit
    5. Layered software
    6. Friends
    7. Operator overloading
      1. overloaded assignment
      2. overloaded arithmetic
      3. overloaded i/o

      Assigned Reading:
      H & R: Chapter 3, Chapter 10 (Sections 10.1 - 10.4)

      Exercises and Programming Problems:
      Assignment Number 3: Group Project: Interactive Dice Rolling with Arrays and Classes.
      Assignment Number 4: Fractions Problem

    FIRST EXAM (1/2 week)

  4. Pointers and Dynamic Data Structures (2 weeks)
    1. Introduction to pointers
    2. Dynamic data / dynamic memory -- allocation and deallocation
    3. Class constructors (default constructors; copy constructors)
    4. Dynamically sized arrays - collections of varying sizes
    5. Linked lists
      1. Traversals - search
      2. Insertion / deletion
    6. More complicated linked lists
      1. Doubly linked lists
      2. Circularly linked lists

      Assigned Reading:
      H & R: Chapters 7 and 8.

      Exercises and Programming Problems:
      Assignment Number 5:

      1. A linked list implementation of a stack
      2. A simple linear linked list manager with insertion, deletion, and search

  5. Template Classes: A First Project and Advanced Issues in C++, Part I (2 weeks)
    1. Template classes
      1. Collections of varying sizes of data elements of varying types
      2. Stack class template -- with elements of type T.
      3. Hash table -- multi-level hierarchy with unspecified table elements
    2. Overview of issues related to the analysis, design, and implementation of larger, more complex programs
      1. Analysis of a problem specification
      2. Software design issues
        • oriented-based system decomposition
        • information hiding; separation of concerns
        • design for reuse

      Assigned Reading:
      Friedman/Koffman, Chapter 12 (1st Edition -- Sections 12.1 through 12.3;
      Bergman and Bruckner: Chapters 1 - 4. OR, see selected pages in Anthology. OR 2nd Edition -- Chapter 12 (Sections 12.3 - 12.5) OR any other text that covers class templates
      Anthology: Parts 5 and 6.
      Any good UNIX manual (on-line or otherwise); separate compilation using the “make” utily

      Exercises and Programming Problems:
      Assignment Number 6: Assembler Project

  6. Recursion (2 weeks)
    1. Definitions and concepts
      1. Review: run-time stack analysis in terms of some simple problems such as Character-Integer Conversion, Factorial
      2. Common sense, surface analysis of recursion
      3. An in depth, detailed analysis of recursion
    2. Recursion as a natural means of expressing algorithms for solving certain kinds of problems
      1. Arithmetic expression evaluation
      2. Towers of Hanoi
    3. Backtracking techniques
      1. Eight queens problem
      2. Maze walk, Knight's tour problems
    4. Applications
      1. Polish notation
      2. Infix to Polish conversion
      3. Polish conversion to code

      Assigned Reading:
      H & R: Chapter 6.
      FK: Chapter 13 (or read any other intro text with covering recursion).
      Anthology: Part 7

      Exercises and Programming Problems:
      Assignment Number 7: Expression Evaluator

  7. Searching and Sorting (1.5 weeks)
    1. Introduction to Big-O notation and algorithm performance
    2. Searching algorithms
    3. Algorithm analysis for best, worst, and average cases
    4. Sorting
      1. Three simple (o(n2)) sorts: exchange, selection and insertion
      2. Three o(n´ log(n)) sorts: Shell sort, heapsort, and quicksort

      Assigned Reading:
      H & R: Chapter 12 (Sections 12.1 - 12.9).
      Anthology: Part 8

      Exercises and Programming Problems:
      Assignment Number 8: Comparative analysis of selected sort algorithms

    SECOND EXAM (1/2 week)
  8. Trees (1.5 weeks)
    1. Binary search trees
    2. Binary tree traversal
    3. Binary expression trees

      Assigned Reading:
      H & R: Chapter 13 (Sections 13.1 - 13.5).

      Exercises and Programming Problems:
      Assignment Number 9: Morse Code Problem

  9. The Object Oriented Paradigm -- Inheritance, Virtual Functions (2 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. Monopoly revisited:
      1. Three level hierarchy with specified table element structures
      2. Hierarchies of user defined types -- inheritance and specialization.
      3. Virtual functions - examples

      Assigned Reading:
      F/K: Appendix E.
      Anthology: Parts 9 and 10.

      Exercises and Programming Problems:
      Assignment Number 1 Revisited: GROUP PROJECT (3 to a group)
      Monopoly Game Simulation: (Described in class)

      Work on project expected to extend through the end of the semester (as much as time permits). 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.

    FINAL EXAM