COMP 3270 - Heaton - Midterm 1

Abstract data structure

Question

refers to the set of operations it allows (eg append (add to end), get_min, remove(i), etc) sometimes also known as the interface

Computational Problem

Question with a correct answer

- Predicate

- Input Data

- Output

Algorithm

Series of steps that take an input and create an output for a computational problem

Data structure

Purpose: store data in a way that efficiently supports how we want to access and change that data

refer to a particular implementation of that interface which may have different run times for the operations involved

Sequences

a

Queue

a

Priority Queue

a

Sets and Maps

a

Array Sequence

a

Linked List Sqeuence

a

Dynamic Array Sequence (Vector)

a

Dynamic Array Stack

a

Linked List Stack

a

Stack

a

Array Queue

a

Linked List Queue

O(1)

Constant

O(n^2)

Quadratic

O(2^n)

Exponential

O(n^c)

Polynomial

O(log n)

Log

O(n)

Linear

O(n log n)

Log Linear

Duplicate Algorithm

Binary Search

Swap algorithm

Selection Sort

Insertion Sort

Bubble Sort

Merge algorithm

Merge Sort

Partition algorithm

Quick Sort

Selection Sort runtime

O(n^2)

Insertion Sort runtime

O(n^2)

Bubble Sort runtime

O(n^2)

Merge Sort runtime

O(n log n)

Quick Sort runtime

O(n log n)