One of the most important courses in the CS program. In SFU this is a pre-requisite course for over 20 CMPT courses and it is for good reasons: it teaches some of the most fundamental concepts in CS (e.g., abstract data types, algorithms, data structures) that are used in many advanced CS topics; it also teaches some programming techniques so students can comfortably implement those concepts and write their own programs. C++ is the programming language of choice (some versions use Java, goal is to have some form of OOP).

It is not an easy course and there are many things to cover (things ramp up very quickly after the first month). But a student who successfully completes this course will have the basic skillset to take on many other more complex CS subjects. My goal is to train students to have the mindset of a computer scientist and be able to both apply CS concepts to problem-solving, and appreciate the ideas behind those concepts.

This is for reference only. For actual outline refer to the course webpage at Canvas (our LMS). Content is subject to change (plus I often update it). This is the schedule I used for Summer 2024.

Course Description

Introduction to a variety of practical and important data structures and methods for implementation and for experimental and analytical evaluation. Topics include: stacks, queues and lists; search trees; hash tables and algorithms; efficient sorting; object-oriented programming; time and space efficiency analysis; and experimental evaluation.

Course Objectives

This course explores fundamental algorithms and data structures that can help in developing elegant and efficient solutions to complex problems. We will study their specification, analysis, implementation (in C++), evaluation, and applications. Platform: Linux (Ubuntu) Language: C++.

By the end of this course students should be able to:

• Design and implement solutions to problems using C++
• Explain, analyze, and compare algorithms in terms of performance
• Describe and utilize fundamental computing science concepts such as data structures
• Maintain good coding practice and style

Recommended Textbooks

• (DSA-C++ Book) Goodrich, M. T., Tamassia, R., & Mount, D. M. (2011). Data structures and algorithms in C++ (Second edition.). Wiley. Online access (requires SFU login)
• Carrano, Henry, & Henry, Timothy. (2017). Data abstraction & problem solving with C++ : walls and mirrors / Frank M. Carrano, University of Rhode Island, Timothy M. Henry, New England Institute of Technology. (Seventh edition.). Pearson.
• Stroustrup, B. (2024). Programming : principles and practice using C++ / Bjarne Stroustrup. (Third edition.). Addison-Wesley. Online access (requires SFU login)

Course Schedule

Handy Online References

• Supplementary explanations of C++ [LINK]
• Supplementary descriptions of DSA [LINK]
• Helpful visualization of algorithms [LINK]
• Another helpful visulization of algorithms [LINK]