Active Outline

General Information

Course ID (CB01A and CB01B)
CIS D022C
Course Title (CB02)
Data Abstraction and Structures
Course Credit Status
Credit - Degree Applicable
Effective Term
Fall 2023
Course Description
Application of software engineering techniques to the design and development of large programs, including a team project, with an emphasis on data abstraction and structures and associated algorithms: stacks, queues, linked lists, trees, graphs, and hash tables. This course also covers recursion and advanced sorting algorithms.
Faculty Requirements
Course Family
Not Applicable

Course Justification

This course is a major preparation requirement in the discipline of Computer Science for at least one CSU or UC and it is CSU and UC transferable. This course belongs on the Network Programming A.A. degree. The course is compliant with the standards of the Association for Computing Machinery and is part of the core curriculum for all Engineering and computer science students.

Foothill Equivalency

Does the course have a Foothill equivalent?
No
Foothill Course ID

Course Philosophy

Formerly Statement

Course Development Options

Basic Skill Status (CB08)
Course is not a basic skills course.
Grade Options
  • Letter Grade
  • Pass/No Pass
Repeat Limit
0

Transferability & Gen. Ed. Options

Transferability
Transferable to both UC and CSU
C-IDArea(s)StatusDetails
COMPComputer ScienceApproved(CIS D022C or CIS D22CH) & (CIS D022B or CIS D22BH or CIS D035A or CIS D036B) required for C-ID COMP 132

Units and Hours

Summary

Minimum Credit Units
4.5
Maximum Credit Units
4.5

Weekly Student Hours

TypeIn ClassOut of Class
Lecture Hours4.08.0
Laboratory Hours1.50.0

Course Student Hours

Course Duration (Weeks)
12.0
Hours per unit divisor
36.0
Course In-Class (Contact) Hours
Lecture
48.0
Laboratory
18.0
Total
66.0
Course Out-of-Class Hours
Lecture
96.0
Laboratory
0.0
NA
0.0
Total
96.0

Prerequisite(s)

CIS D022B, CIS D22BH, CIS D035A or CIS D036B

Corequisite(s)

Advisory(ies)

Elementary algebra or equivalent (or higher), or appropriate placement beyond elementary algebra

Limitation(s) on Enrollment

(Not open to students with credit in the Honors Program related course.)

Entrance Skill(s)

General Course Statement(s)

Methods of Instruction

Lecture and visual aids

Discussion of assigned reading

Discussion and problem solving performed in class

Quiz and examination review performed in class

Homework and extended projects

Collaborative learning and small group exercises

Collaborative projects

Laboratory discussion sessions

Assignments

  1. Required reading from the text
  2. Programs: 5-8 individual programming assignments implemented in C++ or Java which include design as well as coding, debugging, and testing, covering the Lab Topics specified in X. below.
  3. Team Project: Design and development of a large program with three or more programmer-written files.

Methods of Evaluation

  1. Successful completion of programming assignments with output verifying program correctness; use of structured design principles, documentation, programming style, efficiency, and testing methods.
  2. Evaluation of the team project for correctness, use of structured design principles, documentation, programming style, and efficiency.
  3. One or more examinations requiring some algorithm development. Evaluation based on correctness.
  4. A comprehensive final examination requiring some algorithm development

Essential Student Materials/Essential College Facilities

Essential Student Materials
  • None.
Essential College Facilities
  • Access to a computer laboratory with Java and C++ programming environments available

Examples of Primary Texts and References

AuthorTitlePublisherDate/EditionISBN
Carrano, Frank M.Data Structures and Abstractions with JavaPearson2019/5th Edition978-0-134-87266-7
Carrano, Frank M.Data Structures & Problem Solving with C++Pearson2017/7th Edition978-0-134-47840-1
zyBooksData Abstraction and StructuresWiley2022979-8-203-96644-5

Examples of Supporting Texts and References

None.

Learning Outcomes and Objectives

