Studied by 0 people
Who made a famous short path algorithm?
Dijkstra (Dike-Struh)
What does a shortest path algorithm do?
Finds the shortest path between two nodes in a weight graph.
What are 2 ways to traverse a graph?
Breadth
Depth
What is Breadth First search?
A node is checked entirely first before moving onto the next.
What is Depth First search?
An entire branch is explored before backtrackingD and truly checking each node.
What are the 3 ways to traverse a tree?
Pre-Order
In-Order
Post-Order
What type of trees are each of the 3 tree traversals meant for?
Pre-Order and Post-Order work with any tree.
In-Order is mainly meant to be used on Binary trees.
Why do we use Reverse Polish Notation?
Eliminates need for brackets.
Great use in Stacks
What does the Dijkstra Algorithm do?
Finds the shortest path between two nodes in a graph.
What are 2 sorting algorithms?
Bubble
Merge
What are 2 Searching Algorithms?
Linear
Binary
On what list can a Linear search be used?
Linear search can be used on any unordered list.
On what list can a binary search be used?
Binary searches can only be used on ordered lists.
What are the 2 ways RPN can be visualised?
Infix
Postfix
What are the 4 main Computer Science Constructs?
Sequence
Selection
Iteration
Assignment
SSIA
What is meant by Abstraction?
Removal of unrequired information. Keeping only what is necessary.
What is meant by Decomposition?
Breaking down of a problem into smaller and edible chunks.
What is meant by Composition?
The combination. Like composite
What makes up a Turing Machine?
Read & Write Head
Infinite Tape
Finite State Machine (FSM)
What symbol is used to highlight transition functions?
Greek Symbol Delta : δ
What is the difference between TM and UTM?
Turing Machine vs Universal Turing Machine is that the UTM can take in another input more than the general TM.
Why is the Turing Machine so important?
The Turing Machine explains the limits of computation as with this theoretical machine if to be impossible with such a machine then its stated to be an incomputable problem. Only provable through use of the Turing Machine
What does FSM stand for?
Finite State Machine
What does STD stand for?
State Transition Diagram
What does cardinality mean?
The Count meant to be used on a finite set stating the count within the set.
What does finite mean?
The ability to end.
What does infinite mean?
Unknowingly long.
How do you figure out the cartesian product?
Correct use of multiplication.
What is Regular Expression?
Simply put a way of describing a set.
What are the symbols used for Regular Expression?
‘*’ — Meaning zero or more
‘+’ — Meaning one or more
‘?’ — Meaning zero or one repeated (Optional)
‘|’ — Meaning “or“ a choice
‘()’ — Simply just groups them
Can sets contain other sets?
Yes. For those that fit. For example a set containing infinite numbers and one which include 1-10 they’ll defiantly be a set of a set.
What is set comprehension?
Expression of sets through selecting from larger general sets.
What is an empty set called?
{} or Ø
What is a subset?
Example:
A is a subset of B if it only contains items from Set B
Symbol : ⊆
What is a proper subset?
Example:
A is a proper subset of B if it only contains items from B but not all of them
Symbol : ⊂
What are the 3 different set operations?
Union
Intersection
Difference
What does Union do considering sets?
Union would take two sets and combine them into a brand new one combining everything from the previous two. (No Duplicates)
Symbol : ∪
What does Intersection do considering sets?
An intersection considering sets when taking two sets the brand new set that would be created would only included those within the previous sets that are found|duplicate in both of them.
Symbol : ∩
What does Difference do considering sets?
When a difference is applied to two sets the resulting brand new set will only include one of the previous in the brand new one completely removing the other.
Example:
A/B
This will only include those from set A
Symbol : /
What does BNF stand for?
Backus-Naur Form
Considering BNF What is the difference between Terminal and Non-Terminals?
Backus-Naur Form considering the difference between Terminal and Non-Terminals:
Terminal — CANNOT be broken down into simpler parts
Non-Terminals — CAN be broken down into simpler parts
Why use BNF?
Backus-Naur form allows for notation of Context free languages.
What does the Halting Problem prove?
The halting problems shows that there are computational problems that are not possible to be solved.
From best to worst-case what are the BigO classifications?
O(C)
O(log2(n))
O(n)
O(nlog(n))
O(n²)
O(n³)
O(2^n)
O(n!)
What is meant by Heuristic?
The best guess or rather rule of thumb. Expectation
What is the BigO for a Binary Search?
O(log2 (n))
What is the BigO for a Linear Search?
O(n)
What is the BigO for a Merge Sort?
O(nlog(n))
What is the BigO for a Bubble Sort?
O(n²)
What is the difference between Tractable and Intractable?
The difference to whether a problem can be done within a polynomial amount of time or not.
Tractable saying that it CAN.
It’s an intractable saying that it CANNOT.
What is the Halting problem?
The unsolvable problem of determining whether any program will eventually stop if given a particular input.
What does Countably Infinite mean?
Its more of statement really which states that all infinite sets can be counted off with use of the natural numbers set (also being infinite) technically meaning every value up to infinity does have a ordinal value.
What counts as a countable set?
finite sets
countably infinite sets
What are the 4 different types of abstraction?
Procedural
Functional
Data
Problem
What are the 7 different Data Structures?
Queue
Stack
Graph
Tree
Hash Table
Dictionary
Vector
QuickSilverGoTHDV
What are the 3 types of Queue?
Linear
Circular
Priority
What are Data Structures?
Data Structures act as containers for data acting almost as a next level sort of Data Type.
What are the 3 rules of Arrays?
Must be finite
Must be indexed
Must contain the same data type
What is the difference between 1 and 2 dimensional arrays?
One is simply linear with only data being labelled by its index, while 2 dimensional arrays look like tables containing a column and row.
What is an abstract data type?
There truly is no such thing as an abstract data type as all it does is take from other real data types and customize themself in their own way making them different to the original only then being labelled as abstract.
How do you interact with queues?
FIFO (First In First Out)
How does a linear queue function?
With use of 2 pointers:
Front Pointer
Rear Pointer
With these two it will add to the rear (being furthest right) and subtract from the front (being furthest left)
What happens if you reach the end of a linear queue?
CIRCULAR QUEUE!!! in a linear queue it’ll probably just say its full as the pointers always go to the first available space.
Considering a Circular Queue it has the power to go over the edge and loop back round like a circle so if there is space back at the beginning. it can be used.
How does a priority queue work?
Quite similar to that of a weighted graph. Everything is labelled with a value defining its importance in turn saying when it should be dealt with and if there are two of the same variant then simply they are treated as if its a regular queue. (FIFO)
How do you interact with stacks?
FILO (First In Last Out)
How do Stacks work?
Stacks work with a singular pointer known as the top pointer. (Like a stack of books)
What operations can be done on a stack?
Push — Adds an item to the stack
Pop — Removes an item from the stack
Peek — returns the value on top (No Removal)
IsFull , IsEmpty both work.
What are the parts of a graph called?
Nodes or Vertices
Get joined together by
Edges or Arcs
A Weighted graph has values assigned to these edges.
Instead of using a graph to present what else could be used?
An Adjacency list which displays all the relationships in a different way.
What is the difference between Adjacency Matrix and List?
Adjacency Matrixes store every possible edge there is even if they dont exist with the downside being it takes up more storage while the lists only look at the edges which exist and in turn take up less storage.
Adjacency Matrix is better for Dense Graphs
Adjacency List is better for Sparse Graphs
What are the 3 rules for trees?
Must be Connected
Must be an undirected graph
must have no cycles.
What makes a root node?
The Root Node is the first node at the top of a tree diagram. These trees contain parents and children.
To be a Root Node you must have no parents.
What is the difference between Trees and Binary Trees?
A Binary tree has no more that 2 children under a single parent.
What do Hash Tables do?
Hash Tables are a way of storing data that allows for it to be retrieved within a constant time complexity.
How do Hash Tables work?
Hash tables take a value and then hash the value masking it with something else and then never again reveal the original input and continue to use the hashed value instead.
How does Dictionary work?
Exactly like it works for compression when a specialized dictionary gets made in order to use duplicates and save entire phrases.
What is the difference between Static and Dynamic?
Static in regard to Data Structures mentions that they are set and final when it comes to questioning the amount of space or rather data they can hold while for dynamic they are able to change their size willingly.
What does sequential mean?
Sequential looks at order stating that one comes after the other.
What is it called if there happens to be too much data in a single structure?
A stack overflow. (An Overflow error)
What does Push do?
Push adds an item to a stack.
What does Pop do?
Pop removes an item from a stack.
What does Peek do?
Without removing anything it will check the top value.
How many pointers does a stack have?
1 — The Top Pointer
How many pointers do queues have?
2 — The Front and Rear Pointers
What are the two things which define Data Types?
Values in which they take.
The operations which can be performed with them.
What data type can only be true or false?
Boolean
What data type can only accept numbers?
Integer
What data type can only accept one singular input?
Char
What data type can store any other data type?
String
What is meant by assignment?
Providing either a variable or a constant with a value.
What is meant by iteration?
Repeating an instruction.
What is a subroutine?
A subroutine is a named block of code with the mission of being called frequently in order to perform an operation.
What is the difference between Definite and Indefinite?
Definite refers to the amount of iterations having a pre-determined end while indefinite has the possibility to go on for infinity. (or not)
What is indentation?
A incredibly common visual effect that is done to code in order to only make it more visually beneficial with only it having an actual effect once a syntax error has been made.
What does DIV do?
Divides but excludes the remainder.
What does MOD do?
Provides the remainder.
Why is a constant so good at its job?
Overall its easier:
Easier to update with it being in the same place to be used globally.
With the ability of such a variable able of receiving a name it means that it can be easier to understand.
What is concatenation?
Part of string manipulation where even two or more strings can be connected.
What subroutine must always return a value?
A Function
What can parameters be used for?
Passing data between subroutines.
Note
Flashcard