UNIT 6: Algorithms

Binary Search

Binary Search:

* main idea is to track the current range of reasonable guesses
* EX: You must guess a number between 1-100, you’ve already guessed 10 and your partner said the number was higher so you can conclude that numbers between 10-100 are the only reasonable guesses, but anything below 10 is an unreasonable guess. Now you’ve guessed the number is 64, and your partner has said the number is lower than that. So you can conclude that a number between 10-64 are the only reasonable guesses.
* To quickly get to the correct number, choose the middle number between both numbers within the reasonable numbers, the middle number of 10-64 can be given by doing (10+64)/2 and the answer is 37. So you guess the number is 37, whether the actual number is greater or less than 37 you’ve halved the size of the range.

\
Step by step description into using binary search to play the guessing game: for the guessing game, keep track of the set of reasonable guesses


1. Let the current minimum reasonable guess be variable min = 1 & the current maximum reasonable guess be variable max = n
2. Guess the average of max & min, if its a decimal round it down to an integer
3. If guessed correctly, then stop.
4. If the guess was too low, set min to be one larger than the guess
5. If the guess was too high, set max to be one smaller than the guess To understand how many steps go into a certain amount of inputs:
6. Find how many bits it takes to represent the input. If there’s 1 input then there’s 1 step because it takes only 1 bit to represent the input.
7. Binary search algorithm grows at a slow rate because of this process
8. for finding an item from a sorted list of items as the data must be sorted (or binary search cant work) and reduces the number of checks by half to search for a desired value.

\*remember: the steps r also binary representations of its corresponding input

Terms matching with Binary Search:

* Logarithmic- procedure used for Binary Search, starts at the middle and removes half of the data, repeating the process until the desired value is found or all elements have been eliminated
* Class birthdays- every student in class lines up, person with a birthday right in the middle of everyones is chosen, eliminate half the data be it the numbers greater or less than that student’s bday, continue the process until the actual date is exacted
* Sorted Data- how data is sorted, not in a definitive way, depends on the problem

\
Efficiency of Binary Search:

* Binary Search is efficient as the number of steps it takes to complete an algorithm vs its matching input is much smaller. Why? The number of bits to represent a number is smaller than the number, and drastically smaller than a large number. EX: It takes three bits to represent 10 but 4 bits to represent 15, comparing both, 4 bits is much less than 3 to its corresponding number.

Linear Search

Linear Search:

* A search algorithm which checks each element of a list in order until the desired value is found or all the elements in the list have been checked.


1. The number of inputs is equal to the number of steps so the input and steps grow at the same rate.
2. EX: 7 inputs in a linear search has 7 steps, versus binary search which has 3 steps for 3 inputs because 3 bits represent 7 (111 is 1,2,4 and 1+2+4=7)
3. In a linear search, each element in the list is searched one after the other in a sequential manner until it is found in the list. (EX: checks 1 then 2 then 3 etc… until it gets to the desired number)
4. linear does not require an ordered list Linear search grows much faster than binary BUT Binary search is much faster than Linear search in finding the desired number.

Terms matching with Linear Search:

* single raffle

\
Efficiency of Linear Search:

* Not very efficient as it must go at the same pace which is not convenient

Polynomial Search

Polynomial Search:

* For checking every combo of pairs


1. (n^2-n)/2=y


1. n reps the number of items in a list, so its the tickets
2. y is the number of checks
3. EX: list is 1,2,3,4,5 and the combo of all pairs is

1, 2
1, 3
1, 4
1, 5
2, 3
2, 4
2, 5
3, 4
3, 5
4, 5

Terms matching with Polynomial Search:

* pair raffle (as polynomial search is meant for checking every combo of PAIRS)

\
Efficiency of Polynomial Search:

* Not as bad as exponential but still not reliable

Exponential Search

Exponential Search:

* For checking every combo of groups


1. (2^n)-1
2. n is the number of items in the list (tickets) and y is the tickets
3. EX: 2 tickets makes the formula (2^2)-1=y making y=3

\
Terms matching with Exponential Search:

* group raffle- (as exponential search is meant for checking every combo of GROUPS)
* unreasonable
* travelling salesman- speeds very fast in a short amount of time so its an unreasonable algorithm because it requires factorial solutions to get the desired number which takes a long time and has many values as viable numbers so finding the actual value is difficult and gets harder as it continues speeding.
* exponential solution: to find how many combo’s u can make from a set number of items if u took any amount (ex: four items being 1 2 3 4, u make one combo 1 2 3 and other combo’s cannot be ones with all three of those numbers but in different order, so 2 3 1 wouldn’t work but 3 4 1 would)
* factorial solutions- used for exponential algorithm, ex: number 5, then u do this problem 5 times 4 times 3 times 2 times 1

Efficiency of Exponential Search:

* Fast but unreliable as it gets unreasonably large extremely fast

Sequential/Parallel Computing

Sequential/Parallel Computing:

* Sequential- programs run in order, one command at a time
* Parallel- programs are broken into small pieces and some of them are run simultaneously; think of multiple people/computers completing the same task to minimize the time (more people/computers decreases the efficiency of each individual person/computer as adding more people/processors helps less the more you add and the speedup will reach a limit)

\
Terms matching with Sequential/Parallel Computing:

* Speedup- sorting cards; the time used to complete a task sequentially divided by the time to complete a task in parallel parallel time
* Speedup is NEVER equal to the number of processors. Sorting with 2 people doesn't give a speedup of 2. Sorting with 3 people doesn't give a speedup of 3. Because some portions are always still sequential, the benefits of adding more processors will go down. Some portions of your algorithm can’t be made parallel. Each additional processor helps a little less, and the speedup reaches a limit.
* Distributed Computing- programs run by multiple devices; ex: folding a home, cryptocurrency hackers

\
Efficiency of Sequential/Parallel Computing:

* Solutions that use sequential computing are not very efficient as you cannot cut corners bc the program goes step by step
* Solutions that use parallel computing can scale more effectively than solutions that use sequential computing.

Matching Graph of Algorithms

(curves/lines of Algorithms on a graph: shows the time it takes for algorithms run)

\#1 exponential

\#2 polynomial (U-Shaped)

\#3 linear

\#4 binary

Sequencing, Selection, Iteration

Sequencing- going step by step in order

Selection- if and else statements 

Iteration- repeat and loops

Problem vs Algorithm:

Algorithm is the solution to solve a problem

problem- general description of a task that can or cannot be solved w/ an algorithm

algorithm- finite set of instructions that accomplish a task

Efficiency

A measure of how many steps are needed to complete an algorithm 

Difference between Decidable and Undecidable Time

Reasonable time- **polynomial** efficiency or lower (constant, linear, square, cube, etc.) \\n

Unreasonable time- Algorithms with **exponential** or **factorial** efficiencies

Difference between Unreasonable and Undecidable:

Unreasonable- COULD but takes a long/absurd amount of calculations and time

Traveling salesperson, Kevin Bacon game, Wikipedia game

Undecidable- CANNOT, problem cant be calculated as it is an infinite loop (always capable of providing a correct yes or no answer)

Loop run forever?

Conway's Game of Life

Necklace- U start with 2 numbers, multiply it, next number in the line is the ones place =

Cheapest flight

Sorted data

Just how data is sorted, there isn’t one definitive way it is, and for binary search its an algorithm performed to detect the number faster