Untitled
Fold the Video
The summary of MIT Algorithms MIT 6006 lecture
Goals:
A problem
A binary relationship between inputs ans outputs.
Algorithm
A procedure/function that takes inputs and maps it to a correct output, according to thr problem.
we write a constant size of code that can solve the problem for any arbitrary sized input.
INDUCTIVE PROOF (for correctness)
We need:
Efficency
Not only how fast the algorithm runs, but also how fast it runs relative to other algorithms that does the same thing.
log(n) is almost as good as constant time. especially as the input size increases
expontential time is the opposite of log in behavior. (really bad)
MODEL OF COMPUTATIONWORD-RAM (RAM): Random access memory (we can randomly access different locations of it in constant time)
Memory is just a string of bits of 1s an 0s.
CPU really small: it can hold small amount of information but can act on and change information. It also have instructions to look for info from memory, act on it and send it back.
When the WORD size was 32 bits: we can only address 2**32 addresses in memory. It can only address up to 4GB hard drive.
With 64 bits we can address 20 exabytes addresses (total google data is 10 exabytes)
Operations we can perform on the WORD
A CPU normally operates on 2 WORDS and produce the 3rd and spits it out. (A CPU operates on constant amout of data)
Last Updated:
Summarize & share videos seamlessly
Loading...