Skip to main content

Trinity College Dublin, The University of Dublin

Menu Search



Module DescriptorSchool of Computer Science and Statistics

Module CodeCS2010
Module NameAlgorithms and Data Structures
Module Short TitleCS2010
ECTS10
Semester TaughtMichaelmas & Hillary Term
Contact HoursLecture & Tutorial hours: 33
Lab hours with lecturer and demonstrators per lab group: 11
Total hours: 44
Module PersonnelDr Vasileios Koutavas (Michelmas Term)
Dr Ivana Dusparic (Hillary Term)
Learning Outcomes

Having successfully completed this module students will:

  • Have gained significant knowledge on algorithms and data structures, and the mathematical theory and techniques to evaluate their efficiency and effectiveness.
  • Have the ability to evaluate algorithms in terms of their running time and memory space requirements and classify those algorithms in the major complexity classes using appropriate performance models.
  • Be able to efficiently implement the operations of the main data structures used in most programming.
  • Gain experience through experiments in implementing effective new and existing algorithms.
  • Be able to identify the most suitable data structures and algorithms for each programming problem based on the parameters of the problem, the advantages and limitations of each data structura and algorithm, the resources avaliable, the desired performance criteria etc.
  • Be able to design and implement robust, effective and well-structured Java programs using industry standards such as Abstract Data Types and the approaches of unit testing, test coverage, Design by Contract, and pre-/post-conditions. Students will be able to use the last two approaches to avoid defensive programming.
Learning Aims

The aim of the module is threefold:

  • To teach effective programming and problem solving, using a core toolset of classical algorithms and data structures.
  • To introduce the methods for evaluating the performance and requirements of programs written by the students
  • To promote effective software engineering by using well-established techniques for code modularity, structuring, debugging and readablity, such as Design by Contract, and unit testing.
Module Content

Theory:

  • Asymptotic growth functions and analysis of source code to derive running time and space requirements
  • Amortised running time analysis of algorithms
  • Permutations, Combinations and Sets

Data structures:

  • Array and linked list implementations of stacks and queues.
  • Doubly linked lists
  • Union-find
  • Binary trees, binary search trees, balanced search trees, B-trees
  • Hash tables
  • Undirected, directed and weighted graph implementations using adjacency lists
  • Special topics

Algorithms:

  • Recursion vs iteration; tree traversals
  • Greedy algorithms
  • Divide and conquer
  • Graph algorithms
  • Searching and Sorting algorithms
  • Special topics

Programming:

  • Java generics
  • Iterators
  • JUnit testing
  • Design by Contract
Recommended Reading List

Main textbook:
Algorithms (4th Edition)
Robert Sedgewick and Kevin Wayne

Pearson Education 2011

Other recommended textbooks:
Introduction to Programming Using Java (6th Edition)
David J. Eck


Introduction to Algorithms (3rd Edition)
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

MIT Press 2009

Algorithms and Data Structures
Nicolas Wirth
Prentice-Hall 1986

Data Structures and Algorithms
John E. Hopcroft and Jeffrey D. Ullman.
Addison-Wesley 1983

Module PrerequisitesAn introductory course on programming with Java. CS1011 and CS1012
Assessment Details

35% Coursework, 65% Exam

Assessment in the annual examinations is by written exam’ (65%) and coursework (35%). Assessment in the supplementals is by 100% written examination only.

Module Website
Academic Year of Data