main page  —  COMP 526 Applied Algorithmics

# Unit 2: Fundamental Data Structures

This is an archived version of this module from Spring 2022.

This unit covers fundamental data structures:

• stacks, queues, and resizable arrays
• priority queues and binary heaps
• binary search trees

### Learning outcomes

1. Understand and demonstrate the difference between abstract data type (ADT) and its implementation
2. Be able to define the ADTs stack, queue, priority queue and dictionary/symbol table
3. Understand array-based implementations of stack and queue
4. Understand linked lists and the corresponding implementations of stack and queue
5. Know binary heaps and their performance characteristics
6. Understand binary search trees and their performance characteristics

This unit covers some prerequisites for the remainder of the module. To accommodate the varying levels of prior exposure with this material, I will briefly recap the topics to bring all of you to a minimal level before moving on.

If you previously had an algorithms and data structures module in a computer science undergraduate course, this unit will mostly be repetition for you. But if you have never seen the material before, the brief summary I give in the context of this module will not suffice to replace such a module. While not strictly necessary to succeed in COMP526, you are highly encouraged to learn more in depth about these gems of computer science. For that I have collected some external high-quality material:

## Material

• slides
• lecture notes

• Video 2-1 (2022-02-10): §2.1 ADTs, Stacks and Queues

• Video 2-2 (2022-02-10): §2.2 Resizable arrays

• Video 2-3 (2022-02-10): §2.3 Priority queues & binary heaps

• Video 2-4 (2022-02-14): §2.4 Operations on binary heaps
Unfortunately, the first 8min of the recording have no sound; the same content is covered in the video from last year (part 1, part 2).

• Video 2-5 (2022-02-14): §2.5 Symbol tables

• Video 2-6 (2022-02-14): §2.6 Binary search trees

• Video 2-7 (2022-02-14): §2.7 Ordered symbol tables

• Video 2-8 (2022-02-14): §2.8 Balanced binary search trees