School of Computer Science

Module 06-28345 (2017)

Data Structures and Algorithms

Level 1/C

John Bullinaria Semester 2 10 credits
Co-ordinator: John Bullinaria
Reviewer: Achim Jung

The Module Description is a strict subset of this Syllabus Page.

Outline

This module will introduce the principal fundamental data structures and algorithms used in computer science. Data structures will be formulated to represent information in such a way that it can be conveniently and efficiently manipulated by the algorithms that are developed. The ideas will be presented abstractly, although examples will be given in the language used in the programming workshop module.


Aims

The aims of this module are to:

  • introduce the fundamental data structures and algorithms used in computer science;
  • support and underpin the programming workshop module;
  • introduce advanced abstract data types and standard operations on the same and demonstrate their various representations;
  • discuss the advantages and disadvantages of the different representations of data types;
  • introduce invariants for proving algorithm and data structure properties;
  • introduce the main algorithms for fundamental tasks such as sorting and searching and examine their complexity.

Learning Outcomes

On successful completion of this module, the student should be able to:

  1. demonstrate understanding of the principles of algorithm development
  2. demonstrate understanding of abstract models of data and computation
  3. make informed choices between alternative ways of implementation, justifying choices on grounds such as time and space complexity
  4. explain and apply data structures such as binary trees, heap-trees, graphs and tables, together with their internal representations and relevant algorithms
  5. select, with justification, appropriate data structures to ensure efficient implementation of an algorithm (e.g., searching, insertion, deletion or sorting)
  6. explain the differences between basic complexity classes of algorithms (constant, linear, quadratic, logarithmic, exponential)
  7. argue that algorithms are correct, and derive their time complexity
  8. select, with justification, appropriate algorithms for basic tasks such as searching and sorting, including reference to the algorithm's complexity class

Restrictions

N/a


Co-requisites


Teaching methods

2 hrs lecture, 1 hr exercise class per week

Contact Hours:

43


Assessment

Sessional: 1.5 hr examination (80%), continuous assessment (20%).

Supplementary (where allowed): By examination only.


Detailed Syllabus

  1. Introduction
  2. Basic data structures and operations
    • Arrays, Loops, Invariants
    • Linked-Lists, Recursion
    • Stacks, Queues, Sets
  3. Searching
    • Requirements and Specification
    • Linear versus Binary Search
  4. Efficiency and Complexity
    • Measuring Efficiency
    • Complexity classes and Big-O notation
  5. Trees
    • Representations and primitive operators
    • Quad Trees
    • Binary Trees
    • Binary Search Trees, B-Trees
    • Priority Queues and Binary Heap Trees
    • Binomial Heaps, Fibonacci Heaps
  6. Sorting Algorithms
    • General principles and strategies
    • Insertion Sort, Selection Sort, Bubblesort
    • Tree Sort, Heapsort
    • Quicksort, Merge Sort
    • Non-Comparison Sorts
  7. Storing Data
    • Storing in Trees
    • Hash Tables
    • Handling Collisions
  8. Graphs
    • Representations
    • Planarity and Traversals
    • Shortest Paths (Dijkstra's and Floyds Algorithms)
    • Minimal Spanning Trees (Prim's and Kruskal's Algorithms)
    • Travelling Salesmen and Vehicle Routing Problems

Programmes containing this module