Dec 09, 2023
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
Course Learning Outcomes
- Implement and manipulate defined composite data types and structures, classes.
- 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.
- Describe and code various sort and search algorithms.
- 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.
- Describe and code various complex algorithms with memory management components, classes, and pointers.
- Code a breadth first and depth first algorithm.
- Use, create, and extend templates.
- Read/write to multiple file handles and streams in a program.
- Use a source control system such as GitHub to manage source code.
- Software Engineering Concepts and Theory
- Review of C++
- Classes, types and declarations
- Control flow statements
- Pointers – single and multi-level indirection
- Functions – including function pointers
- Inheritance, overloading
- Abstract classes
- Streams and file handles.
- Stacks and Queues
- Add an element to a stack or queue
- Delete an element from a stack or queue
- Use a circular array to simulate a stack or queue
- Simulate a stack or queue using a linked list
- Stack overflow
- Divide and conquer
- Removal of
- Dynamic Abstract Data Structures
- Linked lists– singly and doubly listed
- Binary search trees
- AVL trees (balanced)
- Sort and Search Algorithms
- Quick sort
- Merge sort
- Heap sort
- Radix sort
- Hash tables
- Introduction to Big O notation and analysis
- Memory Management
- Destructor calling order
- Memory leaks
- Garbage collection
- Hash Tables
- Hash functions
- Types of hash tables
- Addressing schemes
- Analysis of complexity
- Creating a template
- Extending an existing template
- Graphs, Trees and Networks
- Adjacency matrix
- Depth-first and breadth-first search
- Shortest path algorithm
Add to Portfolio (opens a new window)