Searching, Sorting, Graphs

Question 1

Two searching algorithms

Answer 1

• linear (or sequential) search

- binary search

Question 2

Sorting algorithms

Answer 2

• insertion sort

- quicksort

Question 3

Recursion

Answer 3

Calling a the function inside the function

Question 4

A graph is

Answer 4

• a collection of vertices

- connected by edges

Question 5

Order of a graph

Answer 5

Number is vertices it has

Question 6

Size of a graph

Answer 6

Number is edges the graph has

Question 7

Degree of vertex

Answer 7

Number of edges incident to that vertex

Question 8

Path

Answer 8

Is a sequence of vertices and edges (without repetition) that connects two vertices

Question 9

Length of path

Answer 9

The number of edges in the path

Question 10

Cycle

Answer 10

A path of min 1, starting and ending at the same vertex

Question 11

Connected graph

Answer 11

If every pair of vertices there exists at least one path

Question 12

Disconnected graph

Answer 12

Consists of at least two connected components

Question 13

Trees

Answer 13

• a connected graph with no cycles

- there exists only one path between any given two vertices

Question 14

Forest

Answer 14

Disconnected graph composed by multiple trees

Question 15

Directed graph or digraph

Answer 15

-is a graph whose edges have a direction

Question 16

Directed edges or arcs

Answer 16

Edges in a directed graph

Question 17

Directed path

Answer 17

Is a path following the direction of the edges

-the endpoints are usually referred to as the source and destination

Question 18

Depth first search

Answer 18

• can be used to find if a path exists between to vertices

- used to explore all vertices in a connected component of a graph, starting from a given source vertex v

Question 19

Tree edges or discovery edges

Answer 19

Edges used to perform the traversal

Question 20

Back edges

Answer 20

Edges connected that would take us back on an explored part of our path

Question 21

Breadth-first search

Answer 21

-to explore and backtrack easily, uses a queue instead of a stack

Question 22

Cross edge

Answer 22

Is an edge that would take is to the vertex who is not an ancestor and has been visited before

Question 23

Parent, ancestor, sibling

Answer 23

• parent: is the previous vertex that got to the other vertex
• ancestor: original one that is in the lineage
• siblings: share a common ancestor

Question 24

Weighted graphs

Answer 24

• used to represent the distance between two things

- also used to represent cost

Question 25

Dijkstra’s algorithm

Answer 25

Finds the shortest possible path to get to a certain vertex