Brainscape's Knowledge GenomeTM

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


See full index

Computer Science > Fundamentals of Algorithms > Flashcards

Fundamentals of Algorithms Flashcards

1
Q

What is depth-first traversal of graphs?

A

Explores the graph as far a possible, then backtracking to visit unvisited nodes.

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

How is depth-first graph traversal implemented?

A

Using a recursive algorithm.
Using stacks , when a node is visited it is placed on the stack and if there are no more nodes attached to them they are popped off the stack.

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

What are the uses of depth-first graph traversals?

A

Finding a route between two nodes
Exploring a maze.

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

What is breadth-first graph traversal?

A

Visits to nodes closest to the starting point first.

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

How are breadth-first graph traversals implemented?

A

Queues keep track of the nodes to visit.

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

What are the uses of breadth-first graph traversals?

A

Social and peer-to-peer networks.

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

What is pre-order traversal of a binary tree?

A

Root
Left
Right

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

What is in-order traversal of a binary tree?

A

Left
Root
Right

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

What is post-order traversal of a binary tree?

A

Left
Right
Root

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

What does the in-order traversal of binary tree produce?

A

Alphabetical order

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

What does the post-order traversal of binary tree produce?

A

Reverse Polish Notation

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

What is recursion?

A

The process of calling a function from within itself.

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

What is the base/terminating case of recursion?

A

It defines the point at which the recursive function will stop calling itself.

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

What is Dijkstra’s shortest path algorithm?

A

An algorithm that calculates the shortest distance between two points.

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

What is Dijkstra’s shortest path algorithm used for in terms of graphs?

A

Used to calculate the shortest path between the starting node and all other nodes on weighted graphs.

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

What is Dijkstra’s shortest path algorithm used for?

A

Network routing
Packet switching
GPS

17
Q

How can weighted graphs be represented?

A

With two dimensional arrays.

18
Q

What is a linear search?

A

A search algorithm that looks through data one item at a time sequentially, until it finds the item being searched for or when it reaches the end of the list.

19
Q

What are the advantages of linear searches?

A

Simple to implement
Works with unordered lists.

20
Q

What are the disadvantages of linear searches?

A

Inefficient
Depends on the size of the dataset and where the item being searched for it located.

21
Q

What are is a binary search?

A

It compares the item being searched for with the middle item and then splits the dataset in half, depending on if the item is less than or greater than. This repeats until the item it’s looking for is located.

22
Q

What are the advantages of binary searches?

A

More efficient
Quicker

23
Q

What are the disadvantages of binary searches?

A

Complex to implement
Only works for ordered lists.

24
Q

What is infix notation?

A

An expression with the operators within the operands.

25
Q

What is prefix notation?

A

An expression with the operators before the operands.

26
Q

What is postfix notation?

A

An expression with the operators after the operands.

27
Q

What is an operator?

A

A mathematical process within an expression.

28
Q

What is an operand?

A

A value within an expression.

29
Q

What is Reverse Polish Notation?

A

Postfix notation
Simplifying mathematical expressions, eliminating the need for brackets.

30
Q

How is Reverse Polish Notation implemented?

A

Using a stack, operands are pushed onto the stack and when there is an operator the result is calculated, replacing the expression.

31
Q

What notation is in-order binary tree traversal?

A

Infix notation

32
Q

What notation is post-order binary tree traversal?

A

Postfix notation (RPN)

33
Q

What notation is pre-order binary tree traversal?

A

Prefix notation (Polish notation).

34
Q

What is bubble sort?

A

It compares the first two items, if the first item is bigger than the second they are swapped, this process is repeated (a pass) until the list is sorted, which is when no swaps are made.

35
Q

What are the advantages and disadvantages of bubble sort?

A

Adv - easy to implement
Uses a small amount of memory.
Dis - inefficient with large lists

36
Q

What is merge sort?

A

“Divide and conquer” algorithm which break the list down into sub-list, until each sub-list only contains one item, it then merges all the sub-lists together, ordering them as it goes, producing a sorted list.

37
Q

What are the advantages and disadvantages of merge sort?

A

Adv- more efficient
Quicker for large datasets
Dis - uses more memory.

Computer Science (10 decks)

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