Computer Science (COMP) 272

Overview

COMP 272 builds on the concepts introduced in COMP 268 and shows how to use data structures as tools to design computer programs that will cope with the complexity of actual applications.

Topics covered include the fundamentals of algorithm analysis, recursion, stacks, queues, lists, trees, sorting and searching. Familiarity with the fundamentals of the Java programming language is a prerequisite to this course.

Learning Objectives

• introduce the terminology and the key concepts related to data structure and algorithm analysis.
• introduce the concept of recursion and the concept of a recursive algorithm, describe the sorting problem and explain its importance.
• describe lists, stacks, and queues at the abstract level, implement them in Java, and analyze the efficiency of their implementations
• explain the notion of a (rooted) tree at the abstract level and give examples for the applications of trees.
• explain the binary heap at the abstract level, define it as an ADT, implement that ADT in Java, and estimate the cost of the implemented heap operations.
• discuss the workings of a hash table at the abstract level, define a hash table ADT and implement it in Java then, estimate the cost of the basic hash table operations.

Learning Outcomes

Students successfully completing this course will be able to:

• demonstrate skills in tracing, analyzing and designing recursive algorithms and recursive Java methods.
• use various sorting algorithms and estimate their running time.
• write Java code about lists, stacks, and queues, and analyze the efficiency of their implementations
• define ADTs for trees in general, for binary trees, and for binary search trees, implement them in Java, and analyse the cost of the implemented tree operations.
• apply binary heaps into internal and external sorting and into implementing priority queues.
• use a hash table at the abstract level, define a hash table ADT and implement it in Java then, estimate the cost of the basic hash table operations.

Outline

Unit 1: Algorithm Analysis

• Algorithm, function, running time, input size, dominant term, Big-Oh.
• Definitions: Big-Oh, Big-Omega, Big-Theta, and Little-Oh.
• Cost analysis of algorithms, verification of running times.

Unit 2: Recursion

• Recursive definition, proof by induction.
• Implementation of recursion, stack of method activation records.
• Divide-and-conquer algorithms.

Unit 3: Sorting

• The sorting problem, Insertion Sort, quadratic sorting algorithms.
• Shell Sort, Merge Sort.
• Quick Sort, Quick Select.

Unit 4: List, Stack, and Queue

• List, stack, and queue ADTs, Java's iterator pattern.
• Array and linked implementations of list ADTs, cost analysis.
• Array and linked implementations of stack and queue ADTs, cost analysis.
• Doubly linked lists and circular lists.

Unit 5: Tree

• Terminology of trees.
• Binary trees and their traversals.
• Implementation of binary search tree, cost analysis.

Unit 6: Heap

• Binary heap as priority queue.
• Implementation of binary heap, cost analysis.
• Heap Sort.
• External sorting, replacement selection.

Unit 7: Hashing

• Concept of hashing, hash functions.
• Collision resolution strategies, clustering.
• Hash table implementations, cost analysis.

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:

Assignment 1	Assignment 2	Assignment 3	Final Exam	Total
20%	20%	20%	40%	100%

To learn more about assignments and examinations, please refer to Athabasca University's online Calendar.