Computer Science (COMP) 504

Object Structure and Programming (Revision 3)

COMP 504 Course website

Delivery Mode: Grouped Study Online (with eTextbook)

Credits: 3

Area of Study: IS Foundation

Prerequisite: None

Faculty: Faculty of Science and Technology

Centre: School of Computing and Information Systems

Instructor: Dr. Fuhua (Oscar) Lin

**Note: This is a graduate level course and students need to apply and be approved to one of the graduate programs or as a non-program School of Computing and Information Student graduate student in order to take this course. Minimum Admission Requirements must be met. Undergraduate students who do not meet admission requirement will not normally be permitted to take this course. http://scis.athabascau.ca/

Overview

The design and analysis of efficient data structures and algorithms has long been recognized as a key subject in computing and information systems. This course discusses the fundamental concepts, principles, and techniques for effective programming, algorithm analysis, and design. Within the object-oriented paradigm, this course uses the object concept, software engineering design patterns, and their programming features to deal with object structure analysis and design. It covers the traditional data structures and algorithmic design patterns, and provides an object-oriented approach to abstract design and algorithm analysis.

Course Objectives

This course is designed to

  • introduce the concepts, principles, and approaches of object and data structures, design patterns, and algorithm development and programming;
  • perform object structure analysis, design, and application through the use of object concept and its programming features;
  • provide both the traditional data structures and object-oriented approach to advanced abstract design and algorithm analysis.

Learning Outcomes

Upon completion of the course, students will be able to

  • explain key concepts, such as abstract data type (ADT), object-oriented programming and design, and design patterns in both software engineering and algorithm design;
  • read, analyze, and design algorithms expressed in pseudo-code;
  • analyze the running time of algorithms based on primitive operations and basic functions;
  • explain and apply software engineering design patterns, such as adapter, iterator, position, template, composition, decorator, etc.;
  • explain and apply algorithmic design patterns, such as recursion, divide-and-conquer, prune-and-search, brute force, greedy algorithm, dynamic programming, etc.;
  • describe the principles and ADTs of the most important data structures, such as Stack, Queue, List, Tree, Priority Queue, Heap, Map, Dictionary, Hash Table, Search Tree, and Graph;
  • implement the ADTs of the above data structures with the Java program language;
  • explain the principles of the most widely used searching, sorting, text processing, and graph algorithms;
  • apply the above data structures and algorithms to model and solve algorithm design and programming problems;
  • analyze and use Java implementations of the data structures and algorithms above in relevant applications;
  • design and implement object-oriented applications in a Java environment using the data structures, algorithms, and design patterns above.

Outline

Unit 0: Course Introduction

Unit 1: Object-Oriented Design and Algorithm Analysis

  1. Java primer (optional)
  2. Object oriented design
  3. Indices, nodes, and recursion
  4. Algorithm analysis

Unit 2: Object and Data Structures

  1. Stacks, queues, and deques
  2. Lists and iterators
  3. Trees
  4. Heaps and priority queues
  5. Hash tables, maps, and skip lists

Unit 3: Searching and Sorting

  1. Searching and search trees
  2. Sorting, sets, and selection

Unit 4: Text and Graph Algorithms

  1. Strings and dynamic programming
  2. Graph algorithms

Evaluation

In order to receive credit for COMP 504, you must achieve a cumulative course grade of "B-" (70 percent) or better, and must achieve an average grade of at least 60 percent on the assignments and achieve a grade of at least 60 percent on the Final Examination. Your cumulative course grade will be based on the following assessment.

Assessment Unit Weight
Assignment 1 (TME1) Units 1 15%
Assignment 2 (TME2) Units 2 20%
Assignment 3 (TME3) Units 3-4 20%
Participation   5%
Final Examination   40%
Total   100%

Course Materials

Textbooks

Registration in this course includes an electronic textbook. For more information on electronic textbooks, please refer to our eText Initiative site.

Goodrich, M., & Tamassia, R. (2014). Data Structures and Algorithms in Java™ (6th ed.). Toronto, ON: John Wiley & Sons. (ISBN 978-1-118-77133-4).

A print version of the eText can sometimes be purchased from the publisher through a direct-to-student link provided on the course website; you can also acquire the textbook on your own if you wish.

Supplemental

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein C. (2009). Introduction to Algorithms (3rd ed.). Cambridge, MA: The MIT Press. (ISBN 978-0-262-03384-8)

Course Materials - Other

The remaining learning materials for COMP 504 are delivered through Athabasca University's learning management system (LMS), Moodle. Online course materials include discussion forums, learning materials, and assignments. Assignments will be submitted online.

Special Course Features

Computer Science 504 is offered in computer mediated communications (CMC) mode, and can be completed at the student's workplace or home.

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.

Opened in Revision 3, October 19, 2010.

Updated January 17 2017 by Student & Academic Services