# Data and Control Structures

Faculty
Science & Technology
Department
Computing Science
Course Code
CMPT 1210
Credits
4.00
Semester Length
15
Max Class Size
Lecture 34, Laboratory 34
Method Of Instruction
Lecture
Lab
Typically Offered
To be determined

## Overview

Course Description
This course continues the study of Object Oriented Design (OOD) and Object Oriented Programming (OOP) with a study of inheritance and polymorphism. Other topics include an introduction to the analysis of algorithms, techniques for searching state spaces, and dynamic data structures including lists, stacks, queues, and trees. Programs are written in C++.
Course Content
1. Modules, information hiding and inheritance
2. Analysis of algorithms (best case, worst case, average case)

2.1.     Search algorithms – hashing, sequential and binary search

2.2.     Sort algorithms – bubble, selection, linear insertion, binary insertion, mergesort, quicksort

3. Dynamic data structures

3.1.     Linear structures – lists, stacks, queues

3.2.     Trees

3.2.1.1.  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 trees

Expression trees

Tree sort

3.2.1.2.  Heaps

Heap sort

Priority queue

Optional

• Trie
• Huffman codes
Methods Of Instruction

There are three components to the course: lectures, labs, and self directed learning (i.e. programming assignments)

The lecture is used to introduce new material, usually via a sequence of theoretical concepts and examples. The textbook is to be used as an additional source of  study material, problems, and examples.

The two-hour biweekly lab is exclusively used to evaluate the student’s practical programming ability.

Assignments are marked according to correctness of the algorithms, efficiency, and programming style.

Means of Assessment

Evaluation will be carried out in accordance with Douglas College policy. The instructor will present a written course outline with specific evaluation criteria at the beginning of semester. Evaluation will be based on some of the following:

labs (6 to 7)                                                          15% - 25%

assignments (4 to 6)                                           20% - 30%

tests (1 to 2) @15% - 30% each                      15% - 60%

final examination                                              25% - 40%

class participation1                                              0% - 5%

Note #1: participation includes (but is not limited to) short pop-quizzes and/or attendance

Learning Outcomes

Students should understand the concepts of

• Inheritance
• Dynamic versus static data structures
• Late/dynamic binding and polymorphism
• Asymptotic behavior of algorithms

Student should be able to

• Analyze the time complexity of iterative and recursive algorithms
• Use OOD on problems where inheritance is advantageous
• Choose the most appropriate abstract data structure and be able to implement it efficiently
Textbook Materials
• Malik, D.S., C++ Programming: Program Design Including Data Structures, Course Technology, Thomson Learning, ISBN 0-619-03569-2
• Portfolio for Programming Assignments
• Two 3 ½ “ high density diskettes

## Requisites

### Prerequisites

CMPT 1110 with a minimum grade of C

Note: MATH 1130 is highly recommended as a prerequisite

### 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
Coquitlam College (COQU) COQU CSCI 201 (4) 2004/09/01 to 2005/08/31
Kwantlen Polytechnic University (KPU) KPU CISY 2315 (3) 2004/09/01 to 2005/04/30
Simon Fraser University (SFU) SFU CMPT 201 (4) 2004/09/01 to 2005/04/30
Thompson Rivers University (TRU) TRU COMP 123 (3) 2004/09/01 to 2005/04/30
Trinity Western University (TWU) TWU CMPT 231 (3) 2004/09/01 to 2005/04/30
University of British Columbia - Vancouver (UBCV) UBCV CPSC 2nd (4) 2004/09/01 to 2005/04/30
University of Northern BC (UNBC) UNBC CPSC 200 (3) 2004/09/01 to 2005/04/30
University of the Fraser Valley (UFV) UFV COMP 251 (4) 2004/09/01 to 2005/04/30
University of Victoria (UVIC) UVIC CSC 115 (1.5) 2004/09/01 to 2005/04/30
Vancouver Island University (VIU) VIU CSCI 161 (3) 2004/09/01 to 2005/04/30

## Course Offerings

### Winter 2021

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