7 | Data structures / graphs Flashcards
Definition: Data Structure
Data structure is a particular way of organizing and storing data in a computer so it can be accessed and modified efficiently.
Data structure
- collection of data values
- relationship among the values
- functions / operations which can be applied to the data
Definition: Array
Array β data structure consisting of a fixed number of items of the same types (items = elements) usually stored in contiguous storage cells.
Access to every element is obtained by specifying a single subscript or index.
Name an advantage of arrays
We can calculate the address of any given element in a
constant time
It takes time in the order of Ξ(1) to
* read a value of a single element
* change a value of a single element
Name a disadvantage of arrays
no dynamic value modification (fixed number of items, of same type)
What is the algorithm for initialising an array? what is the time complexity?
for i in 1 to n do:
tab(i) <- 0
time: cn, is in Theta(n)
What is the algorithm for finding the minimum of an array? what is the time complexity?
min = T(1)
for i in 1 to n do:
if min > T(i)
min = T(i)
time:
c_i + β(2<=i<=n) of c + c = 2c + (n-1)c β Ξ(n)
What is the algorithm for moving elements (when inserting a new element into an array)? what is the time complexity?
algorithm:
for i in n+1 to k+1
T(i) <- T(i-1)
T(k) <- a
time:
[β(k+1<= i<= n+1) of c ] + c
= [ (n+1) - (k+1) + 1)c + c
= (n+1)c + c
β Ξ(n)
Stack
Definition?
Stack β data structure in which items are added to and
subsequently removed from the structure on a last-in-first-out
(LIFO) basis
Stack
Operations on a stack?
push, pop
Stack
Push?
Add an item x to the stack (push)
counter β counter + 1
stack[counter] β x
Stack
Pop?
Remove an item from the stack (pop)
π₯ β stack[counter]
counter β counter - 1
Stack: 10, 3, 5
what happens when you pop, pop, push, pop, pop ?
β> you have an empty stack
Stack
implementation?
Implemented by an array whose index runs from 1 to the
maximum number of elements allowed along with a counter
Queue
Definition?
Queue β data structure in which items are added and removed
on a first-in-first-out (FIFO) basis
Queue
Operations?
Add an item to the queue (enqueue)
Remove an item from the queue (dequeue)
Stacks and Queues
Disadvantages?
- Maximum elements allowed should be known a priori
- Too little, will affect the performance
- Too many, will waste resources
Record
Definition?
Record β data structure comprised a fixed number of items,
called fields, that are possibly of different types
Two-dimensional array
Reading and modifying a value in ____ time
Reading and modifying a value in constant time
since the address of any given element can be
determined in constant time
Record
Access to the fields?
Access to the fields (dot notation) for Jeanne
Jeanne.name, Jeanne.age
Record
pointers
Record are commonly used in conjuction with pointers
type student = β person
says that student is a pointer to a record of type person
such a record can be created dynamically
student β new person
student β means the record that student points to
student β.name, student β.age are the fields
If a pointer has a value of nil, it does not point to any record
List
Definition?
List is a collection of items arranged in a certain order.
Unlike arrays and records, the number of items in a list is
usually not fixed and is not bounded a priori
List
An item of a list is called a ____.
An item of a list is called a node.
List
Two types of implementation?
List can be implemented
as an array
or as with use of pointers and records (for the nodes)
List
implemented as an array?
List can be implemented as an array (of integers)
type list = record
counter: 0 . . πππ₯πππππ‘β
value: array [1. . maxlength] of integers
List
implemented with use of pointers and records?
List can be implemented with use of pointers and records (for the nodes)
type list = β node
type node = record
value:integer
next: β node
Each node, except the last, points to its successor
The last has a value nil
List
different implementations - determining the kth item?
type list = record
counter: 0 . . πππ₯πππππ‘β
value: array [1. . maxlength] of integers
β> in constant time
type list = β node
type node = record
value:integer
next: β node
In time π(π) , due to the following of pointers
List
different implementations - reserve storage a priori?
type list = record
counter: 0 . . πππ₯πππππ‘β
value: array [1. . maxlength] of integers
β> yes
type list = β node
type node = record
value:integer
next: β node
β> No, it can grow and shrink dynamically
List
different implementations - inserting an item after the kth item?
Inserting an item after the k-th item
type list = record
counter: 0 . . πππ₯πππππ‘β
value: array [1. . maxlength] of integers
β> in time Ξ π
type list = β node
type node = record
value:integer
next: β node
β> In time π(1) , by copying and changing few fields
List
Implementation with array + counter vs with pointers and nodes
what do we gain / lose?
With nodes, pointers:
we gained dynamic memory allocation
Accessing: but we lost efficiency of accessing an element of a list: we need to traverse list to find the kth element
Insertion: much easier to insert a new element after kth element - only two operations - constant time operation
Graphs
Informal definition?
Informal: a graph (πΊ) is an abstract representation of a set of components (nodes/vertices) where some pairs of the components are connected by links (edges).
Graphs
Formal definition?
A graph is a pair πΊ = (π, πΈ) , such that πΈ β {{π’, π£}|π’, π£ β π}.
We refer to π as a set of nodes (or vertices) and πΈ as a set of edges.
Graphs
If π = {π’, π£} is an edge, then:
π’ and π£ ________ π
are incident with
Graphs
If π = {π’, π£} is an edge, then:
π ______ π’ and π£.
is incident with
connects
(only different types can be incident!)
Graphs
If π = {π’, π£} is an edge, then:
π’ and π£ are ______
adjacent
neighbours
(only same type can be adjacent!)
Graphs
The number of nodes will be denoted as
π = |π(πΊ)|
Graphs
The number of edges will be denoted as
π = |πΈ(πΊ)|
π = |πΈ(πΊ)|
Graphs
simple graph?
A graph is called simple, if it does not contain multi-edges or loops.
Otherwise it is called a multi-graph
Graphs
parallel edges?
Two edges π and π are called parallel, if they connect the same vertices.
Parallel edges form a multi-edge.
Graphs
loop?
If an edge connects a vertex to itself (i.e. π = {π£, π£}) it is called a loop.
Graphs
Directed graph?
(A directed graph is a pair πΊ = π, πΈ , such that πΈ β
{(π’, π£)|π’, π£ β π}. We refer to π as a set of nodes (or vertices)
and πΈ as a set of directed edges.)
__For the edge π = (π’, π£), π’ is the head and π£ is the tail__
Graphs
Weighted directed graph?
A weighted directed graph is a pair πΊ = π, πΈ , such that πΈ β
{(π’, π£)|π’, π£ β π}, with a weight function π€: πΈ β β.
weight = distance, resource availability / capacity
Graphs
How to represent a graph on a computer?
Three ways:
Adjacency matrix
incidence matrix
or adjacency list
Graphs
Adjacency matrix - undirected graphs?
symmetrical?
π΄[π’, π£] = 1 ππ (π’, π£) β πΈ(πΊ)
π΄[π’, π£] = 0 ππ (π’, π£) β πΈ(πΊ)
Constant time to check for presence of an edge between two nodes
Edge weights can be considered (instead of 1).
Adjacency matrix of an undirected graph is symmetric
Graphs
Adjacency matrix - directed graphs?
symmetrical?
π΄[π’, π£] = 1 ππ (π’, π£) β πΈ(πΊ)
π΄[π’, π£] = 0 ππ (π’, π£) β πΈ(πΊ)
Adjacency matrix of an undirected graph may not be symmetrical
Graphs
Incidence matrix - undirected graphs?
π΄[π’,π] = 1 ππ π’ β π
π΄[π’,π] = 0 ππ π’ β π
Edge weights can be considered (instead of 1).
Graphs
Incidence matrix - directed graphs
π΄[π’,π] = β1 πππ = (π’, π£)
π΄[π’,π] = 1 ππ π = (π£, π’)
π΄[π’,π] = 0, π’ β π
Graphs
incidence relation ?
between different types
node - edge
(incidence matrix allows you to represent more relationships
eg stoichiometric matrices in CMCN)
Graphs
adjacence relation
between same type
eg
node - node
edge - edge
Graphs
Advantage/disadvantage of matrix representation?
advantages:
- constant time to determine whether there is an edge between two nodes
- can directly see what neighbours are
disadvantages
- not dynamically changeable
Graphs
Advantage/disadvantage of list representation?
- you have to traverse through list in order to find a node in the list
- dynamic changes allowed
- Space required is quadratic in the number of nodes
- For sparse graphs (number of edges which grows linearly with the number of edges), list representation is space efficient
- Look-up of neighbours in constant time, but checking all neighbours requires investigation of an entire row
- All neighbours can be investigated in time smaller than π, but looking up neighbours is not in constant time
Graphs
What is a weighted directed hypergraph
a pair πΊ = (π, πΈ),
such that πΈ β (π,π) ,
π,π β π«(π),
with a weight function π€π: π β β
weight = resource demand / production
eg
π = {π£1, π£2, π£3, π£4, π£5}
π€({π£1, π£6}) = {β1, β2}
π€({π£4, π£7}) = {1,1}
Graphs
How can you represent a hypergraph on a computer?
incidence matrix
(eg stoichiometric matrix in CMCN)
Graphs
Walk - formal definition?
Closed if?
Let πΊ = (π, πΈ) be a simple graph.
A sequence π = (π£1, π1, π£2, β¦ ππβ1, π£π)
with π£π β π(πΊ) , 1 β€ π β€ π and
ππ = π£π, π£π+1 β πΈ(πΊ) , 1 β€ π β€ π β 1
is called a walk.
A walk is closed if π£1 = π£π
Graphs
Walk: can nodes and edges be repeated?
Yes
(in a path they cannot)
Graphs
Path - formal definition?
Let πΊ = (π, πΈ) be a simple graph.
A walk π = (π£1, π1, π£2, β¦ ππβ1, π£π)
is a path if
π£π β π£j, 1 β€ π, j β€ π, i β j
A path is a cycle if π£1 = π£π
Graphs
Path: can nodes and edges be repeated?
No
(except in a cycle - then first/last is the same)
If repetition β> a path but not a walk
Graphs
minimal vs. minimum?
minimal refers to subgraphs (or subsets)
minimum refers to cardinality (number of
nodes/edges)
A subgraph π» of πΊ is minimal with respect to a property π if π» satisfies π and there exists no strict subgraph π»β² of π» that also satisfies π.
(Analogously: maximal vs. maximum)
Graphs
How do you know if a graph is minimal?
check if removal of any object from the structure breaks the property in question
β> if so then it is minimal
Graphs
- For some property, if you have the minimal, can you find the minimum?
- If you have the minimum, can you find the minimal?
Yes
No
Graph
Connectedness?
Let πΊ = (π, πΈ) be a graph. Let πΊ is connected if for every
two nodes there exists a path between any two nodes π’ and π£ in πΊ
Connected component is a maximal connected
subgraph
Graphs
what is a connected component?
relevant for what?
re connectedness:
connected component is a maximal connected
subgraph.
(relevant for minimum spanning trees)
Graphs
Tree definition
A graph πΊ is a tree if it is connected and has no cycles.
Hence, a connected forest is a tree.
Graphs
Forest
A graph πΊ is a forest if it has no cycles.
Hence, a connected forest is a tree.
Graphs
rooted tree
A tree is called a rooted tree if one vertex has been
designated the root.
Graphs
rooted tree:
- parent/child of a vertex (uniqueness?)
Graphs
rooted tree:
- parent/child of a vertex (uniqueness?)
- the parent of a vertex is the vertex connected to it on the path to the root,
- every vertex except the root has a unique parent,
- a child of a vertex v is a vertex of which v is the parent
Graphs
rooted tree:
- leaf
- node
- ancestor
- a leaf is a vertex without children
- a node that is not a leaf is call internal
- Node u is an ancestor of v if it lies on the path from the root to v
Graphs
Ways to represent a rooted tree on a computer
What are the two ways?
Two ways (β = a pointer)
type treenode1 = record
value: ππππππππ‘πππ
eldestchild: β treenode 1
next-sibling: β treenode 1
type treenode2 = record
value: ππππππππ‘πππ
parent: β treenode 2
Graphs
Two qays to represent a rooted tree on a computer
type treenode1 = record
value: ππππππππ‘πππ
eldestchild, next-sibling: β treenode 1
type treenode2 = record
value: ππππππππ‘πππ
parent: β treenode 2
Advantages/disadvantages of 1/2 ?
1:
All nodes can be represented with the same record
Many operations are inefficient (e.g. finding a parent of a node)
2:
Very economical representation
Many operations are inefficient, unless they are applied to a node always going up the rooted tree
Graphs
Representation of binary and k-ary trees
type binary-node = record
value: ππππππππ‘πππ
left-child: β binary-node
right-child: β binary-node
type k-ary-node = record value: ππππππππ‘πππ child: array [1. . π] ππ β π-πππ¦-node
Graphs
Search tree definition
A binary tree where value contained in every internal node is both:
- greater than or equal to value in left child or any of childβs descendants
- smaller than or equal to the value in the right child or any of the childβs descendants
Graphs
Search based on a search tree - algo?
function search(x,r)
if r = nil then return nil #{x is not in the tree}
else if x = r β.value then return r
else if x < r β.value then return search(x, r β.left-child)
else return search(x, r β.right-child)Graphs
Height of a tree?
Height of itβs root
Graphs
Nodes: height, depth, level?
- Height of a node: number of edges in the longest path from the node to a leaf
- Depth of a node: number of edges in the path from the root to the node
- Level of a node: height of the root β depth of the nodes
Graphs
special node in a binary tree?
Zoran: parent of only one child
(online: Only child of its parent)
Graphs
essentially complete binary tree?
(Heap)
Binary tree is essentialy complete if:
- each internal node has exactly two children (possible exception of one special node)
- If there is a special node: situated on level 1, has a left but no right child
- Either all leaves are on level 0, or else they are on levels 0 and 1, and no leaf on level 1 is to the left of an internal node at the same level
Graphs
Heap definition?
Heap
- special type of a rooted tree
- essentially complete binary tree such that value
of any internal node is greater than or equal to the values of its children
- can be implemented efficiently with an array, without any explicit pointers
Graphs
essentially complete binary tree of height k:
- how many nodes on level i?
- how many nodes at most on level 0?
(Heap)
- 2πβπ nodes on level π, 1 β€ π β€ π
- at most 2π nodes on level 0
Graphs
essentially complete binary tree - relationship between k (height) and n (nodes)?
(Heap)
2π β€ π < 2π+1
Therefore, π β€ log2π < π + 1, i.e. π = βlog2πβ
