Algorithms Flashcards
What is a program, and how does it differ from an algorithm?
An algorithm is an idea/solution/plan of how to perform a particular task. It is an unambigous step by step procedure for carrying out a task, which always terminates after a finite number of steps. it can be written in plain English.
While an algorithm is the idea behind a program, a program is the expression or implementation of that Idea in a programming language.
How are the contracts of routines expressed?
Through pre- and post conditions
Precondition
A precondition of a subroutine is something that must be true when the subroutine is called,
if the subroutine is to work correctly. For example, for the built-in function Math.sqrt(x), a
precondition is that the parameter, x, is greater than or equal to zero, since it is not possible
to take the square root of a negative number.
Preconditions most often give restrictions on the acceptable values of parameters, as in the
example of Math.sqrt(x). However, they can also refer to global variables that are used in the
subroutine. Or, if it only makes sense to call the subroutine at certain times, the precondition
might refer to the state that the program must be in when the subroutine is called.
It is the obligation of the user to ensure the preconditions are met.
Postcondition
It is something that will be true after the subroutine has run
(assuming that its preconditions were met—and that there are no bugs in the subroutine).
The postcondition of the function Math.sqrt() is that the square of the value that is returned
by this function is equal to the parameter that is provided when the subroutine is called.
It is the obligation of the routine to ensure that post conditions, such as return values, are correct.
What are the 3 criteria by which algorithms are measured?
Correctness, Robustness and Efficiency
Correctness
A program is correct if it accomplishes the task it was designed to perform
Robustness
A program is robust if it can handle illegal inputs and other unexpected situations in a reasonable way.
State
A state consists of all the information
relevant to the execution of a program at a given moment during its execution.
Process
A process is the sequence of states that the computer goes through as it executes the program.
Invariants
A loop invariant is, roughly, a statement that remains true as the loop is executed. More
precisely, we can show that a statement is an invariant for a loop if the following holds: As
long as the statement is true before the code inside the loop is executed, then it will also
be true after the code inside the loop has been executed. That is, a loop invariant is both a
precondition and a postcondition of the body of the loop.
Assertions
A statement that is either true or false (Boolean)
Exceptions
The word “exception” is meant to be more general than
“error.” It includes any circumstance that arises as the program is executed which is meant to
be treated as an exception to the normal flow of control of the program. An exception might
be an error, or it might just be a special case that you would rather not have clutter up your
elegant algorithm.
Efficiency
The term “efficiency” can refer to efficient use of almost any resource, including time,
computer memory, disk space, or network bandwidth.
What is the main technique used for the analysis of algorithms?
asymptotic analysis.
What does the word asymptotic mean?
“the tendency in the long run, as the size of the input is
increased.”
