Data and Control Structures

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

Modules, information hiding and inheritance
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

Learning Activities

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 participation₁ 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
Take advantage of polymorphism
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.

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.

September 2004 (Current)