Computer Science (COMP) 272
Data Structures and Algorithms (Java) (Revision 6)
Revision 6 is closed for registrations, replaced by current version
View previous syllabus
Delivery Mode: Individualized study online
Credits: 3
Area of Study: Science
Prerequisite: COMP 268 or an equivalent introductory programming course in Java. Knowledge of high school mathematics (MATH 30 level) is assumed.
Students in this course are required to contact their tutor using email.
Please see the Tutor and Coordinator Support page for more information.
Centre: School of Computing and Information Systems
SCIS Orientation
COMP 272 has a Challenge for Credit option.
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:
Assignment 1 | Assignment 2 | Discussion Forum | Midterm Quiz | Journal of Unit Exercises | Final Exam | Total |
---|---|---|---|---|---|---|
10% | 10% | 10% | 20% | 10% | 40% | 100% |
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
There is no textbook for this course.
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:
Assignment | Final Examination | Total |
---|---|---|
50% | 50% | 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 6, July 9, 2012.
View previous syllabus