Sub-procedures are functions that have no use on their own but are used in other procedures to contribute to solving a larger problem, for example a function that searches an array for a given item in a library management system. Putting these tasks down into sub procedures has many advantages:

• The complexity of the main procedure is reduced (only the abstraction of the sub-procedure, the calling command, is displayed)
• This allows easier understanding of the working of the procedure
• Each sub-procedure has its own task
• If many procedures use the sub-procedure, code duplication can be avoided → reduced risk of bugs in the code
• Easier management of the code as each function can be developed on their own

Every time there are two possible ways for the algorithm to go. For example, decision making is required to decide if the entered data is valid in a system.

Lets take the example that a system needs the age of the users. To prevent invalid values to be entered, a validation algorithm is used. The decisions required for this algorithm:

• Is a negative value entered?
• Is the value not greater than 150?
• Depending on the system, is the age below 18?

The conditions of a system determine the decisions that are made in the system. Because there are many decisions in the system, one decision can alter the conditions for an other.

Algorithms make decisions based on some pre-conditions. So, they need some initial conditions after which they direct their working. Pre-conditions are often given as parameters to the algorithm.

Concurrent computing is a form of computing in which several computations are executing during overlapping time periods – concurrently – instead of sequentially (one completing before the next starts) Concurrent computing.

Many processes can be implemented concurrently:

• Some calculations (Brute force calculations are usually implemented concurrently)
• GUI is usually implemented concurrently
• The programs in a modern computer run concurrently (parallel)

In a production line many processes are running parallel. Concurrent processing plays a crucial role here as it is what allows the system to execute a large amount of tasks simultaneously.

You need to think ahead. Before you start designing the solution try to think on which tasks can be run independently from each other. For example, in a calendar software, the periodical check if any reminders are due can happen independent from user input, so can run parallel to the rest of the solution.

An abstraction could be a car engine. You don't need to know how it works to be able to operate it, you only need to know how its abstraction works. So, creating an abstraction requires a lots of thinking ahead as you need to select the pieces of information that are relevant for an abstraction.

Computers cannot store an infinite number of things so we need to reduce them to abstractions, containing only necessary information. Also, this properties can then be grouped together into objects, which are a fundamental concept in computing and algorithms.

Lets say we need to create an abstraction from the people in a school. We can decompose the people in the school into teachers and students. Students can aslo be decomposed into boys and girls.

A car engine. It is made up of hundreds of parts, but we still need no nowledge on how they work. We only need to know how its abstraction - the pedals, gearshifting and the steering - work to be able to run it. In fact, the similarity of the abstractions allow us to be able to operate many different kinds of engines and vehicles, regardless on what type of engine they are using.

Sequential search: The algorithm loops through the array one-by-one until the required item is found or the end of the array has been reached. It is the simplest of all search algorithms.

Efficiency for a list consisting of n elements: O(n)

Binary search: The algorithm needs an ordered list to work. It starts in the middle of the array and checks if the desired result is either in the first or second half of the list. The other half is then discarded and the process is used for this sub-array until there is only one element left.

Efficiency for a list consisting of n elements: O(logn). However, if the list is unsorted, the algorithm is useless.

Bubble sort: This is an algorithm to sort an unsorted array, based on comparing and switching items.

Efficiency for a list consisting of n elements: O(n²)

Selection sort: The algorithm starts with the first element in the array. Then it loops through the rest of the array and finds the smallest element and switches it with the first one. Then it goes on to the second element and repeats the procedure until it reaches the end of the array.

Example: an array with content 4|2|1|6|3|5 should be sorted:

Efficiency for a list consisting of n elements: O(n²)

Lists: A finite ordered collection of values, where the same value may occur more than once.

Operations:

• constructor for creating an empty list
• testing whether or not a list is empty
• prepending an entity to a list
• appending an entity to a list
• determining the first component (“head”) of the list
• referring to the list consisting of all components except for the first one (this is the “tail” of the list)

Stack: A special kind of collection where the only operations are the addition or removal of an entity to the collection, known as push and pop. This makes a stack a Last-In-First-Out (LIFO) data structure.

Queue: A special kind of collection where the entities are kept in order and the only operations permitted are the addition or removal on an entity, where the first added entity is removed first. This makes a queue a First-In-First-Out (FIFO) data structure.