Course Objectives

  • Create programs which implement the stack data structure.
  • Create programs which implement the queue data structure.
  • Create programs which implement complex linear lists.
  • Create recursive algorithms and relate efficiency to uses of recursion.
  • Create programs which implement the binary tree, binary search tree, AVL tree, priority queues, and binary heaps data structures.
  • Create programs which implement hashed tables.
  • Demonstrate knowledge of advanced sorting algorithms and discuss the usage and relative advantages of various sorts and their efficiency.
  • Demonstrate knowledge of external sorting algorithms.
  • Create programs which implement the graph data structure.
  • Apply software engineering principles including structured programming, object-oriented programming, and abstract data types.
  • Design and implement a team project with multiple classes in multiple files.
  • Demonstrate usage of templates/generics.

CSLOs

  • Read, analyze and explain data structures programs.

  • Create and analyze efficiency of data structures algorithms, code, document, debug, and test large data structures programs using appropriate design methodology incorporating advanced programming concepts.

Outline

  1. Create programs which implement the stack data structure.
    1. Implementation by linked lists.
    2. Applications
  2. Create programs which implement the queue data structure.
    1. Implementation by linked lists.
    2. Applications
  3. Create programs which implement complex linear lists.
    1. Rings
    2. Doubly linked lists
    3. Multilists
  4. Create recursive algorithms and relate efficiency to uses of recursion.
    1. The concept of recursion
    2. Recursive mathematical functions
    3. Simple recursive algorithms
    4. Divide-and-Conquer strategies
    5. Recursive backtracking
    6. Implementation of recursion using stacks
  5. Create programs which implement the binary tree, binary search tree, AVL tree, priority queues, and binary heaps data structures.
    1. General trees
    2. Binary trees
    3. Binary search trees
    4. AVL trees
    5. Applications
    6. Binary heaps
    7. Priority Queues
  6. Create programs which implement hashed tables.
    1. Hashing algorithms
    2. Clustering and collision resolution
    3. Selecting hash functions
  7. Demonstrate knowledge of advanced sorting algorithms and discuss the usage and relative advantages of various sorts and their efficiency.
    1. Shell Sort
    2. Heap Sort
    3. Quick Sort
  8. Demonstrate knowledge of external sorting algorithms.
    1. Merge
    2. Natural
    3. Balanced
    4. Polyphase
  9. Create programs which implement the graph data structure.
    1. Basic concepts
    2. Spanning trees
    3. Minimum path trees
    4. Depths first and breadth first traversals
  10. Apply software engineering principles including structured programming, object-oriented programming, and abstract data types.
    1. The abstract data type
    2. Cohesion and coupling
    3. Principles of object-oriented programming and structured programming
    4. Type parameters and parameterized types
    5. Modules in programming languages
    6. Strategies for choosing the right data structure
    7. Working in teams
  11. Design and implement a team project with multiple classes in multiple files.
    1. Organizing a multiple-file project
    2. Project building
  12. Demonstrate usage of templates/generics.
    1. Class templates
    2. Function templates

Lab Topics

  1. Design algorithms, code solutions, debug and test programs employing the stack ADT.
  2. Design algorithms, code solutions, debug and test programs employing the queue ADT.
  3. Design algorithms, code solutions, debug and test programs employing complex ADT linked list structures, such as doubly linked lists, multi-linked lists, circularly linked lists.
  4. Design recursive and/or iterative algorithms, code solutions, debug and test programs employing ADT binary trees, binary search trees, AVL trees, priority queues, or binary heaps.
  5. Design algorithms, code solutions, debug and test programs employing hashed tables.
  6. Analyze and compare simple and advanced sorting algorithms, such as Shell Sort, Insertion Sort, Heap Sort, Selection Sort, Quick Sort.
  7. Design algorithms, code solutions, debug and test programs employing graphs.
  8. Demonstrate the building and running of a large program with three or more programmer-written files.
Back to Top