Rules of Dijkstra’s Algorithm Flashcards

1
Q

Rule 1 Dijkstra’s algorithm

A

We make the starting vertex our current vertex.

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

Rule 2 Dijkstra’s algorithm

A

We check all the vertices adjacent to the current vertex and calculate and record the weights from the starting vertex to all known locations.

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

Rule 3 Dijkstra’s algorithm

A

To determine the next current vertex, we find the cheapest unvisited known vertex that can be reached from our starting vertex.

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

Rule 4 Dijkstra’s algorithm

A

Repeat the first three steps until we have visited every vertex in the graph.

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

Data structures operations

A

Read, Search, Insert, Delete

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

Array Search Worst Case

A

N steps

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

Array Insertion Worst Case

A

N + 1 steps

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

Array Deletion Worst Case

A

N steps

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

Set Search Worst Case

A

N steps

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

Set Insertion Worst Case

A

2N + 1 steps

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

Set Deletion Worst Case

A

N steps

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

Ordered Arrays

A

Sorted

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

O(log N)

A

the Big O way of describing an algorithm that increases one step each time the data is doubled

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

Compaction

A

means throwing away duplicate keys in the log, and keeping only the most recent update for each key

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

Bubble Sort

A

O(N^2)

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

Selection Sort

17
Q

Insertion Sort

A

O(N^2) Better for average case scenarios where data is randomly sorted.

18
Q

linear search

19
Q

Constant search

20
Q

binary search

21
Q

LSM-Tree

A

Log-Structured Merge Tree

22
Q

B-Tree WAL

A

write-ahead log for recovery

23
Q

SSTable

A

Sorted String Table

24
Q

storage engine types

A

B-Tree and log-structured indexes

25
Vertex
The node in a graph database which holds information
26
Edge
The path between two vertices in a graph database
27
Kafka
has better throughput, built-in partitioning, replication and inherent fault-tolerance then traditional message broker
28
Point to Point Messaging System
In a point-to-point system, messages are persisted in a queue
29
Publish-Subscribe Messaging System
In the publish-subscribe system, messages are persisted in a topic
30
Dimension table
A Dimension Table is a table in a star schema of a data warehouse
31
Fact Table
A fact table is a table that contains the measures of interest. Ex: sales amount by each store, each day