S02 - Fundamentals of Data Structures

Advantages of Arrays

Direct access to data

Disadvantages of Arrays

Potentially wasteful of memory

Static data structure

Size is declared at compile-time and doesn’t change during runtime

Advantages of static data structure

With memory allocation fixed, no control or oversight is needed to prevent potential overflow or underflow issues when adding new items or removing existing ones.

Dynamic data structure

Size can grow or shrink during runtime

Disadvantage of dynamic data structure

Requires extra memory to store pointers to the next item

Differences of Static and Dynamic data structures

• Static data structures have storage size determined at compile-time

• Dynamic data structures can grow/shrink at runtime

• Static data structures have fixed size

• Static data structures can waste space/memory if the number of items stored is small relative to the size of the structure

• Dynamic data structures only take up the amount of storage space required for the actual data

• Dynamic data structures require pointers to the next item which requires memory

• Static data structures store data in consecutive memory locations

Abstract Data Type (ADT)

Logical description of how we view the data and possible operations

Linear queues

FIFO logic, items join at the rear and leave at the front

What does the front pointer in a queue point to

Next item to remove

What does the rear pointer in a queue point to

Last item added

Methods for queues

Enqueue(item), Dequeue(), isFull(), isEmpty()

Stacks

LIFO logic, items are pushed on top of the stack and removed from the top of the stack

Basic operations of stacks

Push(item), pop(), peek(), isFull(), isEmpty()

Explain how a single stack can be used to reverse the order of the items in a queue

Until the queue is empty, repeatedly remove items from the front of the queue and push it on top of the stack and add them to the rear of the queue

Call stack

System-level data structure. Keeps track of the point to which each subroutine should return control when it finishes executing, the use of this is hidden from the programmer in HLL.

Stack frame contents

• Return address on completion of subroutine execution

• Values of all parameters

• Values of all local variables

How are calls to subroutines executed

1. The parameters are added to a stack frame

2. Local variables are added to the same stack frame

3. Local variables are added to the same stack frame

4. The address to which execution returns after the end of the subroutine is reached is added to the same stack frame

5. Execution is transferred to the subroutine code

What happens when the subroutine completes execution?

1. The stack is popped

2. Program control is returned to the address mentioned in the popped stack frame

3. The values of local variables are parameters are also extracted from the stack frame

4. Execution is transferred back to the return address

Abstraction

The process of removing unnecessary details from some representation

Use of adjacency matrix

Many edges, useful if many changes needed to the graph due to direct access to an edge

Advantages of adjacency matrix

More useful when there are lots of edges, or when many changes are made to the graph due to an edge

Disadvantages of adjacency matrix

Not useful for sparse graph with not many connections - most cells empty, memory space wasted

Why an adjacency matrix shouldn’t be used

For a sparse graph with not many connections, waste of memory

Graph

diagram consisting of vertices, joined by edges where each edge joins exactly two vertices

Uses of adjacency list

Large, sparsely connected graph, only uses storage for connections that exist which is more space efficient

Adjacency list

An alternative way of representing a graph - a list of nodes is created, and each node points to a list of adjacent nodes - dictionary data structure

Advantages of adjacency list

Only uses storage for connections that exist - more space efficient. Good way of representing a large, sparsely connected graph

Tree

fully connected undirected graph with no cycles; doesn’t have to have a root

Rooted tree

tree with one node designated as the root

Binary tree

Rooted tree in which every node has at most 2 children

Binary search tree

• Items are added using an algorithm, by comparing a new item with the root of the tree, then with every subtree’s root

• Makes search quicker

• Items can also be output in order

Binary search tree

Items are added using an algorithm by comparing a new item with the root of the tree, then with every subtree’s root

Advantages of binary search tree

Makes the search quicker, items can be output in order which is faster than the usual sort algorithm

Uses of binary search trees in Computer Science

OS: directory of files and folder structure; Compiler: to build syntax trees; Routers: store routing tables

Hash table

Data structure that creates mapping between keys and values

Collision

When two keys compute the same hash

Hashing algorithm

Calculation that takes the key as input and computes into a hash that is what is stored in the hash table

Collision resolution

Store the record in the next available location in the file

Explain how a value is stored in a hash table

Hashing algorithm is applied to the key; The result is an index of where to store the value in an array; It is possible that the hashing algorithm might generate the same key for two different values (collision); in which case a collision handling method is used

What happens if the load factor of a hash table is >60-65%

Increase table size and rehash all data items; choose a prime number as the hash table size

Searching the hash table

Apply the hash function to the key of the item sought. If target is at the hash then it is found, if not then look for a ‘deleted’ marker. If there is no marker, the item is not found.

Scalar multiplication

Scaling the original vector by a factor of a given multiplier

Convex combination

Space bounded by two vectors and the line joining their ends

Dot product

Value resulting in the sum of products u.v = u1v1+u2v2+u3v3+…+unvn

Applications of dot product

Calculate parity bit in GF(2)

Galois Field

Given to a set that consists of a finite number of items

Dictionary

An abstract data type made up of associated pairs, key and a value

Use of dictionaries

Applications where items need to be looked up: ASCII or Unicode table, foreign language dictionary, trees and graphs

Vector

A mathematical quantity that has both magnitude and direction

Vector addition

If the two vectors are represented as an arrow in the 2D space, the vector addition is the diagonal vector of the resulting parallelogram; its effect is vector translation, of one of the two vectors across the other

Scaler multiplication

Scaling the original vector by a factor of given multiplier

Convex combination

Space bounded by two vectors and the line joining their ends; Formula: w = αu + βv, where α, β >= 0 and α+β=1; vector w will fall on the line, or inside the space if α+β < 1 (this is the convex hull)