Comp Exam paper 1 Flashcards
What is meant by recursion?
A recursive route is one that is defined in terms of itself
How do stacks work?
They store items and follow a last in first out (LIFO) rule. (Like taking from a stack of plates). Used to stored actions so they can be undone.
What does pushing the stack do?
Used to add items to the stack. Pushes the top position of the stack up and adds the item to the stack.
What does popping the stack do?
Used to remove elements from the stack. Moves the top of the counter down and removes the item.
What function has a constant time?
f= O(n^0)
f=O(1)
What function has a logarithmic time?
f= O(log n) : The Binary search
List is split into half with one rejected
f = O(n log n) : Merge sort
What function has a linear time?
f= O(n) : Linear Search
Checks each element of the list individually
What function has a polynomial time?
f= O(n^2) : Bubble sort- swaps item if one is bigger
What function has exponential time?
f= O(2^n) : Fibonacci
What function has factorial time?
f= O(n!) : Travelling salesman problem
What are intractable problems?
Problems that can be solved by a computer, but not in a reasonable amount of time when there are large inputs. (Less than polynomial time)
What is an heuristic approach?
A guessed solution can be checked in polynomial time. Problem becomes tractable.
What is the halting problem?
An unsolvable problem which asks whether it is possible to create a program which takes another program as an input and determines whether it will halt or loop infinitely.
How should you compare Algorithms?
Time complexity: How long it takes to complete a task with a given input
Space complexity: How much memory an algorithm needs to complete a task with a given input
Order of growth: How quickly the complexity grows with growth in input size
What is the proof of the halting problem?
def(g):
If halts(g):
loop_forever()
If halts(g) is true, g will call loop forever and will never halt.
If halts(g) is false, g will halt as it doesn’t call loop forever. This is a contradiction.How do queues work?
They follow a first in, first out rule (FIFO). Has a front of queue, end of queue, size of queue and max size of queue.
What is a static data structure?
They have a fixed size The allocated memory cannot change at runtime. An example is a static array. Doesn’t have overflow or underflow errors
What is a dynamic data structure?
It’s size can grow or shrink at runtime. Often consists of pointers. More efficient use of memory
What are the differences between static and dynamic structures?
Static data structures have a fixed maximum size, whereas the size of dynamic data structures can change
What does peeking the stack do?
Looks at the previous item in the stack
What are trees and graphs?
A way of representing real world problems. It has vertices and edges
What is used to models trees and graphs?
Arrays
When would you use an Adjacency matrix?
When there are many connections (edges)
When would you use an Adjacency list?
When there are few edges(connections)
What is a weighted graph?
A graph with edges that are labelled with numbers (a weight)
How would you trace a breadth-first search? ⭐️
Use a queue and would find the route with the great vertexes between the start and the end. Finds shortest path for an unweighted graph.
How would you trace a depth first search?
Use a stack and exhaustively search each branch to its depth, then back track. Uses less more than breadth first search. Good for navigating a maze.
What is the purpose of Dijkstra’s algorithm?
It finds the shortest path between a node and every other node in a weighted graph. Similar to breadth search but uses a priority queue rather than fifo.
What are the properties of a tree?
It is a connected, unidirectional graph with no cycles.
What is an array?
A data structure that holds similar or related data
What is a one dimensional array?
A type of linear array. Good for storing a vector
What is a two-dimensional array?
Can be visualised on a grid with rows or columns. Good for representing a matrix
