fundamentals of algorithms

Question 1

what are the two types of ways to traverse a graph

Answer 1

depth first

breadth first

Question 2

what is a graph

Answer 2

an abstract data type used to represent complex non linear relationships between objects using unordered set of nodes connected by edges

-

Question 3

describe depth first traversal

Answer 3

starts at root and follows one branch as far as it can go

-used to navigate mazes

Question 4

describe breadth first traversal

Answer 4

start at the root node and scan every connect node from left to right

-finds the shortest path of an unweighted graph

Question 5

what are the steps of depth first traversal

Answer 5

Visit the root node and push it onto the stack.

Traverse on of the sub tree

Visit each unvisited node in the sub tree and push them onto the stack

When you get to a node with no other connections pop it of the stack

If needed continue popping of nodes until you get to one connected to unvisited nodes

When all the nodes are visited the visited array will show the order of traversal

Question 6

what are the steps of breadth first traversal

Answer 6

Visit root node queue connected nodes

Visited= [A]

Queue=[B, D, E]

From right to left visit connected nodes

Dequeue each node as you visit its connected nodes

Enqueue connected nodes

Visited= [A,B]

Queue=[D, E,C]

Visited= [A,B,D]

Queue=[E,C ,F]

Question 7

what abstract data type is used for depth traversal

Answer 7

a stack

Question 8

what abstract data type is used for breadth traversal

Answer 8

a queue

Question 9

what are searching algorithms for

Answer 9

they are used to search for specific items in a data set

Question 10

what are 3 types of searching algorithms

Answer 10

linear search algorithm
binary search algorithm
binary tree search algorithm

Question 11

what is the time complexity of the linear search algorithm

Answer 11

O(n)

Question 12

what is the time complexity of binary search algorithm

Answer 12

O(logn)

Question 13

what is the time complexity of the binary tree search algorithm

Answer 13

O(logn)

Question 14

how does the linear search algorithm work

Answer 14

-Linear search works by inspecting every item in a list one by one until the desired item (the target) is found.

-If the target does not exist in the list, the algorithm will check every single item in the list
before finishing

Question 15

how does the binary search algorithm work

Answer 15

-The first step is to take the middle piece of data

-To find the midpoint of the data, add the highest position and the lowest position of the array being considered, and divide
by 2.

Question 16

what search algorithm is used for ordered lists

Answer 16

binary search algorithms

Question 17

what search algorithm is used for unordered lists

Answer 17

linear search algorithms

Question 18

how does the binary tree search algorithm work

Answer 18

they function the same as binary search algorithms but are just applied to trees

Question 19

what are sorting algorithms for

Answer 19

they are used to sort elements of an array into a specific order.

Question 20

what are the two types of sorting algorithms

Answer 20

bubble sort

merge sort

Question 21

what is the time complexity of the merge sort

Answer 21

O( n log n )

Question 22

what is the time complexity of the bubble sort

Answer 22

O(n^2)

Question 23

how does the bubble sort work

Answer 23

bubble sorts makes passes through the data and swaps adjacent items until no swaps can be performed

Question 24

how does the merge sort work

Answer 24

merge sorts split arrays into smaller lists and reform them using the divide and conquer method

Question 25

which sorting method is quicker

Answer 25

merge sort

Question 26

what is the purpose of the Dijkstra shortest path algorithm

Answer 26

to find the shortest path between a particular start node and all other nodes in a weighted graph