wds Flashcards
When is adjacency matrix more appropriate to use instead of an adjacency list?
When there are more edges between vertices
When is adjacency list more appropriate to use instead of an adjacency matrix?
When there are few edges between vertices
What is a graph?
A nonlinear abstract data structure
What are two examples of linear data structures?
Queue
Stack
What are two examples of non-linear data structures?
Graph
Tree
What does a graph consist of and what can they be used to represent?
Consist of vertices and edges
To record relationships between objects
What properties must a graph have for it to be a tree?
- No cycles
- Undirected
- Connected
Where should I place the dot and number to solve a pre-order traversal?
On the left and use a dotted line around the outside starting from the root
Where should I place the dot and number to solve a In-order traversal?
Below - Starting with the left leaf
Where should I place the dot and number to solve a post-order traversal?
On the right - Starting from the left leaf
What can a programmer do to ‘solve’ an intractable problem?
An algorithm could make an educated guess based on previous data
How can a Universal Turning machine be considered as a interpreter?
It reads instructions one at a time and executes the instructions
What is representational abstraction?
Removing (unnecessary) details;
What is abstraction by generalisation?
Grouping by common characteristics // a hierarchical / ‘kind-of’ relationship;
Explain the circumstances when it would be more appropriate to use an adjacency
matrix instead of an adjacency list.
Adjacency matrix appropriate when there are many edges between vertices
When graph/matrix is not sparse;
When edges frequently changed;
When presence/absence of specific edges needs to be tested frequently;
What is BNF (Backus-Naur Form)?
A formal mathematical way of defining syntax unambiguously
Describe the relationship between regular expressions and FSMs.
Regular language can be defined as any language that a FSM will accept
What is Universal Turing Machine?
A Turing machine that can execute the behaviour of any other Turing
machine // can compute any computable sequence
What the difference between a local and global variable?
Local variables only be accessed in a subroutine of a program whereas global variables can be assessed from any part of the program
Why is it good practice to use local variables?
Less chance of accidently changing the value of a variable
Why is reverse polish notation sometimes used instead of infix notation?
- Simpler for a computer to evaluate
- Doesn’t need brackets
Describe the halting problem?
Determining if a program will halt without running the program for an particular input
Why is it not possible to create a Turing machine that solves the halting problem?
The Halting problem is non-computable and there is no algorithm that solves the Halting problem
What components must a Turing machine have?
- Read-write head
- Start state
- Current state
- Finite set of states
Why is a Turing machine more powerful than any computer?
Because it has an infinite amount of memory
Why is a circular queue better than a linear queue?
- Linear queues can have wasted space that’s not able to be used
- To avoid all items being moved forward when an item is deleted from the queue
What is meant by recursively-defined?
A procedure/ subroutine that can call itself
What is the big O notation for Bubble Sort, Merge Sort, Binary Search and Linear Search?
O(log n): Binary Search - GOOD
O(n): Linear - DECENT
O(n^2) : Bubble Sort - POOR
O(nlog n): Merge Sort
What is the big O notation for bubble sort?
O(n^2) : Bubble Sort - POOR
What is the big O notation for merge sort?
O(nlog n): Merge Sort
What is the big O notation for Binary Search?
O(log n): Binary Search - GOOD
What is the big O notation for Linear Search?
O(n): Linear - DECENT
What’s the difference between a static and dynamic data structure?
-Static data structures have storage size determined before program is
run
-Dynamic data structures can grow/shrink during execution
What’s the difference between a protected attribute and a private attribute?
A protected attribute can be accessed (within its class and) by derived class instances / subclasses; A private attribute can only be accessed within its class;