We are expected to discuss the differences between algorithms used to solve similar problems, for example if binary search is better or not than sequential search for a collection.

Syllabus link:
Examination questions may involve variables, calculations, simple and nested loops, simple conditionals and multiple or nested conditionals.

This would include tracing an algorithm as well as assessing its correctness.

Students will not be expected to construct a flow chart to represent an algorithm in an externally assessed component.

Syllabus link:
Examination questions may involve variables, calculations, simple and nested loops, simple conditionals and multiple or nested conditionals.

This would include tracing an algorithm as well as assessing its correctness.

We are expected to construct pseudocode for some simple operations like checking a mail address for correctness.

Pseudocode notation approved by IB

Syllabus link:
Suitable algorithms may include both standard algorithms and novel algorithms. Suitable may include considerations of efficiency, correctness, reliability and flexibility. Students are expected to suggest algorithms that will actually solve the problem successfully.

We should be aware how different techniques like nested loops can influence the efficiency of an algorithm (a nested loop decreses efficiency to O(n²))

We also should be able to suggest changes in an algorithm to increase efficiency, for example setting a flag to stop search immediately after an item is found.

Questions will involve specific algorithms in pseudocode or flow charts and we are expected to give an acual number of steps required for a given situation. This involves that we have to trace the algorithm.

Add, compare, retrieve and store data.

All of the more complex operations compose of a combination of these simple operations

Examples of fundamental operations:

• Add one number to another
• Store a number in memory
• Compare two numbers to find which one is larger

Examples of compound operations of a computer:

• Find the largest out of several numbers
• Find the modulus of a division

• Fixed vocabulary
• Commands to store, retrieve and modify data
• Defines operations a computer can execute

It is very hard and prone to errors to write programs in machine language. A high level language looks more like english and is thus more readable for programmers. This allows them to focus more on the problem solving itself than on translating their solution into machine-executable code. Also, because every different machine has its own machine instruction set, it is easier to translate programs written in high level languages for many machines than machine code.

Higher level languages are easily readable for humans but computers ultimately understand one form of instructions - machine code. So, programs written in high level languages need to be translated into machine language so that computers can execute them.

Variable: is an entity in a computer program that refers to a location in primary memory that holds a value. There are different variable types, like integers and strings but they only differ in the way the information in memory is interpreted.

Constant: is a special type of variable those content cannot be changed once it is initialised. It is used to store values in a program that do not need to be changed throughout the runtime, for example a mathematics program would store π in a constant as its value does not need to be changed.

Operator: +, -, =, *, /, +=, -=. They are symbols of infix operations that determine what operation should be carried out on the parameter values or how to compare values in a boolean operation.

Object: is an abstract entity in object oriented programming. It tries to model a real-world thing by bundling its properties into one entity - the object - so that they can be treated together. It also simplifies programming as many variables belonging to one object can be grouped together in a logical way.

=: This operator assigns a value to a variable. In boolean operations it checks if two values are the same or not.

≠: This comparative operator compares if two values are the same or not. It is used in boolean operations.

<, >: This comparative operators check if the values are smaller or greater than each other.

⇐, >=: This comparative operators check if two values are smaller, greater or equal than each other.

mod: This infix operand returnes the modulus, the remainder of a division.

div: Whole number division. Any remainder is discarded.

A constant is used to store a value that is not supposed to change during the runtime on an algorithm, for example a constant storing π in an algorithm. A variable is used to store values that change when an algorithm is executed, like the result of an addition

Syllabus link:
Teachers must ensure algorithms use the symbols from the approved notation sheet Pseudocode notation approved by IB.

A collection is a grouping os some variable number of data items that have some shared significance to the problem being solved and the need to be operated upon together in some controlled fashion. Collection_(abstract_data_type).

Collections may find applications in any type of programs that deal with many similar data items at once, for example a library program keeping track of books.

Be sure that you use the specific operations of specific kinds of collections (pou and push for stacks, for example)

Sorting out processes into sub-programmes can make reuse of code possible, if many methods carry out similar operations. Also, by specifying what a sub-program has to do, a developer can concentrate on using the sub program while others can worry about implementing it. Putting specific algorithms into sub-programmes can also increase readability and understandability of the code.

Created by Matyas Mehn — Matyas Mehn 2014/04/02 12:45