3.1 Fundamentals of Algorithms

Question 1

1) What is an algorithm?
2) What is Algorithmic Thinking?
3) What is decomposition?
4) What is abstraction?

Answer 1

1) An algorithm is a sequence of steps that can be followed to complete a task.
2) Algorithmic thinking is the process of developing an algorithm to solve a problem.
3) Decomposition is the process of breaking problems down into smaller, more manageable parts.
4) Abstraction is the process of removing unnecessary detail from a problem.

Question 2

1) What is the difference between an algorithm and a computer program?
2) What is a written description?

Answer 2

1) An algorithm describes the logic of a solution. A computer program is an implementation of this solution, written in a programming language.
2) A written description can be used to specify the steps of an algorithm.

Question 3

What do the following do in flowcharts:
1) Arrows
2) Subroutines
3) Terminators
4) Inputs and Outputs
5) Process
6) Decision

Answer 3

1) Arrows are used to show the direction and flow of the program.
2) Subroutines are represented by a rectangle with two straight lines on either side.
3) Terminators are used for the start and end of subroutines or programs. It is represented by an oval.
4) An input or output is represented by a parallelogram.
5) A process is represented by a rectangle. It is used for an instruction or command.
6) A decision has two branches: True and False. It is represented by a diamond.

Question 4

1) What is pseudocode?
2) What is a trace table?
3) What is a flow chart, and what can be used to signify the flow of the program.

Answer 4

1) Pseudocode is simplified language used to describe the sequence of steps used to solve a problem or complete a task. Pseudocode does not use program specific language.
2) A trace table allows you to formally record the state of variables, the outputs and the condition evaluations as you mentally execute the algorithm.
3) A flow chart can be used to visually represent an algorithm or program. Arrows can be used to signify the flow of the program.

Question 5

1) What is a syntax error?
2) What is a runtime error?
3) What is a logic error?

Answer 5

1) Syntax errors are mistakes in the code, such as spelling and punctuation errors.
2) This is the error message you will receive if a problem occurs with your code while it is running.
3) They occur when the program runs without crashing, but produces an incorrect result. The error is caused by a mistake in the program’s logic. You won’t get an error message, because no syntax or runtime error has occurred.

Question 6

Explain the linear search algorithm step by step

Answer 6

The instructions for performing a linear search can be written as:
1) Take a list of data and an item that is being searched for (the search item).
2) Repeat steps a–c, starting from the first item in the list, until you find the search item, or until the end of the list is reached:
a. Compare the item at the current position to the search item.
b. If the item at the current position is equal to the search item, stop searching.
c. Otherwise, go to the next item in the list.

Question 7

Explain the binary search algorithm step by step

Answer 7

1) Take an ordered list of data and an item that is being searched for.
2) Maintain a range of items where the search item might be found.
Initially, set the range to be the entire list.
3) Repeat the following steps until you find the item you are searching for, or there are no more items to check (the range is empty):
a. Find the item in the middle of the range (the midpoint item).
b. Compare the midpoint item to the item you are searching for.
c. If the midpoint item is equal to the search item, stop searching.
d. Otherwise, if the midpoint item is less than than the search item, change the range to focus on the items after the midpoint.
e. Otherwise, if the midpoint item is greater than than the search item, change the range to focus on the items before the midpoint.

Question 8

1) Explain what best-case scenario means
2) Explain what worst-case scenario means

Answer 8

1) The best-case scenario occurs when the item you are looking for results in the smallest possible number of steps.
2) The worst-case scenario takes place when the item you are looking for results in the greatest possible number of steps.

Question 9

1) Explain what a linear search is
2) Explain what a binary search is

Answer 9

1) Linear search is an algorithm that involves checking each item in a list or sequence of data one at a time. When the data is unsorted, the only sensible option when searching for a particular item is to start at the beginning and look at every item until you find the one you want.
2) Start by setting the counter to the middle position in the list. If the value held there is a match, the search ends. Otherwise, the list is split in half depending on if the value is greater than or less than the midpoint.

Question 10

1) What is the bubble sort algorithm?
2) What is the merge sort algorithm?

Answer 10

1) The bubble sort algorithm works by repeatedly going through a list, comparing adjacent items and swapping the items if they are in the wrong order.
2) Merge sort can be used to combine pairs of sorted lists repeatedly until all the items are in order.

