Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
J277DAV 2.1.1
J277 GCSE CS 2.1 Algorithms
| Question | Answer |
|---|---|
| What is Abstraction and why do we use it in Computing? | WHAT—ABSTRACTION IS THE PROCESS OF REMOVING DETAIL THAT IS UNECESSARY FOR THE SCENARIO. THIS ALLOWS THE DEVELOPER TO FOCUS ON THE PROCESSES AND DATA THAT MATTER WHY—reduces complexity of the problem (relate to scenario) Requires less computing resources (memory storage etc.) |
| What is Decomposition? | Breaking a problem down into smaller sub-problems, making the overall problem easier to solve. |
| Advantages of decomposition? | Smaller problems are easier to solve. Can be tested independently Good for team of programmers - each can focus on a sub-problem |
| Why do we use abstraction in computing? | Allows the programmer to focus on the processes and data that are important. This reduces complexity of the problem (relate to scenario). This will reduce development time. The solution will require less computing resources (memory storage etc.) so will be able to run on a wider range of devices. |
| What is Algorithmic thinking? | Identifying the steps needed to solve a problem. Pseudocode or flowcharts often used for this. |
| Why do we use structure diagrams? | We use structure diagrams to help us decompose a problem. |
| Refine this code print(1) print(2) print(3) print(4) print(5) | for i =1 to 5: print(i) next i |
| Describe the steps of a Binary search | Identify the mid point in an ordered list. Compare midpoint to the item to be found. If it is same then output and stop. If item less than the mid point, discard right list. If it is greater than mid point, discard left list. Repeat steps until item is found or no items left. |
| Describe the steps of a Linear search | Start at the first item of an unordered list. Check if the item is the one to be found. If it is then output and stop. If not compare each item of the list in order to the value being searched for Finish if the item is found or you reach the last item of the list and it is not your value. |
| When would you use a linear search instead of a binary search? | Binary search can only be carried out on a sorted/ordered list. |
| What is the advantage of a binary search over a linear search? | Binary search is normally quicker to find the item you are searching for than linear for long lists. However list needs to be sorted for binary search. If list is very short or item being searched for is near beginning linear may be quicker |
| When does a binary search stop? | When the item you are searching for is found OR If there is one item left and it isn’t the item you are looking for |
| When does a linear search stop? | When the item you are searching for is found OR If you have reached the last item in the array and it isn’t the item you are searching for. |
| How does a Bubble sort work? | Compare first two items in a list (items 1 and 2). Swap if in the wrong order. Compare next 2 items (2 and 3). Swap if in the wrong order. Continue in order until the last two items have been compared and swapped if necessary. This is one pass Repeat this process (another pass) until no swaps are made. The list is now in order. |
| How does a Merge sort work? | Repeatedly split the list in half until each list contains only a single item. Combine two adjacent lists together by comparing each item in the lists in turn, inserting each item into the correct order in the new list. Repeat until one list is created. (If sorting a list of 8 items this will look like lists of 1 item, sorted lists of 2 items, sorted lists of 4 items, sorted list of 8 items) |
| What is an advantage of a merge sort over a bubble sort ? | A merge sort is quicker to sort for large lists or lists that are more unordered. |
| What is an advantage of a merge sort over a insertion sort ? | A merge sort is quicker to sort for large lists or lists that are more unordered. |
| What is an Insertion sort? | This example assumes list will be ascending order: Element 1 is a ‘sorted’ list. The rest of the elements are an ‘unsorted’ list. Compare the first element in the ‘unsorted’ list to each element in the sorted list. IF it is smaller, put it in in front of that element (move the others along). IF larger or no more elements in the sorted list element is in position. REPEAT with the new first elements of the unsorted list UNTIL all element in the ‘unsorted’ list are in the ‘sorted’ list. |
| What is Pseudocode or exam reference language? | A language independent description of the steps of an algorithm. Intended for humans to express and design algorithms before coding. |
| What is a flow chart? | A method of designing algorithms before coding using symbols to show inputs, outputs and processes. |
| What flow chart shape has two horizontal lines with curved vertical lines? | Terminal flow diagram symbol. Start of an algorithm. End of an algorithm. |
| Which flow chart shape is a horizontal rectangle? | Process flow diagram symbol. Used to show changing variables. Example use: counter = 5 |
| Which flow chart shape is a diamond and has two outputs? | Decision flow diagram symbol. Used to show a program branch. Yes and No arrows are used from this symbol. Example use: IF counter = 5 |
| Which flow chart shape is a slanted parallelogram | Input/output flow diagram symbol. Indicates an input from the user. Indicates an output to the user. |
| Which flow chart shape is a horizonal rectangle with an additional 2 vertical lines inside the rectangle? | Sub-routine call flow diagram symbol. Used to show a call to a procedure or function in another flow diagram. |
Created by:
Davenant Computer Science
Popular Computers sets