Flashcards in S1 - Algorithms (Done) Deck (25)
What is computational thinking ?
The steps you take to find the best solution to a complex problem.
What are the three key techniques for computational thinking ?
Decomposition, abstraction and algorithmic thinking.
What is decomposition ?
Breaking down a complex problem into smaller problems and solving each one individually.
What is abstraction ?
Picking out the important bits of info from a problem.
What is algorithmic thinking ?
A logical way of getting from the problem to the solution.
What is pseudo-code ?
Not an actual programming language, follows a similar structure without worrying about the syntax. Quick to write and easily converted into other programming languages.
What are the two main search algorithms ?
Binary and linear search.
When are binary and linear searches used ?
Binary searches are used in an ordered list, whereas a linear search is used in an un-ordered list.
How would you find the middle item in a list ?
make the length of the list n, and do (n + 1) ÷ 2 and round up if necessary.
How would you complete a binary search ?
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.
How would you complete a linear search ?
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.
What are the two sorting algorithms ?
A bubble sort and merge sort.
How do you do a bubble sort ?
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.
What are the advantages of a bubble sort ?
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.
What are the disadvantages of a bubble sort ?
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.
How do you do a merge sort ?
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.
What are the advantages of a merge sort ?
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.
What are the disadvantages of a merge sort ?
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.
What is the difference between a linear and binary search ?
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.
In a flow chart what represents a start or stop ?
Boxes with rounded corners, at the beginning and end of an algorithm.
In a flow chart what represents inputs or outputs ?
Parallelogram boxes, holds anything that goes in or out of the algorithm.
In a flow chart what represents processes ?
Rectangular boxes, contains general instructions, processes and calculations.
In a flow chart what represents a decision ?
Diamond boxes, containing yes or no questions with two paths it can follow depending on this.
In a flow chart what represents a subroutine ?
Rectangular boxes with additional lines on either end, referencing other flowcharts.