Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

*M AMBI > 7 | Data structures / graphs > Flashcards

7 | Data structures / graphs Flashcards

1
Q

Definition: Data Structure

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Definition: Array

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Name an advantage of arrays

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Name a disadvantage of arrays

A

no dynamic value modification (fixed number of items, of same type)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the algorithm for initialising an array? what is the time complexity?

A

for i in 1 to n do:
tab(i) <- 0

time: cn, is in Theta(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the algorithm for finding the minimum of an array? what is the time complexity?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the algorithm for moving elements (when inserting a new element into an array)? what is the time complexity?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Stack

Definition?

A

Stack – data structure in which items are added to and
subsequently removed from the structure on a last-in-first-out
(LIFO) basis

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Stack

Operations on a stack?

A

push, pop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Stack

Push?

A

Add an item x to the stack (push)

counter ← counter + 1
stack[counter] ← x

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Stack

Pop?

A

Remove an item from the stack (pop)

𝑥 ← stack[counter]
counter ← counter - 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Stack: 10, 3, 5

what happens when you pop, pop, push, pop, pop ?

A

–> you have an empty stack

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Stack

implementation?

A

Implemented by an array whose index runs from 1 to the
maximum number of elements allowed along with a counter

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Queue

Definition?

A

Queue – data structure in which items are added and removed
on a first-in-first-out (FIFO) basis

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Queue

Operations?

A

Add an item to the queue (enqueue)
Remove an item from the queue (dequeue)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Stacks and Queues

Disadvantages?

A
  • Maximum elements allowed should be known a priori
  • Too little, will affect the performance
  • Too many, will waste resources
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Record

Definition?

A

Record – data structure comprised a fixed number of items,
called fields, that are possibly of different types

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Two-dimensional array

Reading and modifying a value in ____ time

A

Reading and modifying a value in constant time

since the address of any given element can be
determined in constant time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Record

Access to the fields?

A

Access to the fields (dot notation) for Jeanne
Jeanne.name, Jeanne.age

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Record

pointers

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

List

Definition?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

List

An item of a list is called a ____.

A

An item of a list is called a node.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

List

Two types of implementation?

A

List can be implemented

as an array

or as with use of pointers and records (for the nodes)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

List

implemented as an array?

A

List can be implemented as an array (of integers)

type list = record
counter: 0 . . 𝑚𝑎𝑥𝑙𝑒𝑛𝑔𝑡ℎ
value: array [1. . maxlength] of integers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

List

implemented with use of pointers and records?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

List

different implementations - determining the kth item?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

List

different implementations - reserve storage a priori?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

List

different implementations - inserting an item after the kth item?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

List

Implementation with array + counter vs with pointers and nodes

what do we gain / lose?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Graphs

Informal definition?

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Graphs

Formal definition?

A

A graph is a pair 𝐺 = (𝑉, 𝐸) , such that 𝐸 ⊆ {{𝑢, 𝑣}|𝑢, 𝑣 ∈ 𝑉}.

We refer to 𝑉 as a set of nodes (or vertices) and 𝐸 as a set of edges.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Graphs

If 𝑒 = {𝑢, 𝑣} is an edge, then:

𝑢 and 𝑣 ________ 𝑒

A

are incident with

33
Q

Graphs

If 𝑒 = {𝑢, 𝑣} is an edge, then:

𝑒 ______ 𝑢 and 𝑣.

A

is incident with
connects

(only different types can be incident!)

34
Q

Graphs

If 𝑒 = {𝑢, 𝑣} is an edge, then:

𝑢 and 𝑣 are ______

A

adjacent
neighbours

(only same type can be adjacent!)

35
Q

Graphs

The number of nodes will be denoted as

A

𝑛 = |𝑉(𝐺)|

36
Q

Graphs

The number of edges will be denoted as
𝑚 = |𝐸(𝐺)|

A

𝑚 = |𝐸(𝐺)|

37
Q

Graphs

simple graph?

A

A graph is called simple, if it does not contain multi-edges or loops.

Otherwise it is called a multi-graph

38
Q

Graphs

parallel edges?

A

Two edges 𝑒 and 𝑓 are called parallel, if they connect the same vertices.

Parallel edges form a multi-edge.

39
Q

Graphs

loop?

A

If an edge connects a vertex to itself (i.e. 𝑒 = {𝑣, 𝑣}) it is called a loop.

40
Q

Graphs

Directed graph?

A

(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__

41
Q

Graphs

Weighted directed graph?

A

A weighted directed graph is a pair 𝐺 = 𝑉, 𝐸 , such that 𝐸 ⊆
{(𝑢, 𝑣)|𝑢, 𝑣 ∈ 𝑉}, with a weight function 𝑤: 𝐸 → ℝ.

weight = distance, resource availability / capacity

42
Q

Graphs

How to represent a graph on a computer?

A

Three ways:

Adjacency matrix
incidence matrix
or adjacency list

43
Q

Graphs

Adjacency matrix - undirected graphs?

symmetrical?

A

𝐴[𝑢, 𝑣] = 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

44
Q

Graphs

Adjacency matrix - directed graphs?

symmetrical?

A

𝐴[𝑢, 𝑣] = 1 𝑖𝑓 (𝑢, 𝑣) ∈ 𝐸(𝐺)
𝐴[𝑢, 𝑣] = 0 𝑖𝑓 (𝑢, 𝑣) ∉ 𝐸(𝐺)

Adjacency matrix of an undirected graph may not be symmetrical

45
Q

Graphs

Incidence matrix - undirected graphs?

A

𝐴[𝑢,𝑒] = 1 𝑖𝑓 𝑢 ∈ 𝑒
𝐴[𝑢,𝑒] = 0 𝑖𝑓 𝑢 ∉ 𝑒

Edge weights can be considered (instead of 1).

46
Q

Graphs

Incidence matrix - directed graphs

A

𝐴[𝑢,𝑒] = −1 𝑖𝑓𝑒 = (𝑢, 𝑣)
𝐴[𝑢,𝑒] = 1 𝑖𝑓 𝑒 = (𝑣, 𝑢)
𝐴[𝑢,𝑒] = 0, 𝑢 ∉ 𝑒

47
Q

Graphs

incidence relation ?

A

between different types

node - edge

(incidence matrix allows you to represent more relationships
eg stoichiometric matrices in CMCN)

48
Q

Graphs

adjacence relation

A

between same type

eg

node - node
edge - edge

49
Q

Graphs

Advantage/disadvantage of matrix representation?

A

advantages:
- constant time to determine whether there is an edge between two nodes
- can directly see what neighbours are

disadvantages
- not dynamically changeable

50
Q

Graphs

Advantage/disadvantage of list representation?

A
  • 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
51
Q

Graphs

What is a weighted directed hypergraph

A

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}

52
Q

Graphs

How can you represent a hypergraph on a computer?

A

incidence matrix

(eg stoichiometric matrix in CMCN)

53
Q

Graphs

Walk - formal definition?

Closed if?

A

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 = 𝑣𝑘

54
Q

Graphs

Walk: can nodes and edges be repeated?

A

Yes

(in a path they cannot)

55
Q

Graphs

Path - formal definition?

A

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 = 𝑣𝑘

56
Q

Graphs

Path: can nodes and edges be repeated?

A

No
(except in a cycle - then first/last is the same)

If repetition –> a path but not a walk

57
Q

Graphs

minimal vs. minimum?

A

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)

