wds Flashcards
(34 cards)
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
