Department of Computer Science

Course director: t.b.a.
Implementation details

COSC 2011.03 Fundamentals of Data Structures

Section A  Fall    X. Deng  Mon, Wed, Fri 14:30
Section M  Winter  J. Liu   Mon, Wed, Fri 14:30
Section N  Winter  B. Guo   Tue, Thu 16:30-18:00

This course discusses the fundamental data structures commonly used in the design of algorithms. At the end of this course, you will know about the classical data structures, and master the skills in the use of abstraction, specification and program construction using modules. Furthermore, you will be able to apply them effectively in the design and implementation of algorithms.

C++ will be used as the implementation language. No prior knowledge of C or C++ is assumed. At the end of the course you will be able to programme in C++ and understand the fundamentals of the object-oriented paradigm. You may not be an expert in C++ as some advanced and complicated features may not be taught or used. However, it is expected that you will be able to quickly learn these concepts on your own.

Topics covered may include the following.

  • Review of primitive data types and abstract data type -- arrays, stacks, queues and lists -- as an introduction to C++.
  • Searching and sorting: implementation in C++. A mixture of review and new algorithms.
  • Priority queues.
  • Trees: threaded, balanced (AVL-, 2-3-, and/or B- trees), tries
  • Graphs: representations; transitive closure; graph traversals; spanning trees; minimum path; flow problems

    Texts: t.b.a.

    Prerequisites: general prerequisites