Fundamentals of Algorithms (C3)

Question 1

Describe Depth-first searches

Answer 1

• They use a stack, and are used for navigating mazes.
• Start on a node, go the next adjacent node based on alphabetic order.
• Add each node you visit to a stack.
• Once there are no adjacent nodes, pop the top value from the stack, and visit the new top value.
• Repeat until you reach the end.

Question 2

Describe Breadth-first searches

Answer 2

• These use queues, where each node is visited and added to the queue.
• The next node is taken from the end (so the first one in), as opposed from the top like a stack.
• So essentially same as depth first, but you look at the BOTTOM of the stack (a queue).

Question 3

Compare depth first and breadth first searches

Answer 3

• Breadth first uses queues, depth first uses queues.
• Breadth first better nodes are closer to starting node, depth first better when solutions further away from source.
• Breadth first worse for decision-making trees.

Question 4

Describe pre, in, and post order traversal of a tree.

Answer 4

• Pre (node-left-right): Visit root, left subtree, then right subtree.
• In (left-node-right): Traverse left subtree, visit root, traverse right subtree. (add from bottom up)
• In (left-right-node): Traverse left subtree, traverse right subtree, visit node. (add from bottom up)

Question 5

Uses of RPN

Answer 5

• Expressions are simpler for computers to evaluate using a stack.
• Eliminates the need for brackets in sub-expressions.

Question 6

How to make bubble sort more efficient?

Answer 6

• Add variable set to true if a swap is made each pass, and change the outer loop so it only runs if the flag variable is set to true.
• After the inner loop, subtract 1 from N

Question 7

What does * mean in regex?

Answer 7

Zero or more

Question 8

What does ? mean in regex?

Answer 8

Zero or one