Data structures and algorithms

Primary tabs

Global rating: 
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Please login or register to take this course.
Aims and scope: 

This module provides an introduction to data structures and algorithms for computer scientists. The module introduces a number of fundamental data structures, including arrays, linked lists, stacks, queues, trees, hash tables, and graphs. These are presented both abstractly, via the notion Abstract Data Types, and concretely in terms of their implementation in an object-oriented framework. The data structures are discussed and analysed in terms of efficiency of the basic operations they support and their application to program design problems. Consideration is given to important, fundamental algorithms for searching and sorting data. After successful completion of this course, students should be able to evidence knowledge of a variety of data structures in terms of their characteristic behaviours; implement and apply appropriate data structures for solving program design problems; demonstrate basic knowledge of complexity issues with respect to data manipulation; evidence understanding of a number of fundamental algorithms.

Algorithms and algorithmic problem solving are at the heart of computer science. This module introduces students to the design and analysis of efficient algorithms and data structures. Students learn how to quantify the efficiency of an algorithm and what algorithmic solutions are efficient. Techniques for designing efficient algorithms are taught, including efficient data structures for storing and retrieving data. This is done using illustrative and fundamental problems: searching, sorting, graph algorithms, and combinatorial problems such as finding shortest paths in networks.

This course is designed for a second course in computer science, the CS 2 course at many universities. The course’s emphasis is on the specification, design, implementation, and use of the basic data types. In addition, we cover a range of important programming techniques and provide self-contained coverage of abstraction techniques, object-oriented programming, big-O time analysis of algorithms, and sorting. We assume that the student has already had an introductory computer science and programming class, but we do include coverage of those topics (such as recursion and pointers) that are not always covered completely in a first course. Providing an early, self-contained review of object-oriented programming and C++, this course gives students a firm grasp of key concepts and allows those experienced in another language to adjust easily. A solid foundation in building and using abstract data types is also provided, along with an assortment of advanced topics such as B-trees for project building and graphs.

This course is designed for students who are comfortable with the basics of programming in the C language, including C arrays as a structured data type. Its main objective is to complete instruction in basic tools, both coding and data organization strategies, needed for solving programming problems in different kinds of programming languages and effectively using data structures libraries provided by many languages. The course extends knowledge of the C language and programming to include structures, files, recursion, and pointers to dynamically allocated memory. It introduces the concept of Abstract Data Types (ADTs) and the principle of separation of interface and implementation. It also presents basic Big O notation as a basic concept of algorithm analysis and uses it throughout the course to characterize the time and space complexity properties of different implementations of ADTs. The remainder of the course examines different commonly used ADTs (lists, stacks, queues, trees, graphs, hash tables and heaps) along with the fundamental operations associated with these types (initialization, addition, deletion, traversal, etc. ...) and their implementations. Students will develop competence in making choices about the most appropriate data structures for solving moderately sized problems and supporting their choices with arguments based on the time and space complexity properties of each data structure.

Topics: 

1. The Phases of Software Development. 2. Abstract Data Types and C++ Classes. 3. Container Classes. 4. Pointers and Dynamic arrys. 5. Linked Lists. 6. Software Development with Templates, Iterators, and the STL. 7. Stacks. 8. Queues. 9. Recursive Thinking. 10. Trees. 11. Balanced Trees. 12. Searching. 13. Sorting. 14. Derived Classes and Inheritance. 15. Graphs.

Indicative reading: 

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms, 3rd ed. MIT press; Hanly, J. R., Koffman, E. B. (2015). Problem solving and program design in C, 8th ed. Pearson; Main, M., & Savitch, W. J. (2010). Data structures and other objects using C++, 4th ed. Pearson; Goodrich, M. & Tamassia, R. (2011). Data Structures and Algorithms in Java, 5th ed. John Wiley and Sons; Weiss, M.A. (2010). Data Structures & Problem Solving using Java, 4th ed. Addison-Wesley.

Teaching modules: