M1 Flashcards
is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.
algorithm
is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. This is thus a sequence of computational steps that transform the input into the output.
algorithm
AN ALGORITHM…
Can be represented in various forms
Recipe, process, method, technique, procedure, routine,… with
the following requirements:
ü Finiteness ü Definiteness ü Clearly specified input ü Clearly specified/expected output ü Effectiveness
Before you start to work on the the solution the developer, programmer must be able to understand fully the problem statement
Problem definition
Problem statements often have three elements:
• the X, stated clearly and with enough contextual detail to establish X;
• the X, often stated as a X or a working thesis;
• the X, statement of X of the document the writer is preparing.
problem itself
why it is important
method of solving the problem
claim
purpose
objective and scope
involves the definition of model objectives, conceptualization of the problem, translation into a computational model, and model testing, revision, and application.
Model development
Model development is an X process, in which many models are derived, tested and built upon until a model fitting the X is built
iterative
desired criteria
X may need to begin the search at the X as the original model building began, rather than where it finished. This may be for a number of reasons, a common one being that the model currently in service is X suited for reuse because it is poorly understood
Subsequent modeling work
same place
poorly
All algorithms must satisfy the following criteria:
• X. An algorithm has X, taken from a specified set of objects.
• X. An algorithm has X, which have a specified relation
to the inputs.
• X. Each step must be X; Each instruction is clear and unambiguous.
• X. The algorithm must always X after a finite number of steps.
• X. All operations to be performed must be X that they can be done exactly and in finite length.
Input,,, zero or more inputs
Output,,, one or more outputs
Definiteness,,, precisely defined
Finiteness,,, terminate
Effectiveness,,, sufficiently basic
In theoretical computer science, the X of an algorithm is asserted when it is said that the algorithm is correct with respect to a X. X refers to the input-output behavior of the algorithm.
correctness
specification
Functional correctness
A distinction is made between X correctness, which requires that if an answer is X it will be correct, and X correctness, which additionally requires that the algorithm X
partial
returned
total
terminates
Since there is no general solution to the X problem, a total correctness assertion may lie much deeper. A X is a type of mathematical proof that plays a critical role in formal verification because total correctness of an algorithm depends on X
halting
termination proof
termination
X is the determination of the amount of time and space resources required to execute it.
Usually, the X of an algorithm is stated as a function relating the input length to the number of steps, known as X, or volume of memory, known as X
Analysis of algorithms
efficiency or running time
time complexity
space complexity
- X is the process of executing a program with the intent of finding errors.
- A good test is one that has a high probability of X.
- X cannot show the absence of errors. It can only show if X.
- It is possible to write the tests X the program
Program testing
finding an error
Program testing,,, errors are present
before
For a programmer X is always a must. The presence of documentation helps X of all aspects of an application and it X on the quality of a software product. Its main focuses are development, maintenance, and knowledge transfer to other developers
reliable documentation
keep track
improves
Successful documentation will make information X, provide a limited number of user entry points, help new users learn X, simplify the product and help cut X.
easily accessible
quickly
support costs
X is usually focused on the following components that make up an application:
server environments, business rules, databases/files, troubleshooting, application installation and code deployment
Documentation
The main characteristics of algorithms are as follows −
• Algorithms must have a X
• Algorithms should have an explicitly defined set of X
• Algorithms are X with unambiguous operations
• Algorithms halt in a X amount of time. Algorithms should not run for
infinity, i.e., an algorithm must end at some point
unique name
inputs and outputs
well-ordered
finite
gives a high-level description of an algorithm without the ambiguity associated with plain text but also without the need to know the syntax of a particular programming language.
Pseudocode
An algorithm is a X with some specific characteristics that describes a X, which could be executed by a Turing-complete computer machine to perform a X. Generally, the word “algorithm” can be used to describe any X in computer science.
formal definition
process
specific task
high-level task
pseudocode is an X and (often rudimentary) human readable description of an algorithm leaving many granular details of it. Writing a pseudocode has no restriction of styles and its only objective is to X the high level steps of algorithm in a much realistic manner in X.
informal
describe
natural language
pseudocode is an X and (often rudimentary) human readable description of an algorithm leaving many granular details of it. Writing a pseudocode has no restriction of styles and its only objective is to X the high level steps of algorithm in a much realistic manner in X.
informal
describe
natural language
X IMPORTANCE
• the core of computer science
X IMPORTANCE
• A practitionerʼs toolkit of known algorithms
• Framework for designing and analyzing algorithms for
new problems
THEORETICAL
PRACTICAL
