Course

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(s) 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
  • Abstract Data Types (ADTs)
  • 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
  • The Stack ADT
  • 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
Learning Activities

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

Corequisites

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

These are for current course guidelines only. For a full list of archived courses please see https://www.bctransferguide.ca

Institution Transfer Details for CMPT 2300
College of the Rockies (COTR) COTR COMP 2XX (3)
Kwantlen Polytechnic University (KPU) KPU INFO 2315 (3)
North Island College (NIC) NIC CPS 101 (3)
Okanagan College (OC) OC COSC 222 (3)
Simon Fraser University (SFU) SFU CMPT 225 (3)
Thompson Rivers University (TRU) TRU COMP 2230 (3)
University Canada West (UCW) UCW CPSC 2XX (3)
University of British Columbia - Okanagan (UBCO) UBCO COSC_O 121 (3)
University of British Columbia - Vancouver (UBCV) UBCV CPSC_V 2nd (3)
University of Northern BC (UNBC) UNBC CPSC 2XX (3)
University of the Fraser Valley (UFV) UFV COMP 251 (4)
University of Victoria (UVIC) UVIC CSC 115 (1.5)
Vancouver Island University (VIU) VIU CSCI 161 (4)

Course Offerings

Summer 2024