# Data & Control Structures

Faculty
Department
Computing Studies & Information Systems
Course Code
CSIS 2475
Credits
3.00
Semester Length
15 Weeks X 4 Hours per Week = 60 Hours
Max Class Size
35
Method Of Instruction
Lecture
Lab
Seminar
Typically Offered
To be determined

## Overview

Course Description
This course focuses on dynamically allocated structures such as lists, hash tables, stacks, queues, trees, and graphs. The time and space complexity of algorithms is considered throughout. Programs are written in C++.
Course Content
1. Review classes, information hiding, composition, inheritance, polymorphism
2. Analysis of algorithms (best case, worst case, average case)
• Search algorithms – hashing, sequential and binary search
• Sort algorithms – bubble, selection, linear insertion, binary insertion, mergesort, quicksort
3. Dynamic data structures
• Linear structures – lists, stacks, queues
• Trees
• Binary trees
• Recursive algorithms for tree traversals
• Iterative algorithms for searching a tree (depth-first using a stack, breadth-first using a queue, and heuristic using a priority queue)
• Binary search treesExpression trees
• Tree sort
• Heaps
• Heap sort
• Priority queue
• Tree
• Huffman codes
• Graphs
Methods Of Instruction

Lecture, seminar, laboratory assignments, reading, and research

Means of Assessment
 Attendance and Participation 0% - 5% Assignments (Minimum: 4) 40% - 50% Tests (Minimum: 1) 15% - 50% Final Examination 25% - 40% Total 100%
Learning Outcomes

The student will be able to:

1. explain the concepts of dynamic versus static data structures;
2. explain the concepts of asymptotic behaviour of algorithms.

The student should be able to:

1. analyze the time and space complexity of iterative and recursive algorithms;
2. choose the most appropriate abstract data structure and be able to implement it efficiently.
Textbook Materials

Textbooks and Materials to be Purchased by Students

Malik, D.S. C++ Programming; Program Design including Data Structures. Latest edition. Course Technology.

## Requisites

### Prerequisites

CSIS2375 or CISY1275 or CMPT1110

Note: MATH1130 is recommended as a prerequisite or corequisite

### Corequisites

No corequisite courses.

### Equivalencies

No equivalent courses.

### Requisite for

This course is not required for any other course.

## Course Guidelines

Course Guidelines for previous years are viewable by selecting the version desired. If you took this course and do not see a listing for the starting semester / year of the course, consider the previous version as the applicable version.

## Course Transfers

Institution Transfer Details Effective Dates
Kwantlen Polytechnic University (KPU) KPU CISY 2315 (3) 2008/01/01 to -
Langara College (LANG) LANG CPSC 2150 (3) 2012/01/01 to -
Simon Fraser University (SFU) SFU CMPT 102 (3), Q 2008/01/01 to -
Thompson Rivers University (TRU) TRU COMP 2230 (3) 2010/09/01 to -
Thompson Rivers University (TRU) TRU COMP 223 (3) 2008/01/01 to 2010/08/31
University of British Columbia - Okanagan (UBCO) UBCO COSC 2nd (3), Exempt UBCO COSC 222 (3) 2008/01/01 to -
University of British Columbia - Vancouver (UBCV) UBCV CPSC 2nd (3) 2008/01/01 to -
University of the Fraser Valley (UFV) UFV COMP 251 (4) 2008/01/01 to -
University of Victoria (UVIC) UVIC CSC 225 (1.5) 2008/01/01 to -

## Course Offerings

### Fall 2020

There aren't any scheduled upcoming offerings for this course.