IB Computer Science HL - Topic 4 - Computational Thinking

Topics 4.1, 4.2 and 4.3 all included. This does not include specific PSEUDOCODE methods, that can be found on a separate deck.

State the fundamental operations of a computer

ADD, COMPARE, RETRIEVE(Load), STORE(Save)

What is the difference between fundamental and compound operations of a computer

Fundamental operations cannot be decomposed into smaller tasks so do not require the processor to go through a number of sub operations to see a result. Compound operations are made up of multiple fundamental operations.

What are fundamental operations

A set of instructions in the CPU which enable commands to be processed

Define pre-conditions

Constraints on the state of the system before the use case can start.

Define post-conditions

Constraints on the state of the system after execution

Why are pre-conditions needed ? Give an example

Many processes require certain conditions before execution. One example is the user being logged in.

Define abstraction

Simplification to remove unneccassary detail

Why is abstraction required in the design of algorithms?

It allows a general idea of what the problem is and how to solve it. The process removes all specific detail, and any patterns that will not help solve a problem.

What is a sequential search

A search which searches items from start to end, checking one-by-one.

Advantages of sequential search:

Easy to code and good for small lists

Disadvantages of sequential search:

Slow for long lists

What is a binary search

A search which uses 3 pointers. The middle pointer's value will be compared against the key. If it is lower than the key, the key must be in the second half. If the middle index is higher than the key, then the key must be in the first half. This causes the number of search elements to be halved each time

Advantages of binary search:

More efficient for longer lists as it does not look at every item of data

Disadvantages of binary search:

• It is complicated for small number of elements

• difficult if data is constantly being added

• only works for sorted lists.

What is bubble sort

A sorting algorithm which compares adjacent items and swaps them if they're in the wrong order.

Advantages of bubble sort:

easy to implement and works with smaller lists.

Disadvantages of bubble sort:

\
time inefficient and slow for longer lists.

What is a selection sort

A sorting algorithm which creates a sub-list which is sorted within the main unsorted list.

How is a selection sort efficient

Only the smallest item is swapped each time. This reduces unnecessary computational calculations, creating a more efficient algorithm.

Advantages of selection sort:

efficient for shorter lists

Disadvantages of selection sort

not suitable for larger lists as it has high algorithmic complexity;

What are the 5 access collection methods.

* .addItem(item)
* .getNext()
* .resetNext()
* .hasNext()
* .isEmpty()

\

What does .addItem(item) do ?

adds item to the end of the collection.

What does .getNext() do ?

\
\

returns the next value and moves the pointer along.

What does .resetNext() do ?

\
\

resets the collection's pointer.

\
What does .hasNext() do?

\
\

returns true if there are still values, false if there are no longer any values.

\
What does .isEmpty() do ?

\

returns true if the collection is empty, false if there are still values.

How can we solve the problem of a sorting algorithm continuing to pass even if a list is sorted

By creating an early exit sort. Implemented using flags as a boolean variable, if there are no more swaps, the flag is set to false.

How can we solve the problem of a sorting algorithm comparing sorted elements

Basing the inner loop on the outer loop

Define time complexity

Time taken to execute an algorithm.

What does time complexity rely on ?

The number of steps an algorithm takes for x inputs. So the number of loops and the number of data items, is important.

Define the data structure type collection.

an object that groups multiple elements into a single unit. They are an unordered list of unknown length or size. They are dynamic data structures.

The following list of numbers needs to be put into ascending order:

9 , 11 , 3 , 4 , 5 , 7 , 1 , 2

State the list that would be obtained after **two** iterations of a bubble sort.

3 , 4 , 5 , 7 , 1 , 2 , 9 , 11

Sort the array [12 , 52 , 16 , 42 , 88 , 86]

into descending order using selection sort. Show each pass

12 52 16 42 88 86 // Initial

88 52 16 42 12 86

88 86 16 42 12 52

88 86 52 42 12 16

88 86 52 42 12 16

88 86 52 42 16 12 // Sorted!

What are the three languages within computer language

