(2) Algorithms I

Question 1

Definition of Algorithm

Answer 1

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)

Question 2

Characteristics of algorithms

Answer 2

• independent of particular programming languages
• independent of particular software
• creative: different algorithms can solve a problem

Question 3

How can we transfer an algorithm to machine language?

Answer 3

Compiler or Interpreter

Question 4

Definition Compiler

Answer 4

• computer program
  transforms complete program in a programming language in a program in machine language
• object code can be executed

Question 5

How does a Compiler work?

Answer 5

• Scans the entire program first, then translate the entire program and executes the translated program
• Source code is translated exactly once

Question 6

Definition Interpreter

Answer 6

• Computer program

- Takes one statement at a time of a programming language and translates it into machine language

Question 7

How does an Interpreter work?

Answer 7

• Scans one statement at a time and translates it
• Directly executes every translated statement
• Source code might need to be translated several times

Question 8

What are pros and cons of a Compiler and an Interpreter?

Answer 8

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

Question 9

How are programs and data fundamentals designed in Java?

Answer 9

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

Question 10

Variable Definition

Answer 10

A variable is a symbolic reference to some memory cell. An alias (name) is used to address the variable.

Question 11

What is a constructed Java type?

Answer 11

• List of same-type elements (array)

- Combination of different types (record)

Question 12

Definition Array

Answer 12

Collection of elements of the same data type.

• array element is accessed via its index
• arrays may be multi-dimensional

Question 13

What are the default values of an int array and string array?

Answer 13

int: default value is 0
string: no default value (empty fields)

Question 14

An algorithm is a sequence of steps with…

Answer 14

1. No parallel execution of steps.
2. Every step is executed exactly once. No neglection, no repetition.
3. The execution order corresponds exactly to the order defined by
   the statements.
4. The execution of the last step of the algorithm completes the algorithm.

Question 15

Definition Control Structure

Answer 15

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).

Question 16

Definition Conditional Statement

Answer 16

A conditional statement defines that a condition must evaluate to true in order to proceed with the execution of the subsequent statement

Question 17

Definition Loops

Answer 17

Loops allow the execution of a statement or block of statements repeatedly.

Question 18

Definition For-Loop

Answer 18

• 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;
}

Question 19

Definition While-Loop

Answer 19

• 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++;
}

Question 20

Definition Do-While-Loop

Answer 20

• 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);

Question 21

Definition and Examples of Infinite Loops

Answer 21

• 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;
}

Question 22

In every loop we must make sure that:

Answer 22

(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

Question 23

Definition of Method

Answer 23

• help to structure our programs/algorithms
• provide reuse of functionality
• encapsulate the complexity of the algorithm

Question 24

Composition of a Method

Answer 24

• 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)

Question 25

In which case is an algorithm recursive?

Answer 25

An algorithm is recursive if it calls itself

int factorial (int number) {
   if (number <= 1) {
        return 1; 
   }
   else {
        return number * factorial(number - 1); 
   }
}