# Computer Science (COMP) 272

## Data Structures and Algorithms (Revision 7)

Delivery Mode: Individualized study online

Credits: 3

Area of Study: Science

Prerequisite: COMP 268 or COMP 206. Familiarity with the fundamentals of Java and/or C++ is a prerequisite to this course. Candidates with considerable programming skills in Java, C, C++, or other languages may be admitted upon approval from the course professor. Knowledge of high school mathematics (MATH 30 level) is assumed.

COMP 272 has a Challenge for Credit option.

**Note: Students who are concerned about not meeting the prerequisites for this course are encouraged to contact the course coordinator before registering

## Overview

COMP 272 covers analysis and design of fundamental data structures and engages learners to use data structures as tools to algorithmically design efficient computer programs that will cope with the complexity of actual applications.

The course focuses on basic and essential topics in data structures, including array-based lists, linked lists, skiplists, hash tables, recursion, binary trees, scapegoat trees, red–black trees, heaps, sorting algorithms, graphs, and binary trie.

## Outline

• Unit 0: Orientation
• Unit 1: Introduction
• Unit 2: Array-Based Lists
• Unit 4: Skiplists
• Unit 5: Hash Tables
• Unit 6: Recursion
• Unit 7: Binary Trees
• Unit 8: Scapegoat Trees
• Unit 9: Red–Black Trees
• Unit 10: Heaps
• Unit 11:Sorting Algorithms
• Unit 12: Graphs
• Unit 13: Binary Trie

## Learning Outcomes

Students successfully completing this course will be able to:

• explain the need for efficiency in data structures and algorithms.
• apply methods to analyze running time of essential data structures and estimate efficiency of the algorithms and implementations.
• understand and apply the concept of abstract data type to represent and implement heterogeneous data structures.
• write programs using array-based lists.
• write programs using linked lists.
• write programs that use skiplists.
• write code for hash tables, and compare and contrast various collision detection and avoidance techniques.
• demonstrate skills in tracing, analyzing, and designing recursive algorithms and recursive methods.
• write programs using binary trees and variations.
• explain programs that use scapegoat trees.
• explain programs that use red–black trees.
• write programs to apply heaps to implement priority queues.
• analyze and implement different types of sorting algorithms.
• implement data structures for graphs and approaches for searching graphs using breadth-first, depth-first, best-first search, etc.
• analyze binary trie.

## Evaluation

To receive credit for COMP 272, you must achieve a course composite grade of at least “D” (50 percent) and a grade of at least 50 percent on the final examination. The weighting of the composite grade is as follows:

Activity Weighting
Assignment 1 (Unit 1-4) 20%
Assignment 2 (Unit 5-8) 20%
Assignment 3 (Unit 9-13) 20%
Final Exam 40%
Total 100%

The final examination for this course must be taken online with an AU approved exam invigilator at an approved invigilation centre. It is your responsibility to ensure your chosen invigilation centre can accommodate online exams. For a list of invigilators who can accommodate online exams, visit the Exam Invigilation Network.

## Course Materials

### Textbook

The main text for this course is Pat Morin’s online book titled Open Data Structures. You can choose to complete this course using either Java or using C++, or both. The main text can be accessed at http://www.aupress.ca/index.php/books/120226. You may choose Java edition, C++ edition, or pseudo-code edition for the textbook at http:/opendatastructures.org/ as well.

### Other Materials

• Units 0 through 13 of the study guide
• descriptions of the requirements for the individual assignments
• sample exam

Additional supporting materials of interest to students may occasionally be made available electronically.

### Special Course Features

Computer science courses at Athabasca University require that students use computer-mediated communications. We expect students to have access to computer equipment with certain requirements.

The course work in COMP 272 requires students to have an appropriate programming environment or tool for Java or C++ programming in their local computer(s). More information about programming environment and tools needed to implement any assignment are detailed in the course package.

## Challenge for Credit Course Overview

The Challenge for Credit process allows students to demonstrate that they have acquired a command of the general subject matter, knowledge, intellectual and/or other skills that would normally be found in a university level course.

Full information for the Challenge for Credit can be found in the Undergraduate Calendar.

## Challenge Evaluation

To receive credit for the COMP 272 challenge registration, you must achieve a grade of at least 75 per cent on the assignment and "B" (75 per cent) on the final examination. The weighting of the composite grade is as follows:

Activity Weighting
Assignment 50%
Final Examination 50%
Total 100%

### Undergraduate Challenge for Credit Course Registration Form

Athabasca University reserves the right to amend course outlines occasionally and without notice. Courses offered by other delivery methods may vary from their individualized-study counterparts.

Revision 7, May 22, 2014.