Lecture 1
Fundamental objects of study in computer science.
Algorithms
Logic or procedure of solving any problem.
Algorithm
Advantages of algorithm
True or False.
Algorithm is dependent on any programming language. Thus, it's easy to understand for anyone even without programming knowledge.
False. Algorithm is not dependent on any programming language.
Measure of the time/space required by an algorithm
Complexity of an algrithm
1. A software of most computers with many calculators.
2. A sequence of numbers that do not form any progression, used to facilitate unbiased sampling of a population.
3. What is important in cryptography
1. Random-Number Generator
2. Random Number
3. Randomness
A way to classify how efficient an algorithm is.
Complexity of an algorithm
The computational complexity and efficient implementation of an algorithm are important in computing, and this depends on suitable __________.
Data structures
Disadvantages of algorithm
True or False.
Algorithm is time consuming.
True
Give examples of things that can affect the running time of an algorithm.
Size of the input,
Efficiency of the compiler,
Programming skills,
Complexity of underlying algorithm,
Computer used or the hardware platform,
Representation of Abstract data types.
true random numbers and pseudorandom numbers
The complexity of an algorithm is a function f(n) which measures ____ and _____ used by an algorithm in terms of input size n.
In comparing algorithm,
Best is equal to _______.
Fastest
Disadvantages of algorithm
True or False.
small tasks are difficult to put in algorithm
For any defined problem, there can be N number of solution. Also, it is most commonly estimated by counting the number of the elementary steps performed by any algorithm to finish execution.
Time complexity
An alternative to to "true" random numbers. A computer could use a seed value and an algorithm to generate numbers that appears to be random but in fact predictable.
Pseudorandom numbers
Running time of the program as a size of input.
Time Complexity
Advantages of algorithm
True or False.
By using algorithm, the problem is broken down into pieces or steps.
True
1.The steps are precisely stated.
2.The algorithm receives _____.
3.The algorithm produces _____.
4.Result of each steps are uniquely defined and only depend on the input and the result of the preceding steps.
5.The Algorithm applies to a set of inputs.
6.The algorithm stops after a finite number of instructions are executed.
1. Precision
2.Input
3.Output
4. Uniqueness
5.Generality
6.Finiteness
Types of Notation for Time complexity
1.Fewer than or same as
2.Fewer than
3.More than or same as
4.More than
5.The same as
1.Big Oh
2.Little Oh
3.Big Omega
4.Little Omega
5.Big theta
The computer measures some type of physical phenomenon that takes place outside of the computer. You're not a predictable machine, so an attacker can't guess the precise moment when you press these keys.
"True" random numbers.
Amount of computer memory required during the program execution, as a function of the input size.
Space complexity
Advantages of algorithm
True or False.
An algorithm uses an indefinite procedure.
False. it should be definite procedure.
Used to characterized something with many arts where those parts interact with each other in multiple ways.
Complexity
Understanding Notations of Time complexity
1.Set of functions that grow slower than or at the same rate as expression.
2.Set of functions that grow faster than or at the same rate as expression.
3.Consist of all functions that lie in both expression.
1.O(expression)
2.Omega(expression)
3.Theta(expression)
These _____are important for secure encryption, whether you're encrypting your own files or just using an HTTPS website on the internet.
Random numbers