We must remember that programs can be defined pretty much as `data structures + algorithms`. As we conclude this exploration we'll be discussing Searching algorithms and Dynamic Programming.

# On CS Algorithms: Chapter II

We must remember that programs can be defined pretty much as `data structures + algorithms`. As we conclude this exploration we'll be discussing Searching algorithms and Dynamic Programming.

# Searching + Traversal, BFS, DFS

• Searching + Traversal
• Breadth-first search (BFS), Depth-first search (DFS)

Searching is super useful:

• How computers/software can search so fast? Some strategies

• Linear Search
• Binary Search
• BFS
• DFS

## Linear / Sequential Search

• Find target value within a list.
• Like loop through arrays to find items.

• Check one-by-one.
• Best case `O(1)` and worst case check every single item `O(n)`
• Some JS strategies using linear:
``````var beasts = ['Centaur', 'Godzilla'];

// ALL are linear

beasts.indexOf('Godzilla');

beasts.findIndex(function(item){
return item === 'Godzilla';
});

// return item instead of index
beasts.find(function(item){
return item === 'Godzilla';
})

// true / false
beasts.includes('Godzilla')
``````

We can't use this on Google or Facebook, since it will cost time.

## Binary Search

Good on sorted lists. E.g. you're looking for 34 and list is sorted: 1, 4, 5, 9, 34, 45

Instead of checking everything you can do binary search:

• You can start in middle of list:

• Is 9 higher than 34? NO. Then discard to left.
• Go to middle of group again and do comparison.
• If it's sorted we can do better than O(n), creating a binary search tree. Data complexity since its a tree then it gives great storage too.
• Divide and conquer too.
• Binary search has lookup method by implementing trees as we saw on tree DS.
• This has `O(log n)`.
• But sometimes we need to traverse all nodes, there are other strategies for that.

## Traversal - Graph + Tree Traversals

Sometimes we want to add color property to all nodes. Traversals is like visiting every node.

• How can we traverse a Tree / Graph?

• With Breadth-first search (BFS), Depth-first search (DFS).
• Both have `O(n)`.
• Main benefit we don't put them on Arrays or Hash Tables is order and good O(log n) instead of O(n).
• Trees / Graphs are used a lot in traversal.

## Breadth-first search (BFS) & Depth-first search (DFS)

### BFS & DFS Intro

• BFS:

• Start with root node and move left to right across second, third level, and so on.
• Until you find node you're looking OR tree ends.
• BFS uses more memory b/c it tracks child nodes. So there are implications
• DFS:

• Follows one branch until is on last leave then moves forward checking unexplored children and branches.
• Lower memory requirement. Don't need to store all child pointers.
• So until it hits dead end then moves.
• BFS / DFS:
``````//OUR TREE
//     9
//  4     20
//1  6  15  170

// BFS: Visits all levels and outputs a list as it finds what it needs
// [9,4,20,1,6,15,17]

// DFS: List is different
// [9,4,1,6,20, 15,17]
``````

### BFS vs DFS

BFS is like water from top to down. DFS is like lines.

When to use BFS or DFS? Time complexity is same for both `O(n)`

• BFS:

• Good for finding shortest path. As it checks closer nodes.
• If you have additional info and know where the node is, use BFS.
• DFS:

• When you know node is in lower level then use DFS.
• Ask the question does the path exist
• Good: Less memory
• Bad:** it can get slow if tree is very deep not very good finding shortest path**
• Good Resource.

## Common Interview Questions BFS vs DFS

Study to see how you explain to interviewer

1. If you know a solution is NOT far from the root of the tree:

• BFS - starts searching closest nodes first.
2. If the tree is VERY deep and solutions are rare,

• BFS (DFS will take long time. )
3. If the tree is very wide:

• DFS (BFS will need too much memory as it has to keeps track of all the nodes)
4. If solutions are frequent but located DEEP in the tree

• DFS
5. determining whether a path exists between two nodes

• DFS
6. Finding the shortest path

• BFS

## Coding BFS & DFS

• Code Here.
• Uses a queue array
• Usually is done with iteration.

### Depth-first search - Exercises

• Code here.
• stack DS used here as it is Recursion. Height of tree will tell how much memory, memory consumption will depend on that.
• preOrder: from parent
• inOrder: order of nodes
• postOrder: order from trees at the bottom
• Play with code and console log to see how it inputs
• main difference is the order you get output
• depending on your needs you might implement one or the other
• You just learned how to traverse through tree try to implement in a graph!

### Validate a BST - Interview Qs

• A very common question you will get asked in an interview is how to validate a binary search tree! Hint, you want to use BFS for this.
• Try it here.

