Algorithmic Thinking

Which of the following describes an algorithm? Tick three Steps are carried out in order It is always written in pseudocode Every algorithm must have iteration It solves a problem It has a sequence of steps Every algorithm must have selection Look at each description in the table below. Does it describe pseudocode, a flow diagram or both? Flowchart A diagram with boxes and arrows Both Shows how an algorithm works Pseudocode Instructions similar to a programming language can be compared to a high level programming language Match the words on the left with the meanings on the right. Functional decomposition Breaking a problem into smaller parts to solve using subroutines Selection Running different parts of a program based on a condition (if statement) Iteration Running a section of code more than onc Abstraction Ignoring details of a problem to make it easier to solve. Searching A search which looks at each of the items in a list in order is known as what type of search? A Binary search A Linear search A search engine In order to do a linear search does the list need to be sorted? Yes always No never It can be sorted or unsorted In a binarysearch we first compare the item we are looking for with the middleitem in the list. The advantageof using this method compared to a linear search is that it is generally more efficient. 4 7 12 32 45 7 80 looking at the numbers above, using a linear search it would take 5 searches to find number 45 (please type your answer as a number). The first item that would be searched would be 4. 7 14 15 19 27 31 39 42 53 72 91 Using a binary search to find number 53 from the numbers above. The first item to be compared would be 31 (enter answers as a number)and the second number to be compared would be 53. Where as in a linear search it would take 9 searches to find 53. 12 8 15 20 18 25 This data will be sorted by going from the beginning to the end data item by swapping items in pairs, this is called a bubble sort. This sort is relatively easy to program and does not require a large amount of memory. After each item has been analysed or swapped from first to this this is called the first pass. After the first pass the item that will be in the first position will be number 8 (enter the answer as a number). When you believe you have sorted the data out the computer will then go through the data again. On the occasion that this happens it is the last pass and the sort is then complete. It would therefore take 3 passes to complete this sort Match the search / sort to their correct description Binary search Find data by splitting the list in half and then checks if this is the item. If not it will then see if it is higher or lower. The data must be ordered to w Bubble sort Puts data in order by swapping items in a list Linear search An inefficient way of searching for data, though it will work on un-ordered lists. Checks through every item one at a time. Merge sort Will sort data by splitting the list of data in half until only one item remains. It will then pair up items again but putting them in order as it happens. This is an efficient way to sort data but it requires more memory due to the number of lists that need to be made Insertion sort Sorts data out by choosing the second item, compares it to all items before it and then insert it in place, then makes it way through the list (like sorting a deck of cards). The image above can be represented as P=NOT (A AND B). If P = 1 and A = 1 what will be the value of B? 0 1 Both could be correct