Fundamentals of algorithms & theory of computation

How does a breadth-first search work?

Start a root, scan every node connected and then continue scanning from left to right (utilising a queue)

how does a depth-first search work?

Start at root, follow a branch as far as it will go, then backtrack. (utilising a stack)

how does pre-order, in-order and post-order traversals work?

Pre-order Traversal:

In a pre-order traversal:

1. Visit the current node.

2. Recursively traverse the left subtree.

3. Recursively traverse the right subtree.

In-order Traversal:

In an in-order traversal:

1. Recursively traverse the left subtree.

2. Visit the current node.

3. Recursively traverse the right subtree.

Post-order Traversal:

In a post-order traversal:

1. Recursively traverse the left subtree.

2. Recursively traverse the right subtree.

3. Visit the current node.

advantages of RPN

1. No parentheses needed.

2. Simple evaluation with stacks.

3. Efficient for implementation.

4. Natural for stack-based systems.

5. Reduces need for intermediate results.

how to convert from Infix to RPN

1. Initialize an Empty Stack: We'll use a stack to keep track of operators and manage their precedence.

2. Scan the Infix Expression from Left to Right: For each token (operand or operator) in the infix expression:

   • If it's an operand, add it directly to the output.

   • If it's an operator:

     • While there are operators already on the stack with higher precedence (or equal precedence in the case of left-associative operators), pop them from the stack

how does a linear search work?

scan each item in a list 1 by 1

how does a binary search work?

divide the list into 2, check if the item is greater than or less than, repeat

what is Procedural abstraction

abstracting away the actual values used in any particular computation and replacing it with a formula

what is functional abstraction

Functional abstraction is the process of hiding the implementation details of a function and it builds up from a procedure

what is data abstraction?

Data abstraction is the process of hiding the complex implementation details and showing only the essential features.

what is problem abstraction

removing details from a problem until you can represent it in a way that is possible to solve.

what is problem decomposition

taking a big problem and breaking it down into smaller problems

what is composition

developing solutions by using pre-existing components which are proven to work

what is automation

taking physical world scenarios and using a computer to ease operations.