| Quick sort doesn't use additional memory like merge sort does | What are 4 examples of abstract data types? |
| - Keys pressed on a keyboard
- Printer Queue | What are 2 real world examples of queues? |
| enQueue(item) | how do you add an item to the end of a queue? (code) |
| Removes the front item from the queue and returns it | What does deQueue() do? |
| isEmpty() | how do you check if a queue is empty? |
| isFull() | how do you check if a queue is full? |
| - Dynamic data structures are ones which can grow or shrink in size
- They require a heap in order to work | What is a dynamic data structure and what do they require in order to work? |
| A portion of memory from which space is automatically allocated or de-allocated as needed | What is the heap? |
| A list | What's an example of a dynamic data structure in python? |
| May grow too large and cause overflow, crashing the program | What's a downside of using a dynamic data structure |
| - moving the items forward items are removed (may cause long processing time with large queues)
- keeping the items in place and using pointers instead | What are 2 ways of implementing a linear queue? |
| - Space which can't be filled will slowly show up at the start of the queue
- Can be fixed with a circular queue - putting new items at the start of the queue once the end is reached like a loop | What is an issue with using pointers in a linear queue and how can it be fixed? |
| A queue where the items are ordered by priority, not order in which they were added | What is a priority queue? |
| Check the priority of each item in the queue, starting at the back and moving it along one place until an item with the same or lower priority is found, at which point the new item can be inserted | How would you implement a priority queue? |
| Trying to pop from a stack which is already empty | In the context of stacks, what is underflow? |
| myList.isEmpty() | In python, how do you test if a list "myList" is empty? |
| - Pressing the back button on a web browser
- Pressing undo in photoshop or word | What are two common everyday applications of a stack? |
| - A pointer to the top of the stack
- A var holding the size of the array (the maximum size of the stack) | A stack can be implemented with either a dynamic or a static data structure, what two additional variables are needed if a static data structure is used? |
| push(item) | How do you add a new item to a stack? (code) |
| pop() | How do you remove and return an item from a stack? (code) |
| Returns the top item from the stack without removing it | In the context of stacks, what does peek() do? |
| The address of the instruction that control should return to when a subroutine ends | What does the call stack hold? |
| - Stack frames are groupings in the stack, they show the stuff related to different subroutines called | What is a stack frame? |
| MOD returns the remainder of a division, DIV just divides the number | What's the difference between MOD and DIV? |
| initialises the queue | What does this pseudocode do? (queues)
front = 0
rear = -1
size = 0
maxSize = size of array |
| Checks if the queue is empty | What does this pseudocode do? (queues)
if size == 0 then
return True
else
return False
endif |
| Checks if the queue is full | What does this pseudocode do? (queues)
if size == maxSize then
return True
else
return False
endif |
| Adds an element to the queue | What does this pseudocode do? (queues)
if isFull then
print("Queue full")
else
rear = (rear + 1) MOD maxSize
q[rear] = newItem
size = size + 1 |
| Removes an item from the queue | What does this pseudocode do? (queues)
if isEmpty then
print("Queue empty")
item = Null
else
item = q[front]
front = (front + 1) MOD maxSize
size = size - 1 |
| Functions produce information, procedures perform a task | What's the difference between functions and procedures? |
| Function - input("bruh")
Procedure - print("bruh") | Give one python example of a function and one of a procedure |
| - small enough to be easily understood and debug
- subroutines can be tested independently
- once thoroughly tested, a subroutine can be reused with confidence in different programs
- modular approach makes it easier for multiple programmers to collaborate | What are some advantages of using subroutines? |
| Recursion is calling itself within itself, iteration is just looping | What is the difference between recursion and iteration? |
| Recursive algorithms are often much shorter but they can cause stack overflow if called too many times, an iterative routine has no limit to the number of times it can be called | What's one advantage and one disadvantage of recursion over iteration? |
| Round down | (binary search) how do determine the middle item in a list with an even number of items? |
| (first + last) / 2 | When coding a binary search algorithm, how do you find the middle item? |
| - binary search
- merge sort | what is one search and one sort algorithm that use divide and conquer? |
| There must be a condition which will end the recursion, otherwise it will go forever until stack overflow | What is a requirement when using recursion? |
| Quicker - good time complexity
Takes more space - bad space complexity | What are the advantages and disadvantages of merge sorts in terms of time and space complexity? |
| Quick sort doesn't use additional memory like merge sort does | What is the advantage of quick sort over merge sort? |
| left subtree -> root node -> right subtree | What order is the tree traversed in an in-order traversal? |
| left subtree -> right subtree -> root node | What order is the tree traversed in a post-order traversal? |
| root node -> left subtree -> right subtree | What order is the tree traversed in a pre-order traversal? |
| A binary search tree | What is a typical use of a rooted tree? |
| - An array of records
- left, data, right | When implementing a binary search tree, what would be the appropriate data type and what would be the 3 pieces of data which would need to be stored? |
| In-order traversal | Which tree traversal order is ideal for searching efficiently? |
| The pointer will hold the value "null" | In a linked list, how do you know a node is the last one? |
| Integrated Development Environment | What does IDE stand for? |
| a software package that helps you write code more easily | What is an IDE? |
| Normal: 1 and 99
Boundary: 0 and 100
Erroneous: -1 and 101 | If something required an input between 1 and 100, what would be an example or normal data, boundary data, and erroneous data? |
| Running through a program on paper and noting down when variables change in the trace table | What is dry-running? |
| passing variables into and out of a subprogram (procedure e.g. function) | What is parameter parsing? |
| By Value - when you don't want the subprogram to change the value of the variable (input) - only passes the actual value of the var
By Reference - when you want to get data from the subprogram (output) - passes the memory location of the var, therefore allowing it to be changed | What are the two types of parameter parsing? (name and description) |
| Backtracking is incrementally building up towards a solution, abandoning partial success when the solution can't be completed and then going back to a previously successful match - for example, getting to a dead end in a maze and then going back slightly to try a different way | What is backtracking and what is an example of it? |
| Analysing vast amounts of data in order to discover new information and trends | What is data mining? |
| making use of experience to find a solution which is 'good enough' - like an educated guess | What are heuristics? |
| Statements used to select which statement will be executed next, depending on some condition
For example, an if statement | What are selection statements? And what is an example in terms of code? |
| Switch or Case statement | What is an alternative to a nested if statement? |
| switch choice:
burger: print("you have selected option burger")
fries: print("you have selected option fries")
drink: print("you have selected option drink")
else:
print("You must select either burger, fries or drink")
endswitch | How does a switch statement work? |
| The underground map | What is an example of abstraction that I'd be familiar with living in London? |
| Grouping by common characteristics - "is a type of" | What is abstraction by generalisation? |
| A logical description of how data is viewed and the actions which can be performed on it, not how those actions are actually physically carried out | What is data abstraction? |
| How a procedure is called, what arguments are required, what data type each one is, and what order they need to be written in | What is procedure interface? |
| Breaking down a problem into sub-problems to make it easier to solve | What is problem decomposition? |
| Breaking down a problem into individual tasks and then breaking the tasks into subtasks and so on until each subtask is simple enough to be written as a self-contained module or subroutine | What is top-down design and where is it especially useful? |
| Parallel computing is when multiple tasks are being executed simultaneously - requires multiple processors
Concurrent processing is when multiple tasks are running at the same time but by sharing processor time | What's the difference between parallel and concurrent computing? |
| - More tasks completed in a given time
- Time that would be wasted by the processor waiting for the user to input data is used on another task
- But if a large number of users are all trying to run programs and some of these programs involve a lot of computation, they'll take longer to complete | What are two advantages and a drawback of concurrent processing? |
| - Several tasks can be completed simultaneously by different processors
- A browser can display several webpages in different windows and still run a lengthy search simultaneously
- But some tasks may run faster with a single processor | Two benefits of parallel processing and one drawback |
| - An algorithm which always executes in the same time, regardless of the size of the data set
- O(1) | What is a constant complexity (Big O) and what is the notation? |
| - An algorithm which halves the data set in each pass (good for large data sets)
- O(log n) | What is a logarithmic complexity and what is the notation? (Big O) |
| - An algorithm whose performance is proportional to the size of the data set and declines as the data set grows
- O(n) | What is linear complexity and what is the notation? (Big O) |
| - An algorithm whose performance is proportional to the SQUARE of the size of the data set. Significantly reduces efficiency with increasingly large data sets
- O(n^2) | What is polynomial complexity and what is the notation? (Big O) |
| An algorithm that doubles with each addition to the data set in each pass. Inefficient and should be avoided
- O(2^n) | What is exponential complexity and what is the notation? (Big O) |
| Constant - O(1) | What is the Big O notation for an algorithm with no loop? |
| Linear - O(n) | What is the Big O notation for an algorithm with a for/while loop? |
| Polynomial - O(n^num of loops) | What is the Big O notation for an algorithm with a Nested loop? |
| Exponential - O(2^n) | What is the Big O notation for a recursive algorithm? |
| A repeat until loop checks the condition at the END of each loop so it will always run at least once | What is the difference between a while loop and a repeat until loop? An the effect of the difference. |
| Ensures that each subroutine is completely self-contained | What is the advantage of local variables for subroutines? |
| Giving the computer a list of instructions on what is should do step by step in order to finish the task at hand | What is procedural programming? |
