Lecture: 2 hours/week
Lab: 2 hours/week
The methods of instruction for this course include lectures, labs, and self-directed learning (programming assignments).
- An overview of object-oriented design and implementation principles, including encapsulation, inheritance, polymorphism, operator overloading, and templates
- Abstract Data Types (ADTs)
- An introduction to efficiency analysis of algorithms and related mathematical notations: Big-O, Small-O, Omega, and Theta
- Divide and Conquer problem-solving technique and recursion
- Sorting and searching algorithms
- Representing a data structure in memory: contiguous vs. linked representation
- The Stack ADT
- Queues and priority queues
- Linked lists and their variations
- Implementing and using iterators
- Hashing: hash maps and hash sets
- C++ Standard Template Library (STL): use of STL containers, algorithms, and iterators for application development
Upon the completion of this course, successful students will be able to:
- define the concept of Abstract Data Types (ADTs);
- evaluate the time and space complexity of algorithms using an experimental analysis;
- differentiate and compare an ADT's contiguous implementation versus its linked implementation;
- define and implement fundamental data structures such as stacks, queues, lists, trees, sets, hash tables, and graphs as ADTs;
- apply object-oriented principles to implement an ADT;
- utilize static and dynamic memory allocation in implementing a data structure;
- select appropriate data structures and algorithms for a specific application;
- utilize the Divide and Conquer technique to solve a problem recursively;
- analyze the efficiency of a recursive function and compare it with an equivalent iterative implementation;
- identify, implement, analyze, and compare different sorting and searching algorithms;
- implement and utilize iterators and;
- identify different components of the C++ Standard Template Library (STL) and apply STL containers, algorithms, and iterators to develop applications.
Evaluation will be carried out in accordance with the Douglas College Evaluation Policy. The instructor will present a written course outline with specific evaluation criteria at the beginning of the semester. Evaluation will be based on the following:
| Labs | 10% - 20% |
| Assignments | 10% - 30% |
| Quizzes* | 0% - 15% |
| Term tests* | 20% - 35% |
| Final examination* |
25% - 40% |
| Total |
100% |
* In order to pass the course, in addition to receiving an overall course grade of 50%, students must achieve a grade of at least 50% on the combined weighted examination components (including quizzes, term tests, and final examinations.)
Consult the Douglas College Bookstore for the latest required textbooks and materials.
Sample text:
Data Abstraction & Problem Solving with C++: Walls and Mirrors (latest edition), Frank M. Carrano and Timothy Henry, Pearson, ISBN: 978-0134463971
None