Computer Science (COMP) 504
Object Structure and Programming (Revision 3)
Area of Study: IS Foundation
Faculty: Faculty of Science and Technology
Instructor: Dr. Fuhua (Oscar) Lin
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.
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.
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.
Unit 0: Course Introduction
Unit 1: Object-Oriented Design and Algorithm Analysis
- Java primer (optional)
- Object oriented design
- Indices, nodes, and recursion
- Algorithm analysis
Unit 2: Object and Data Structures
- Stacks, queues, and deques
- Lists and iterators
- Heaps and priority queues
- Hash tables, maps, and skip lists
Unit 3: Searching and Sorting
- Searching and search trees
- Sorting, sets, and selection
Unit 4: Text and Graph Algorithms
- Strings and dynamic programming
- Graph algorithms
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.
|Assignment 1 (TME1)||Units 1||15%|
|Assignment 2 (TME2)||Units 2||20%|
|Assignment 3 (TME3)||Units 3-4||20%|
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.
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 - OtherThe 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.