CS126 Flashcards
What is an algorithm?
An algorithm takes a set of inputs applies an operation defined by a set of instructions to these inputs and generates a set of outputs.
What is the running time of an algorithm?
The running time is the time taken for the algorithm to convert the set of inputs into a set of outputs
What affects the running time of an algorithm?
Usually as the input size of an algorithm increases the running time of the algorithm increases.
What is the caveat when it comes to same sized inputs?
Even if the inputs to an algorithm are the same size,the running time may be different as for example the operation may be to sort numbers in ascending order and one set of inputs may already be ordered.
What is the best case running time?
This is the minimum running time of an algorithm and is not really useful
What is the average case running time?
This is the typical running time on average however,this is quite difficult to determine.
What is the worst case running time?
This is the upper bound on the running time and is standard to analyse.
How to determine the running time of an algorithm the experimental way?
1.Write a program implementing the algorithm
2.Run the algorithm with varying size and type of inputs
3.Plot the inputs on a graph and determine.
What are the limitations of experimental analysis?
1.You must implement the algorithm however it is not always possible to do so
2.You must test the algorithm with all different kinds of inputs
3.You must test the algorithm in a controlled system
same software and hardware
however some algorithms may need more advanced tech
What is theoretical analysis and what are the benefits of it?
TA uses a high level description of an algorithm rather than an implementation.It considers all different inputs and as there is no need for hardware or software it is a controlled environment.Running time is characterised as a function of input size n.
How do we model a high level description of an algorithm?And what is it?
We use pseudocode.Pseudocode is code somewhere between english and computer program where we can hide design issues such as semicolons.Less detail than a program and more structured than english.
What is the RAM model of computation?
Its full form is random access machine and its has
one cpu
unbounded number of memory cells
executes one program
each cell stores an arbitary large positive integer and is assigned a number that can accessed in unit time
What are primitive operations?
They are basic computations performed by an algorithm. This may include assigning a value to a variable, indexing into an array, adding two numbers, calling a method, evaluating an expression.
