S1 - Algorithms (Done)

Question 1

What is computational thinking ?

Answer 1

The steps you take to find the best solution to a complex problem.

Question 2

What are the three key techniques for computational thinking ?

Answer 2

Decomposition, abstraction and algorithmic thinking.

Question 3

What is decomposition ?

Answer 3

Breaking down a complex problem into smaller problems and solving each one individually.

Question 4

What is abstraction ?

Answer 4

Picking out the important bits of info from a problem.

Question 5

What is algorithmic thinking ?

Answer 5

A logical way of getting from the problem to the solution.

Question 6

What is pseudo-code ?

Answer 6

Not an actual programming language, follows a similar structure without worrying about the syntax. Quick to write and easily converted into other programming languages.

Question 7

What are the two main search algorithms ?

Answer 7

Binary and linear search.

Question 8

When are binary and linear searches used ?

Answer 8

Binary searches are used in an ordered list, whereas a linear search is used in an un-ordered list.

Question 9

How would you find the middle item in a list ?

Answer 9

make the length of the list n, and do (n + 1) ÷ 2 and round up if necessary.

Question 10

How would you complete a binary search ?

Answer 10

Find the middle item, if it’s the one you’re looking for stop, else middle item is more than desired item - get rid of second half of the list, if the middle item is less than the desired item get rid of the first half. repeat this with each new list until you have desired item.

Question 11

How would you complete a linear search ?

Answer 11

Look at the first item in the list, if it’s the one you’re looking for stop, else look at the next item. Repeat this until you’ve either reached the end of the list or found the desired item.

Question 12

What are the two sorting algorithms ?

Answer 12

A bubble sort and merge sort.

Question 13

How do you do a bubble sort ?

Answer 13

Look at the first pair of integers and swap them if they’re in the wrong order, move on to the next pair and do the same. Repeatedly do this until you get to the end of the list, called one pass. Repeat all of this until there are no swaps in a pass.

Question 14

What are the advantages of a bubble sort ?

Answer 14

It’s simple and can be easily implemented on a computer, and it’s an efficient way to check if a list is already in order, and it doesn’t use very much memory as all sorting is done using the original list.

Question 15

What are the disadvantages of a bubble sort ?

Answer 15

It’s an inefficient way to sort a list (worst case it’ll do (n(n-1)) ÷ 2 comparisons), and because of this it’s pretty slow for very large lists.

Question 16

How do you do a merge sort ?

Answer 16

Split the list in half, with the second sub-list starting with the middle term, and keep doing this until each sub-list contains one item. Then merge pairs of sub-lists, doubling the items, each time sort the items into the right order - until all the sub-lists are merged and are in the right order.

Question 17

What are the advantages of a merge sort ?

Answer 17

Generally more efficient than a bubble sort algorithm for larger lists, and similar for short lists. It also has consistent running time regardless of the order of items in the original list.

Question 18

What are the disadvantages of a merge sort ?

Answer 18

Even if the list is already sorted it goes through the whole process, so bubble sort may be quicker in some cases, and it uses more memory as it has to create additional lists.

Question 19

What is the difference between a linear and binary search ?

Answer 19

Linear search is much simpler, but not as efficient - however linear search’s biggest advantage is it can be used on any list. In small ordered lists difference in efficiency doesn’t matter so run time will be similar, in big lists binary search’s run time will be shorter than a linear search.

Question 20

In a flow chart what represents a start or stop ?

Answer 20

Boxes with rounded corners, at the beginning and end of an algorithm.

Question 21

In a flow chart what represents inputs or outputs ?

Answer 21

Parallelogram boxes, holds anything that goes in or out of the algorithm.

Question 22

In a flow chart what represents processes ?

Answer 22

Rectangular boxes, contains general instructions, processes and calculations.

Question 23

In a flow chart what represents a decision ?

Answer 23

Diamond boxes, containing yes or no questions with two paths it can follow depending on this.

Question 24

In a flow chart what represents a subroutine ?

Answer 24

Rectangular boxes with additional lines on either end, referencing other flowcharts.

Question 25

In a flow chart what does an arrow represent ?

Answer 25

The direction the algorithm should move in, and connect the boxes.