[UPenn] Expressing and Analyzing Algorithms

This lecture note is about Expressing and Analyzing Algorithms.

Please refer to the first lecture note below :

2022.09.08 - [CS Knowledge] - [UPenn] Computational Thinking for Problem Solving

Source: Penn Engineering

 

Linear Search and Binary Search

This work is making a bunch of comparisons, called 'Linear Search' with linear complexity, which cannot be the most efficient way to bring the outcome.

In linear search, we start with the first item and look at the next one, whereas in 'Binary Search', we start comparing the value in the middle of the list to the target, and if they are equal, then we have found the target and can stop looking. If the value in the middle of the list is greater than the target, remove the middle element and elements that are larger than it and repeat. If the value in the middle of the list is less than the target, remove the middle element and elements that are smaller than it and repeat. By using this method, we can save more time and spend fewer comparisons to get to the target. (Penn Engineering)

It is somehow better than the linear search. However, the binary search has logarithmic complexity, meaning that if we double the input size, the number of operations only increases by one.

There are two different algorithms.

 

Brute Force Algorithms

Brute force algorithms can be used for solving optimization problems.
• Try all possible solutions
• Identify the ones that solve the problem
• Determine the best one

 

Greedy Algorithms

Do the thing that seems best at the time
• Brute force: consider all possible solutions and choose the best one. It is optimized but cannot be the quickest.
• Greedy: make a decision that seems best right now and keep repeating
it until done. It is quick but cannot be optimized.

 

Source: Penn Engineering

 

The difference between Greedy and Brute force is whether to look through every possible solution or not. Each algorithm has pros and cons, so it is essential to use each in a good situation.

Moreover, depending on the case, all types of algorithms can be used in one flowchart.