COMP108

Data Structures and Algorithms

Aims

  1. To introduce the notation, terminology, and techniques underpinning the study of algorithms.
  2. To introduce basic data structures and associated algorithms.
  3. To introduce standard algorithmic design paradigms and efficient use of data structures employed in the development of efficient algorithmic solutions.

Syllabus

  1. Basics of algorithms (6 lectures)
    1. What is an algorithm, design of pseudo code algorithm, basic notion of asymptotics and worst case analysis of running time
  2. Basic data structures and associated algorithms (12 lectures)
    1. Arrays and linked lists
    2. Stacks and queues
    3. Trees and graphs
    4. Hash table
  3. Algorithmic design techniques and efficient use of data structures (18 lectures)
    1. Basic top down approach - searching and sorting
    2. Divide-and-conquer approach - searching and sorting
    3. Greedy approach - graph algorithms
    4. Dynamic programming approach

Learning Outcomes

  • Be able to describe the principles of and apply a variety of data structures and their associated algorithms;
  • Be able to describe standard algorithms, apply a given pseudo code algorithm in order to solve a given problem, and carry out simple asymptotic analyses of algorithms;
  • Be able to describe and apply different algorithm design principles and distinguish the differences between these principles;
  • Be able to choose and justify the use of appropriate data structures to enable efficient implementation of algorithms;