low level, assembly code and high level language.

What are the essential features of high level languages

**fixed vocabulary** — specific keywords are used for specific purposes;

**unambiguous meaning** — code always means the same thing: keywords have specific meanings and purpose in the language;

**fixed consistent grammar and syntax**

Which two computer languages need to be translated into machine code for execution

Low level and high level

What are the benefits of the features in high level languages

• makes future maintenance easier;

• languages will be easier to learn and use;

• there will be less logical errors;

• there will be less compilation errors;

• other developers can understand the system easier.

What is the need for high level langauges

1. They are easier to code in, so:

   • save programming time as you don’t have to write in machine code

   • are easier to debug;

   • require less training;

2. provide abstraction;

   • as they hide the binary processing;

3. are similar to natural human language.

3 types of translators

Assemblers, interpreters and compilers.

What does an assembler do ?

Converts assembly code to machine code.

What does an interpreter do

Converts high level language to machine code. The interpreter translates line-by-line.

Advantage of interpreter

• Easier to debug (line by line)

• Creates platform independent code(as they execute the source program code themselves)

Disadvantage of interpreter

interpreters take longer to execute.

Advantages of compiler

Take less time to execute

Disadvantages of compiler

compilers are harder to debug

Why are translators needed

• To convert code into binary.

• To abstract from the complications of machine code.

• To provide platform independence (allows programs to be created for all operating systems).

Define variable

A storage location for data in a program. Its value can change during run-time.

Define constant

A variable whose value does not change during run-time.

Define operators

Used to represent actions. They are operations on primitive data types.

Define objects

An instance of a class. They are an abstraction. They hold data (private attributes) and ways to manipulate the data (public behaviours).

what does the operator MOD do ?

return the remainder

what does the operator DIV do ?

Returns the how many times X divides Y. It leaves no remainder.

Define modular design

Use of functions and modules of code.

Benefits of modular design

Reusable code

Maintenance

Ease to debug

Organisation/Modularisation

Why is reusability of sub programs useful

• reduces redundant code

• reuse in future projects = saved time

Why is modularisation of sub programs useful

• makes code more readable as each block’s purpose is well-defined;

• makes code more manageable as each module can be separately designed, implemented and tested.

• enables distributed development, allowing developers to work in parallel on different modules.

Why are sub programs easy to debug

Segments are pretested with sample data

Outline the benefits of predefined sub-programs and collections. Why might developers choose to use these rather than developing their own?

they are tested and are reliable, reducing the cost and time needed to develop a large program.

Identify the three types of programming error

* syntax errors.
* logic errors.
* runtime errors.

Give an advantage of having both an interpreter and a compiler available.

Compilers have faster and more efficient execution and give more control to developers over hardware elements like memory management and CPU usage. This makes them hard to debug, interpreters could help with this

Explain the two different methods. Provide examples

• Functions and procedures

• Functions return a value procedures do not

• Procedure eg. System.out.println() as it outputs a value to the console rather then return

• Function eg. Math.pow() as it returns the 1st parameter raised to the value of the second.
  

Negatives of modular design

• If a module fails, it can be difficult and expensive to replace.

• Must consider if an object is modular or not which can be very time consuming

• Poorly designed modules can lead to problems and inconsistency in the overall product

Define concurrent processing

when tasks are given slices of processor time, to give the illusion that tasks are being performed simultaneously

Define concurrent thinking

Identifying patterns or areas where concurrency can be applied, speeding up the process

Discuss how a real world object is different from its abstraction

The abstraction considers functionality, interface and properties of entities. Attributes are an abstraction for the characteristics of an object while methods are an abstraction for the actions a real-world object is able to perform.

Explain the need for abstraction.

• allows non-experts to make use of a range of systems or models

• enables for more efficient software design as programmers can focus on core elements rather than unnecessary details

• reduces the time spent on the project and prevents the program from getting unnecessarily large.

What is the big O notation for ?

a metric for determining an algorithms efficiency

Efficiency equation

efficiency = time complexity + space complexity