Data structures and abstract data types

what is the difference between an abstract datatype and data structures?

-a data structure defines how data is stored and organized along with the algorithms for manipulating it,
-an abstract data type defines the logical behavior and operations of a data structure without specifying its implementation details. Data structures are concrete implementations based on ADTs

What are queues?

It follows the First-In-First-Out (FIFO) principle, meaning that the element that is added first to the queue is the one that is removed first.

A queue typically supports two primary operations:

Enqueue: This operation adds an element to the end of the queue.

Dequeue: This operation removes and returns the element at the front of the queue.

In addition to these basic operations, queues may also offer other operations such as:

Peek: This operation returns the element at the front of the queue without removing it.

isEmpty: This operation checks whether the queue is empty.

Size: This operation returns the number of elements in the queue.

What are stacks?

Stacks follow the Last-In-First-Out (LIFO) principle, meaning that the most recently added element is the first one to be removed.

operations include:

Push: This operation adds an element to the top of the stack.

Pop: This operation removes and returns the element from the top of the stack.

Additionally, stacks may offer other operations such as:

Peek: This operation returns the element at the top of the stack without removing it.

isEmpty: This operation checks whether the stack is empty.

Size: This operation returns the number of elements in the stack.

Stacks are commonly used in various programming scenarios such as:

Managing function calls and recursion in programming languages (using the call stack).

Parsing expressions (e.g., infix to postfix conversion).

Undo mechanisms in text editors and other software.

Implementing backtracking algorithms.

Memory management and expression evaluation.

what are the advantages and disadvantages of adjacency lists?

Space Efficiency: Adjacency lists are often more space-efficient than adjacency matrices, especially for sparse graphs where there are relatively few edges.

Flexibility: Adjacency lists allow for efficient representation of graphs with varying degrees of connectivity, making them suitable for dynamic or irregularly structured graphs.

Efficient for Sparse Graphs: In sparse graphs, adjacency lists can save memory by only storing information about existing edges.

Disadvantages:

Slower Edge Lookup: Finding whether an edge exists between two vertices may take longer in adjacency lists compared to adjacency matrices, especially for dense graphs.

Higher Memory Overhead per Edge: Adjacency lists typically require more memory per edge than adjacency matrices, which can lead to increased memory usage for dense graphs.

Less Efficient for Dense Graphs: In dense graphs with many edges, adjacency lists may consume more memory and have slower access times compared to adjacency matrices.

what are the advantages and disadvantages of adjacency matrixes?

Advantages:

Fast Edge Lookup: Determining whether an edge exists between two vertices is efficient with constant-time lookup, making adjacency matrices suitable for dense graphs.

Efficient Memory Usage for Dense Graphs: In dense graphs where most vertices are connected to each other, adjacency matrices can be more memory-efficient compared to adjacency lists.

Efficient for Static Graphs: Adjacency matrices are suitable for static graphs where the number of vertices and edges remains constant, as they offer efficient access and manipulation operations once constructed.

Efficient for Edge Weight Lookup: If the graph is weighted, adjacency matrices provide efficient access to edge weights since weights are directly stored in the matrix.

Disadvantages:

Space Inefficiency for Sparse Graphs: For sparse graphs where few edges exist, adjacency matrices can be highly space-inefficient, as they allocate memory for all possible edges regardless of their existence.

Costly Memory Overhead: Adjacency matrices have a high memory overhead, especially for large graphs, as they require a 2D array to represent edges, potentially leading to wasted memory.

Inefficient for Dynamic Graphs: Adjacency matrices are less efficient for dynamic graphs where edges or vertices are frequently added or removed, as resizing the matrix can be costly in terms of time and memory.

Limited Scalability: As the number of vertices increases, the size of the adjacency matrix grows quadratically, potentially limiting scalability for very large graphs due to memory constraints.

what are the types of trees?

Binary Tree:

A binary tree is a tree data structure where each node has at most two children: a left child and a right child.

Binary Search Tree (BST):

A binary search tree is a binary tree where for each node, all nodes in its left subtree have values less than the node's value, and all nodes in its right subtree have values greater than the node's value.

trees contain no loops

What are hash tables?

a type of array that uses a hash function to determine where data is to be stored and organised within a data structure

what are dictionaries?

Dictionaries are data structures used to store collections of key-value pairs, where each key is associated with a corresponding value. They are also known as associative arrays, maps, or hash maps in some programming languages.

how do you add and multiply vectors?

Adding Vectors:

To add two vectors, you simply add their corresponding components together. For example, to add vectors v = [v1, v2, ..., vn] and u = [u1, u2, ..., un], the result would be v + u = [v1 + u1, v2 + u2, ..., vn + un].

Scalar Multiplication:

Multiplying a vector by a scalar (a single number) involves multiplying each component of the vector by that scalar. For example, if α is a scalar and v = [v1, v2, ..., vn], then αv = [αv1, αv2, ..., αvn].

how do you find the dot product and convex combination?

Dot Product:

The dot product of two vectors is a scalar value calculated by multiplying corresponding components of the vectors and summing the results. For vectors v = [v1, v2, ..., vn] and u = [u1, u2, ..., un], the dot product is v ⋅ u = v1u1 + v2u2 + ... + vnun.

Convex Combination:

A convex combination of two vectors involves combining them with scalar weights such that the sum of the weights is 1. For example, given vectors v and u, their convex combination βv + (1 - β)u for 0 ≤ β ≤ 1 lies on the line segment connecting v and u.

how do you find the angle between vectors?

Angle Between Vectors:

The angle between two vectors can be calculated using the dot product and the magnitudes of the vectors. The formula is θ = arccos((v ⋅ u) / (||v|| ||u||)), where θ is the angle between vectors v and u, and ||v|| and ||u|| are the magnitudes of v and u, respectively.

Static Data Structure Advantages and disadvantages

Memory allocation Is fixed meaning there will be no issue of adding and removing items

No risk of overflow or underflow

Can be inefficient if not all the memory slots are utilised

Dynamic data structure advantages and disadvantages?

Makes efficient use of memory as because the data structure only uses as much memory as it needs

Run the risk of overflow or underflow

They are harder to program as the code needs to keep track of the size and location at all times

what are linear, circular and priority queues?

Priority Queue:

A priority queue is an abstract data type similar to a regular queue, but each element has an associated priority. Elements with higher priority are dequeued before elements with lower priority, regardless of the order in which they were added.

Circular Queue:

A circular queue is a data structure that operates like a regular queue but with a fixed size. When the queue is full, adding new elements overwrites the oldest elements in the queue, allowing continuous use of the available space. it has front and rear pointers.

Linear Queue:

A linear queue, also known as a standard queue, is a basic queue data structure where elements are added at one end (rear) and removed from the other end (front). It follows the FIFO (First-In-First-Out) principle, meaning that the first element added to the queue is the first one to be removed.

What are the types of graphs?

Undirected Graph:

Directed Graph:

Unweighted Graph:

Weighted Graph:

What is a static data structure?

memory is allocated when program is written. Fixed in size

What is a dynamic data structure

Memory allocated to the program when needed. Not fixed in size