Question 11

Explain the bubble sort algorithm step by step

Answer 11

1. Take a list of data to be sorted.
2. Repeat step 1 (the pass) until no swaps are made:
   Repeat steps a-c for all the items in the list, starting from the first one:
   a. Compare the item at the current position to the one next to it.
   b. If the item at the current position is greater than the one next to it, swap the items within the list.
   c. Go to the next item in the list.

Question 12

What is the merge sort algorithm?

Answer 12

1. Take a list of data to be sorted.
2. Repeatedly split the list in half until each item is in a list of its own.
3. Repeat steps a to d until all lists have been merged.
   a. Take two lists of data to be merged.
   b. Create a new empty list for the merged items.
   c. Repeat steps i to ii until one of the lists of items is empty:
   i. Compare the first items of the two lists.
   ii. Place the item that is lower into the merged list in the next available position.
   d. Then place each item from the remaining list into the merged list in order.

Question 13

What are the advantages and disadvantages of linear and binary search?

Answer 13

Advantages of linear search:
- Small lists can be searched quite quickly
- Easier to implement
- The data does not need to be in order
Advantages of binary search:
- Much faster at searching large lists than linear search

Question 14

What are the advantages and disadvantages of merge sort and bubble sort

Answer 14

Advantages of bubble sort:
- Simplest and easiest to code
- Uses less memory
Disadvantages:
- Not suitable with larger lists
- Inefficient and slow
Advantages of merge sort:
- Far more efficient and fast
- Suitable for a large number of items
-Disadvantages:
- Uses more memory
- More complex to program

Question 15

1) How do you assign a variable and a constant in pseudocode?
2) How do you make a comment in pseudocode?
3) How do you do integer division and modulus operator in pseudocode?
4) How do you show boolean operators?

Answer 15

1) Variable name ← Value, or CONSTANT Variable name ← Value for a constant
2) # Comment
3) Integer division: 9 DIV 5; Modulus operator: 9 MOD 5
4) AND, OR, NOT, eg. (3 = 3) AND (3 ≤ 4), NOT (a < b)

Question 16

1) How do you write a FOR loop in pseudocode?
2) How do you write a WHILE loop in pseudocode?

Answer 16

1) FOR a ← 1 TO 3
OUTPUT a
ENDFOR
# This code will output 1, 2, 3. A for loop in pseudocode includes the first and the last integers (eg. Includes 1 and 3.)

FOR a ← 1 TO 5 STEP 2
OUTPUT a
ENDFOR
# will output 1, 3, 5
FOR-IN-ENDFOR
(repeat the statements the number of times that there are characters in a string).

length ← 0
FOR char IN message
length ← length + 1
ENDFOR
# will calculate the number of characters in message
reversed ← ‘’
FOR char IN message
reversed ← char + reversed
ENDFOR
OUTPUT reversed
# will output the string in reverse
2) WHILE condition (eg. a < 0)
# statements here
ENDWHILE

Question 17

1) How do you write an IF, ELIF, ELSE selection in pseudocode
2) How do you create and use subroutines in pseudocode?

Answer 17

statements here

1) IF condition THEN
ELIF condition THEN
# statements here
ELSE
ENDIF
2) SUBROUTINE add(a, b)
result ← a + b
RETURN result
ENDSUBROUTINE
add(2,3)

Question 18

1) How do you create an array in pseudocode, and update it?
2) How do you convert a string to an integer, and unicode/ASCII to character?
3) How do you output and input in pseudocode?
4) How do you generate random numbers in pseudocode?

Answer 18

1) primes ← [2, 3, 5, 7, 11, 13]; primes[2] ← 4
2) STRING_TO_INT(‘16’); CODE_TO_CHAR(97)
3) OUTPUT a, g (must be a string); a ← USERINPUT
4) diceRoll ← RANDOM_INT(1, 6) (numbers inclusive)

Question 19

1) What is a record?
2) How is a record written in pseudocode?

Answer 19

1) A record is all of the data or information about one person or one thing.
2) RECORD Artwork
title: String
year: Integer
ENDRECORD
TheSun ← Artwork(‘The Sun’, 1893)
OUTPUT TheSun.year
TheSun.year ← 1895