2.1 algorithms

What are the 3 concepts of computational thinking?

1. Abstraction

2. Decomposition

3. Algorithmic thinking

What is abstraction?

The process of only focusing on the relevant and important details, while ignoring the unnecessary ones.

What is decomposition?

The process of breaking down a complex problem into smaller, more manageable subproblems.

What is algorithmic thinking?

The process of creating a step by step solution to a problem.

What is an algorithm?

What is the Input-Process-Output Model?

What is the input in an algorithm?

The data that is entered into the algorithm.

What is the process in an algorithm?

The steps/operations performed on the input data.

What is the output in an algorithm?

The result produced

What is a structure diagram?

A visual representation showing how a problem is broken down into subsections, and how they relate to each other

What are the 3 ways of representing algorithms?

• Flowcharts

• Psuedocode

• High level programming language

What are the meaning of the flowchart symbols?

What is a syntax error?

An error that occurs when code violates the grammatical rules of a programming language.

What is a logic error?

An error that occurs when a program runs successfully but produces incorrect results.

What is a trace table?

A table used to track the value of variables line by line as a program is run.

What do trace tables help find?

Logic errors.

What are the 2 types of search algorithm?

• Linear search

• Binary search

What are the steps for a linear search?

1. Compare first item in the list with the item you are searching for.

2. If it isn’t the item you are searching for, then compare with the next item in the list.

3. This is repeated until the item is found or until the end of the list is reached.

What are the steps for a binary search?

1. Find the midpoint of the list

   • (n + 1) / 2

2. Compare the item at the midpoint with the item you are searching for.

3. If the item you are searching for is greater, ignore the lower part of the list.

4. If the item you are searching for is lesser, ignore the upper part of the list.

5. This is repeated until the item at the midpoint is the item being searched for.

What is the pre-requisite of a binary search?

The list must be in order.

What are the 3 types of sort algorithm?

• Bubble sort

• Merge sort

• Insertion sort

What are the steps for a bubble sort?

1. Compare first two adjacent elements.

2. If they are in the wrong order, swap them.

3. Otherwise, move onto the next two adjacent elements and compare.

4. Repeat until the whole list is in the correct order.

How is bubble sort applied to a data set?

EX: [6, 7, 3, 4]

[6, 3, 7, 4]

[6, 3, 4, 7]

[3, 6, 4, 7]

[3, 4, 6, 7]

What is an example of a bubble sort algorithm?

What are the steps for a merge sort?

1. Divide the list by 2 until each data element is separate and an individual list.

2. Then, combine adjacent individual lists into multiple sorted lists.

3. Repeat until they combine to form one sorted list.

How is a merge sort applied to a data set?

EX: [6, 7, 3, 4]

[6, 7] [3, 4]

[6] [7] [3] [4]

[6, 7] [3, 4]

[3, 4, 6, 7]

What is an example of a merge sort algorithm?

What are the steps for an insertion sort?

1. The first value is separated from the rest of the list and is sorted, while the rest of the array is unsorted.

2. Compare the next value in the list, in the unsorted portion, with the value(s) stored in the sorted portion of the list.

3. Insert it into its correct position in the sorted list.

4. Repeat until the whole list is in the correct order.

How is an insertion sort applied to a data set?

EX: [6, 7, 3, 4]

[6] [7, 3, 4]

[6, 7] [3, 4]

[3, 6, 7] [4]

[3, 4, 6, 7]

What is an example of an insertion sort algorithm?