# Data Structures and Algorithms

Faculty
Science & Technology
Department
Computing Science
Course Code
CMPT 2300
Credits
3.00
Semester Length
15
Max Class Size
35
Method Of Instruction
Lecture
Lab
Typically Offered
To be determined

## Overview

Course Description
This course introduces students to a variety of fundamental data structures and their related algorithms. Topics include: abstract data types, data structures implementation and analytical evaluation methods, problem solving using divide and conquer, sorting and searching algorithms, complexity analysis of algorithms, iterators, hashing, and C++ Standard Template Library (STL). Students will apply object-oriented programming techniques to implement important linear and non-linear data structures such as stacks, queues, priority queues, lists, trees (including binary search trees and binary heaps), sets, and graphs.
Course Content
• An overview of object-oriented design and implementation principles, including encapsulation, inheritance, polymorphism, operator overloading, and templates
• An introduction to efficiency analysis of algorithms and related mathematical notations: Big-O, Small-O, Omega, and Theta
• Divide and Conquer problem-solving technique and recursion
• Sorting and searching algorithms
• Representing a data structure in memory: contiguous vs. linked representation
• Queues and priority queues
• Linked lists and their variations
• Implementing and using iterators
• Hashing: hash maps and hash sets
• C++ Standard Template Library (STL): use of STL containers, algorithms, and iterators for application development
Methods Of Instruction

The methods of instruction for this course include lectures, labs, and self-directed learning (programming assignments).

Means of Assessment

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

 Labs 10% - 20% Assignments 10% - 30% Quizzes* 0% - 15% Term tests* 20% - 35% Final examination* 25% - 40% Total 100%

* In order to pass the course, in addition to receiving an overall course grade of 50%, students must achieve a grade of at least 50% on the combined weighted examination components (including quizzes, term tests, and final examinations.)

Learning Outcomes

Upon the completion of this course, successful students will be able to:

• define the concept of Abstract Data Types (ADTs);
• evaluate the time and space complexity of algorithms using an experimental analysis;
• differentiate and compare an ADT's contiguous implementation versus its linked implementation;
• define and implement fundamental data structures such as stacks, queues, lists, trees, sets, hash tables, and graphs as ADTs;
• apply object-oriented principles to implement an ADT;
• utilize static and dynamic memory allocation in implementing a data structure;
• select appropriate data structures and algorithms for a specific application;
• utilize the Divide and Conquer technique to solve a problem recursively;
• analyze the efficiency of a recursive function and compare it with an equivalent iterative implementation;
• identify, implement, analyze, and compare different sorting and searching algorithms;
• implement and utilize iterators and;
• identify different components of the C++ Standard Template Library (STL) and apply STL containers, algorithms, and iterators to develop applications.
Textbook Materials

Consult the Douglas College Bookstore for the latest required textbooks and materials.

Sample text:

Data Abstraction & Problem Solving with C++: Walls and Mirrors (latest edition), Frank M. Carrano and Timothy Henry, Pearson, ISBN: 978-0134463971

## Requisites

### Prerequisites

CMPT 1209 or CSIS 1275 or CSIS 2175 with a minimum grade of C

### Equivalencies

No equivalent courses.

## 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
College of the Rockies (COTR) COTR COMP 2XX (3) 2018/01/01 to -
Kwantlen Polytechnic University (KPU) KPU CPSC 1204 (3) 2018/01/01 to -
North Island College (NIC) NIC CPS 101 (3) 2018/01/01 to -
Okanagan College (OC) OC COSC 222 (3) 2018/01/01 to -
Simon Fraser University (SFU) SFU CMPT 225 (3) 2018/01/01 to -
University Canada West (UCW) UCW CPSC 2XX (3) 2018/01/01 to -
University of British Columbia - Okanagan (UBCO) UBCO COSC 121 (3) 2018/01/01 to -
University of British Columbia - Vancouver (UBCV) UBCV CPSC 2nd (3) 2018/01/01 to -
University of Northern BC (UNBC) UNBC CPSC 2XX (3) 2018/01/01 to -
University of the Fraser Valley (UFV) UFV COMP 251 (4) 2018/01/01 to -
University of Victoria (UVIC) UVIC CSC 115 (1.5) 2018/01/01 to -
Vancouver Island University (VIU) VIU CSCI 161 (4) 2018/01/01 to -

## Course Offerings

### Fall 2021

CRN
Days
Dates
Start Date
End Date
Instructor
Status
36281
Tue Thu
07-Sep-2021
- 08-Dec-2021
07-Sep-2021
08-Dec-2021
Ariafar
Arezoo
Open
Max
Enrolled
Remaining
Waitlist
35
22
13
0
Days
Building
Room
Time
Tue Thu
New Westminster - North Bldg.
N6111
12:30 - 14:20