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 generics and collections, algorithm analysis, recursion, stacks, queues, lists, iterators, vectors, trees, heaps, sorting, hashing, searching, and graphs. 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, introduce the concept of a recursive algorithm, and develop recursive programs in Java;
• describe generics, collections, lists, stacks, queues, iterators, and vectors at the abstract level, implement them in Java, and analyze the efficiency of their implementations;
• explain the notion of a tree at the abstract level and develop example applications using different types of trees;
• explain 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, and estimate the cost of the basic operations for different hash functions;
• develop code to search text using Robin-Karp, Boyer-Moore, and Regular Expressions ;
• represent graphs in data structures and implement java code to search graphs using breadth-first, depth-first, and best-first search.

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 generics, collections, lists, stacks, queues, iterators, and vectors, and analyze the efficiency of their implementations.
• write Java code for different types of sorting algorithms.
• define ADTs for trees in general, for other types of 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.
• write Java code for hash tables and compare and contrast various collision detection and avoidance techniques.
• write Java code to search text using Robin-Karp, Boyer-Moore, and Regular Expressions.
• write Java code to develop graphs and search graphs using breadth-first, depth-first, and best-first search.

Outline

Unit 1: What are Data Structures and Algorithms? (Week 1)

• What are Data Structures and Algorithms?
• The Importance of Algorithms
• A Data Structure called "Array"
• Linearly searching for a data item in a data structure.
• Binary search - better than Linear search?
• Generics in Java
• Collections - an introduction
• Collections Algorithms
• Collections Examples

Unit 2: Computational Complexity (Week 2)

• O-Notation
• O-Notation Examples
• Algorithm Running Time
• Algorithmic Complexity of Selection Sort
• Algorithmic Complexity of Insertion Sort
• Comparing Sorting Techniques based on Complexity
• More on Algorithmic Complexity
• A Recap on Computational Complexity

Unit 3: Stacks, Queues, Lists, Iterators, and Vectors (Weeks 3 & 4)

• Stack as a Data Structure
• A Stack Interface
• Queue as a Data Structure
• Singly Linked Lists
• Variations of Lists
• Stacks as Lists
• Efficiency of Lists
• Iterators in Java
• The For-Each Loop
• Vectors

Unit 4: Sorting (Weeks 5 & 6)

• Sorting Algorithms - Introduction
• Object Ordering in Collections
• SortedSet Interface
• SortedMap Interface
• Insertion Sort
• Merge Sort
• Bubble Sort
• Heap Sort
• Quick Sort
• Radix Sort
• Counting Sort
• Bucket Sort

Unit 5: Recursion (Week 7)

• Introduction to Recursion
• How to write Recursive Programs
• Why use Recursion?
• Time Complexity of Recursion

Unit 6: Heaps and Trees (Weeks 9 & 10)

• Tree
• Introduction to Heaps
• Binary Trees and Binary Search Trees
• Binary Heap Trees and Priority Queues
• AVL Trees
• Red-Black Trees
• B-Tree

Unit 7: Hashing (Weeks 11 & 12)

• What is Hashing
• Types of Hash Functions
• Resolving Hash Collisions
• HashTable examples
• HashMap examples
• Distributed Hash Table

Unit 8: Searching Text (Weeks 13 & 14)

• Simple Search for Text
• Fast Text Search - Robin-Karp Algorithm
• Fast Text Search - Boyer-Moore Algorithm
• Regular Expressions - an introduction
• Regular Expressions in Java - Character Classes
• Regular Expressions in Java - Quantifiers
• Regular Expressions in Java - Groups and Boundary Matchers

Unit 9 Graphs (Weeks 15 & 16)

• Graphs
• Representing Graphs in Data Structures
• Searching Graphs - depth-first search
• Searching Graphs - breadth-first
• Searching Graphs - best-first

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:

The midterm and final examinations 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.

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

Course Materials

Textbook

Other materials

Course materials for COMP 272 are stored in a self-extracting file on the servers at Athabasca University.

At this time the self-extracting file contains the following materials

• Units 1 to 9 of the study guide.
• Descriptions of the requirements for the individual tutor-marked assignments.

Registered students may download the self-extracting file through the World Wide Web. Additional supporting materials of interest to students may occasionally be made available electronically.

Special Course Features

IS 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 a Java 5 compiler and virtual machine installed in their computer.

Special Instructional Features

Delivery of COMP 272 (contacting the tutor, submitting assignments) is dependent on computer mediated communications. Students are required to have access to the World Wide Web.

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.

• Undergraduate Challenge for Credit Policy
• Undergraduate Challenge for Credit Procedures

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:

Undergraduate Challenge for Credit Course Registration Form

• Challenge for Credit Form