(W4) Greedy Algorithms

Question 1

What is a graph?

Answer 1

Encoding pairwise relationships among a set of objects

A graph consists of vertices and edges.

Question 2

Define vertex or node in the context of a graph.

Answer 2

Object in the graph

Vertices are the fundamental units or points in a graph.

Question 3

What is an edge in a graph?

Answer 3

Line that connects two vertices

Edges represent the relationships between vertices.

Question 4

What is the formal notation for a graph?

Answer 4

graph G = (V, E)

Where V is a set of vertices and E is a set of edges.

Question 5

How is an edge represented in formal notation?

Answer 5

edge e = (u, v)

Where u and v are two vertices.

Question 6

What characterizes undirected graphs?

Answer 6

(u, v) = (v, u)

There is no sense of direction in undirected graphs.

Question 7

What is a directed graph?

Answer 7

(u, v) is from u to v

The direction matters in directed graphs.

Question 8

What are weighted edges?

Answer 8

Edges that have an associated weight w

The weight can represent cost, distance, or any other metric.

Question 9

Define a simple graph.

Answer 9

Does not have loops and does not contain multiple edges between the same pair of nodes

Simple graphs have unique edges between pairs of vertices.

Question 10

What is a connected graph?

Answer 10

Connected graphs have all vertices part of a single connected component.

Any node can find a path to any other node

Question 11

What defines a connected component in a graph?

Answer 11

Subgraph in which each pair of nodes is connected via a path

Each connected component contains nodes that can reach one another.

Question 12

Describe an adjacency matrix for unweighted graphs.

Answer 12

Create a V x V matrix M and store the weight at M[i][j] if an edge exists

It represents the presence of edges using a matrix.

Question 13

What is the space complexity of an adjacency matrix?

Answer 13

O(V²)

This is regardless of the number of edges.

Question 14

How do you check if an edge exists in an adjacency matrix?

Answer 14

O(1)
Checking for the presence of an edge is constant time.

Question 15

Describe an adjacency list for unweighted graphs.

Answer 15

Create an array of size V, storing adjacent vertices in V[i]

This representation is efficient for sparse graphs.

Question 16

What is the space complexity of an adjacency list?

Answer 16

O(V + E)

This accounts for both vertices and edges.

Question 17

What is the time complexity for checking if a particular edge exists in an adjacency list?

Answer 17

O(log V)
If the list is sorted

Question 18

What is the time complexity for retrieving all adjacent vertices on a given vertex in an adjacency list?

Answer 18

O(X)

Where X is the number of adjacent vertices.

Question 19

What is the main characteristic of Breadth-First Search (BFS)?

Answer 19

Traverses the graph uniformly from the source vertex.

Note - it doesn’t revisit vertex

Question 20

In BFS, how are vertices visited in relation to their distance from the source?

Answer 20

All vertices that are k edges away from the source vertex are visited before vertices k+1 edges away.

Question 21

What is the BFS algorithm

Answer 21

Create a queue - insert the starting node
Create a visited array - mark the start as visisted

While the queue is not empty:
1. get the first vertex from the queue
2. relax the edges - so for each edge
- mark the end as visited, add the end vertex to the queue

Question 22

What is the time complexity of the BFS algorithm?

Answer 22

O(V + E) if using adjancey list
O(V^2) if using adjancey matrix

Question 23

What is the space complexity of the BFS algorithm?

Answer 23

O(V + E)

Question 24

What is the main characteristic of Depth-First Search (DFS)?

Answer 24

Traverses the graph as deeply as possible, then backtracks.

Note - it doesn’t revisit vertex

Question 25

What is the DFS algorithm?

Answer 25

Initialize a 'visited' data structure add the initial vertex loop thru each neighbour in the graph: 1. if the neighbour has not been visited -> recursive call from that neighbour

Question 26

What is the time complexity of the DFS algorithm?

Answer 26

O(V + E)

Question 27

What is the space complexity of the DFS algorithm?

Answer 27

O(V + E) for adjacency list O(V^2) for adjacency matirx (V iterations, indexing over V possible edges)

Question 28

What does DAG stand for?

Answer 28

Directed Acyclic Graph

Question 29

What are some practical examples of a Directed Acyclic Graph (DAG)?

Answer 29

* Subtasks of a project which must finish before other projects * Relationship between subjects for degrees (i.e. pre-reqs) * People genealogy - x is an ancestor of * Power sets

Question 30

In a DAG, how is the order of vertices defined?

Answer 30

A < B if A -> B

Question 31

What does it mean if some vertices in a DAG are incomparable?

Answer 31

Cannot know the order of B and C.

Question 32

What is a topological order in a DAG?

Answer 32

Permutation of the vertices such that for every directed edge u -> v, u appears before v.

Question 33

What is the time complexity for DFS when used for topological sort?

Answer 33

O(V + E)

Question 34

What is the space complexity for DFS when used for topological sort?

Answer 34

Probably O(V + E), but requires storage for the vertex.

Question 35

What can 2-coloring also be used to represent

Answer 35

Bipartite Graphs Note - the number of 2-coloring sets is 2 ^ connected components

Question 36

How to find connected components in an unweighted undirected graph

Answer 36

Observe the fact that a DFS call from a random vertex will reach every vertex in the component so keep calling DFS on non-visited nodes, and each DFS call, you will get a different component

Question 37

Finding cycles in undirected graphs (+ why doesn't this approach work in directed graphs)

Answer 37

Keep track of nodes visited. 1. perform a DFS on unvisited nodes 2. if you find a path to a node that has been visited, then you know there is a cycle (note - you'll need to keep a reference to the previous node so that you don't travel from a -> b, and then go back to a and consider it a cycle) Issue with directed graphs - when there are two paths to the same node, it will detect it as a cycle

Question 38

Finding cycles in directed graphs

Answer 38

Requires a modification to the previous example Key Idea: only mark a loop when you manage to reach the starting node (for that DFS) Keep a status array -> 3x values, unvisited, active, inactive Then for each unvisited node: mark it as an active node, do dfs, and for each node, check if it's 'active'. when you finish DFS mark the node as inactive BFS is more clunky - not as easy to keep track of previous nodes

Question 39

Finding the shortest cycle in a directed graph

Answer 39

Trick - use BFS (why? because you want to find the shortest distance back to the source node by edges, so BFS will spread out and find that, where DFS may not) Otherwise - you also want to make sure you start from every possible source node - to ensure you find the shortest path O(V(V+E))

Question 40

BFS with multiple sources?

Answer 40

Set all sources to equal 0. BFS will then just find the shortest path to each node, and will ignore longer paths from other sources

Question 41

Find connected components in an undirected graph that are cycles

Answer 41

Important trick - the degree at every node should be 2 (as otherwise it's not a full cycle) otherwise - check all non visited nodes, perform DFS, and for each confirmed cycle - increase a counter

Question 42

how to calculate height of graph

Answer 42

the number of edges between start and end node