Jul 24, 2024  
2023-2024 College Catalog 
    
2023-2024 College Catalog [ARCHIVED CATALOG]

CIS 269 - Data Structures

4 Credits, 4 Contact Hours
4 lecture periods 0 lab periods

Advanced topics in computer science and programming in C> Includes software engineering concepts and theory, memory management, inheritance, overloading, abstract classes, review of C< stacks, queues, recursion, and dynamic abstract data structures. Also includes source control, templates, hash tables, sort and search algorithms, file handling and streams, trees, graphs and networks.

Prerequisite(s): CIS 131  and CIS 278 .
Gen-Ed: Meets AGEC Options requirement; Meets CTE - Options requirement



Button linking to AZ Transfer course equivalency guide  

Course Learning Outcomes
  1. Implement and manipulate defined composite data types and structures, classes.
  2. Design, develop, modularize, test, validate, and document program solutions to business and scientific information processing problems using top-down design, data structure, and file handling tools.
  3. Describe and code various sort and search algorithms. 
  4. Execute performance analysis and determine relative timing complexity (Bit Oh Notation) relating to the sort and search algorithms, discuss advantages and disadvantages of the above. 
  5. Describe and code various complex algorithms with memory management components, classes, and pointers.
  6. Code a breadth first and depth first algorithm.
  7. Use, create, and extend templates.
  8. Read/write to multiple file handles and streams in a program.
  9. Use a source control system such as GitHub to manage source code.

Outline:
  1. Software Engineering Concepts and Theory
  2. Review of C++    
    1. Classes, types and declarations
    2. Operators
    3. Control flow statements
    4. Pointers – single and multi-level indirection
    5. Functions – including function pointers
    6. Inheritance, overloading
    7. Abstract classes
    8. Streams and file handles.   
  3. Stacks and Queues    
    1. Add an element to a stack or queue
    2. Delete an element from a stack or queue
    3. Use a circular array to simulate a stack or queue
    4. Simulate a stack or queue using a linked list
    5. Stack overflow   
  4. Recursion    
    1. Divide and conquer
    2. Backtracking
    3. Removal of
  5. Dynamic Abstract Data Structures    
    1. Linked lists– singly and doubly listed
    2. Trees        
      1. Binary
      2. Binary search trees
      3. AVL trees (balanced)   
  6. Sort and Search Algorithms    
    1. Quick sort
    2. Merge sort
    3. Heap sort
    4. Radix sort
    5. Hash tables
    6. Introduction to Big O notation and analysis
  7. Memory Management    
    1. Destructor calling order
    2. Memory leaks
    3. Garbage collection
  8. Hash Tables    
    1. Hash functions
    2. Types of hash tables
    3. Addressing schemes
    4. Analysis of complexity   
  9. Templates    
    1. Creating a template
    2. Extending an existing template   
  10. Graphs, Trees and Networks    
    1. Adjacency matrix
    2. Depth-first and breadth-first search
    3. Shortest path algorithm   


Effective Term:
Fall 2023