(2) Algorithms I Flashcards
Definition of Algorithm
A procedure for a systematic and stepwise problem solution.
- abstracts from concrete implementation
- computational procedure that takes input and produces an output
- well defined execution order
- solves a class of problems (not a single problem)
Characteristics of algorithms
- independent of particular programming languages
- independent of particular software
- creative: different algorithms can solve a problem
How can we transfer an algorithm to machine language?
Compiler or Interpreter
Definition Compiler
- computer program
transforms complete program in a programming language in a program in machine language - object code can be executed
How does a Compiler work?
- Scans the entire program first, then translate the entire program and executes the translated program
- Source code is translated exactly once
Definition Interpreter
- Computer program
- Takes one statement at a time of a programming language and translates it into machine language
How does an Interpreter work?
- Scans one statement at a time and translates it
- Directly executes every translated statement
- Source code might need to be translated several times
What are pros and cons of a Compiler and an Interpreter?
Compiler:
+ more efficient -> only one translation of entire program necessary
+ program may be optimised after translation
- for every source code change, program has to be entirely retranslated
Interpreter:
+ fast Response to changes in the program
- repeated translations of statements
- execution is very time consuming
How are programs and data fundamentals designed in Java?
Program: Statements
- number of statements
- represent flow of control
- operate data
Data: Variables
- refer to memory addresses where data is stored
- symbolic identifiers commonly used
- variables are given by their name
Variable Definition
A variable is a symbolic reference to some memory cell. An alias (name) is used to address the variable.
What is a constructed Java type?
- List of same-type elements (array)
- Combination of different types (record)
Definition Array
Collection of elements of the same data type.
- array element is accessed via its index
- arrays may be multi-dimensional
What are the default values of an int array and string array?
int: default value is 0
string: no default value (empty fields)
An algorithm is a sequence of steps with…
- No parallel execution of steps.
- Every step is executed exactly once. No neglection, no repetition.
- The execution order corresponds exactly to the order defined by
the statements. - The execution of the last step of the algorithm completes the algorithm.
Definition Control Structure
A control structure is an instruction which allows to manipulate the order of execution such that the flow differs from the implicitly specified sequential order (restricted to a single thread of execution).
Definition Conditional Statement
A conditional statement defines that a condition must evaluate to true in order to proceed with the execution of the subsequent statement
Definition Loops
Loops allow the execution of a statement or block of statements repeatedly.
Definition For-Loop
- A for-loop consists of a loop head and a loop body
- The loop head is a control expression which consists of three parameter:
1. Initialization expression
2. Loop test expression
3. Iterator
for (int i = 1; i <= 6; i++) {
j = j + i;
}
Definition While-Loop
- The while loop executes its body as long as the loop condition is met
- The loop expression is tested at the beginning of the loop
while (i <= 6) {
j = j + i;
i++;
}
Definition Do-While-Loop
- The do-while loop executes its body as long as the loop condition is met
- The loop expression is tested at the end of the loop (body is executed at least once)
do {
j = j + i;
i++;
} while (i <= 6);
Definition and Examples of Infinite Loops
- In most cases, infinite loops are caused by incorrect termination conditions
- Non-terminating algorithms are not correct if they require infinite time to solve a problem
- Non-terminating algorithms can be correct if they continuously solve a permanently recurring problem:
- traffic light regulation
- artificial respiration
while (i < 6) {
i = i – 1;
x = x * x;
}
In every loop we must make sure that:
(1) the control variable is initialized
(2) its value is changed in every run
(3) it is used in the loop condition
(4) it eventually reaches a value that the loop condition will evaluate to false
Definition of Method
- help to structure our programs/algorithms
- provide reuse of functionality
- encapsulate the complexity of the algorithm
Composition of a Method
- The data type of the returned result (returnType)
- The name of the method (methodName)
- A list of formal parameters (type1 arg1, type2 arg2, …)
- The method body (the actual algorithm)
In which case is an algorithm recursive?
An algorithm is recursive if it calls itself
int factorial (int number) {
if (number <= 1) {
return 1;
}
else {
return number * factorial(number - 1);
}
}