### Graph Traversals

• Tree traversal will be the same as Graph traversal. Trees are a type of graphs.
• Graphs model real life, like recommendation engine (items related) using like BFS. Facebook what type of friend request or LinkedIn connection with DFS.
• See it in action

Remember

• DFS is for shortest path. Closest to our node. Related items on Amazon, closest connections.
• DFS check if it exists. We can go very deep very fast.
• BFS in Graphs:

• What's the closest node to 0? BFS is very good as it looks closest nodes first.
• DFS in Graphs:

• Great for solving a maze. Because it goes deep then backtracks to solve the puzzle until finds exit.
• Idea of backtracking after dead end is just recursion.
• It answers does the path exist?
• If very deep branch can get very slow. Needs to keep track of all the functions on the stack.

## Dijkstra + Bellman-Ford Algorithms

• In interview you'll probably don't implement them
• BFS doesn't care about weight. So doesn't take to account weighted graphs.
• Dijkstra / Bellman-Ford Algorithms:

• Find the shortest path between two nodes on a weighted graph.
• Bellman can accommodate negative weights and Dijkstra doesn't.
• Dijkstra is faster than Bellman's (worst case is O(n^2)).

In an Interview:

• These algorithms are very complex
• Know that they exist and how to use them.
• If you see a weighted graph and asked to find best algorithm:

• BFS can't be used because is weighted
• Negative weights? If YES, Bellman. If NO, Dijkstra.

## Searching + Traversal Review

• Searching and Traversal are one of the most popular algorithms.
• Learned about how to traverse tree/graph.
• Now we're better to equipped to answer questions.
• Review the Technical Interview Mind Map.
• More here.

## Dynamic Programming (DP)

• DP is just optimization technique using cache. If you can cache then you can do DP. So its just a buzz word a lot of times.
• DP solves problems by breaking it down into sub problems, storing solutions in case those sub problems arise.
• DP

• Divide and Conquer + Memoization (cache)

## Memoization

• Caching is a way to store values that you can use later. Like a backpack that holds items you need.
• Memoization is a specific caching we use in our programs.

Memoization example

``````function add80(n) {
return n + 80
}

``````

What if this operation took a long time? Can we optimize it with memoization?

``````function add80(n) {
return n + 80
}

let c = {}

if (n in cache) {
//O(1)
return cache[n]
} else {
cache[n] = n + 80
return cache[n]
}
}
``````

What is then memoization?

• Caches return value based on parameters. If param of function doesn't change then its memoized then it will return cache version. If parameter changes then calculates as usual.
• So its a way to remember a solution to a problem so you don't have to calculate again.

### Closures in Memoization

Patterns in DP:

``````function memoAdd80() {
let cache = {}
//closure returns a function
return function(n) {
if (n in cache) {
//O(1)
return cache[n]
} else {
cache[n] = n + 80
return cache[n]
}
}
}

console.log(1, memoized(6))
// console.log(cache)
// console.log('-----------')
console.log(2, memoized(6))
``````
• Closures return a fn inside a fn
• Because of closure we can avoid global scope and access cache.

### Fibonacci and DP (caching)

Remember recursion example.

``````let calculations = 0
function fib(n) {
calculations++
if (n < 1) {
return n
}

return fib(n-1) + fib(n-2)
}

fib(6)
//will take a long time
// fib(30)
``````
• Remember this is pretty bad! O(2^n). We'll never want to implement this in real life.

• This because we repeat a lot of calculations.
• Can we fix this with caching (DP)? Reduce it to O(n)

• Yes we can because the solution is optimal and we do the same.
• We can actually return a memoized version with O(1) and use the cached version.

Solving fibonacci. See below or here.

Note: we increased the space complexity with memoization.

## Assess when to use DP (caching / memoization)

1. Can it be divided into subproblem. Problem broken down into smaller problems.
2. Recursive solution
3. Are there repetitive sub-problems?

• Same calculation over and over? we can memoize the problem!
4. Memoize sub-problems
5. Implement caching! and save a lot of calculations!

## Interview Questions: Dynamic Programming

Here are some popular Dynamic Programming Questions (see if you can notice the pattern):

## Review of DP

• All you need is to remember the pattern of saving a cache variable and use closures to return a function within a function.
• If there's repeated calculation then get the memoized result.
• Memoized version has more space complexity, so this tradeoff is necessary.
• Other way to incorporate DP is bottom up approach.
• This one avoids recursion. Starts from simple to higher solutions.
• This one is harder to know how/when to use
• Interview is unlikely that they will ask you to implement both methods.
• In short memoization help us to avoid having to do repeated tasks. If you can implement this you're on your way to become a great engineer.