58
Q

Graphs

How do you know if a graph is minimal?

A

check if removal of any object from the structure breaks the property in question

–> if so then it is minimal

59
Q

Graphs

  1. For some property, if you have the minimal, can you find the minimum?
  2. If you have the minimum, can you find the minimal?
A

Yes

No

60
Q

Graph

Connectedness?

A

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

61
Q

Graphs

what is a connected component?

relevant for what?

A

re connectedness:

connected component is a maximal connected
subgraph.

(relevant for minimum spanning trees)

62
Q

Graphs

Tree definition

A

A graph 𝐺 is a tree if it is connected and has no cycles.

Hence, a connected forest is a tree.

63
Q

Graphs

Forest

A

A graph 𝐺 is a forest if it has no cycles.

Hence, a connected forest is a tree.

64
Q

Graphs

rooted tree

A

A tree is called a rooted tree if one vertex has been
designated the root.

65
Q

Graphs

rooted tree:
- parent/child of a vertex (uniqueness?)

A
66
Q

Graphs

rooted tree:
- parent/child of a vertex (uniqueness?)

A
  • 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
67
Q

Graphs

rooted tree:
- leaf
- node
- ancestor

A
  • 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
68
Q

Graphs

Ways to represent a rooted tree on a computer

What are the two ways?

A

Two ways (↑ = a pointer)

type treenode1 = record
    value: 𝑖𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛
    eldestchild: ↑ treenode 1
    next-sibling: ↑ treenode 1
type treenode2 = record
    value: 𝑖𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛
    parent: ↑ treenode 2
69
Q

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 ?

A

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

70
Q

Graphs

Representation of binary and k-ary trees

A 
type binary-node = record
    value: 𝑖𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛
    left-child: ↑ binary-node
    right-child: ↑ binary-node
type k-ary-node = record
value: 𝑖𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛
child: array [1. . 𝑘] 𝑜𝑓 ↑ 𝑘-𝑎𝑟𝑦-node
71
Q

Graphs

Search tree definition

A

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

72
Q

Graphs

Search based on a search tree - algo?

A 
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)
73
Q

Graphs

Height of a tree?

A

Height of it’s root

74
Q

Graphs

Nodes: height, depth, level?

A
  • 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
75
Q

Graphs

special node in a binary tree?

A

Zoran: parent of only one child
(online: Only child of its parent)

76
Q

Graphs

essentially complete binary tree?

(Heap)

A

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

77
Q

Graphs

Heap definition?

A

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

78
Q

Graphs

essentially complete binary tree of height k:
- how many nodes on level i?
- how many nodes at most on level 0?

(Heap)

A
  • 2𝑘−𝑖 nodes on level 𝑖, 1 ≤ 𝑖 ≤ 𝑘
  • at most 2𝑘 nodes on level 0
79
Q

Graphs

essentially complete binary tree - relationship between k (height) and n (nodes)?

(Heap)

A

2𝑘 ≤ 𝑛 < 2𝑘+1

Therefore, 𝑘 ≤ log2𝑛 < 𝑘 + 1, i.e. 𝑘 = ⌊log2𝑛⌋

*M AMBI (16 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions