|
Made up of multiple fields
|
|
Each field consists of a single data type
|
|
Each record is processed as a single item
|
|
Binary trees are tree entities wherein each element has no more than two children.
|
|
Pre-Order Traversal
1. Root
2. Left 3. Right |
|
In-Order Traversal
1. Left
2. Root 3. Right |
|
Post-Order Traversal
1. Left
2. Right 3. Root |
|
De Morgan's law states that NOT(A OR B) is the same as NOT(A) AND NOT(B).
|
|
Also, NOT(A AND B) is the same as NOT(A) OR NOT(B).
|
|
A recursive function is a function that calls itself repeatedly until a certain condition is met, at which point it "collapses" and returns a result.
|
|
Presence Check
|
This check ensures that something has been entered.
|
|
Range Check
|
Ensures that data is within a given range.
|
|
Type Check
|
Checks to make sure the data is of the correct type(i.e Integer, String, Float)
|
|
Format Check
|
Ensures that the data follows a particular format (for use with Post Codes)
|
|
List Check
|
Ensures that data is one of a given list of options, for example "M", "F" or "X" for a gender check
|
|
Length Check
|
Make sure that the data is of the correct length(in terms of characters, digits or elements)
|
|
1. Start from the first vertex, named A.
|
|
2. Work out the weight from the A to each other connected node, in this case B and C. Add these costs to a list and order the list from lowest cost to highest.
|
|
3. "Move" to the node that has the lowest cost in the list.
|
|
4. Calculate the cost to move from A to any nodes adjacent to the currently visited node, and add these costs to the list.
|
|
5. Ignore longer routes(for instance, going from A to B to C rather than A to C)
|
|
6. Repeat steps 2->5 until you arrive at your destination.
|
|
Stacks are LIFO(Last In, First Out), so items can be pushed or popped from the top of the stack
|
|
Stacks may be used for:
1. Storing return addresses 2. Storing intermediate steps in arithmetic operations 3. Interrupts |
|
A hash table is composed of both a table of data and a key. The key is a smaller file which identifies the location of a specific piece of data in the much larger table.
|
|
A hashing calculation is performed on each piece of data before it is placed into the table. The location it is placed at is determined via the result of the hash.
|
|
If there is a hash collision, one of two things will happen:
1. Chaining - This is where a list is created in the memory location where a collision has occurred and each element that is stored there becomes an element in that list.
2. Rehashing - This involves running another hashing algorithm on the result of the first hash to obtain a new memory location. |
|
Screen Verification
|
This is a visual check to ensure that no errors have been made. For instance, sending the data back to the source to check over it.
|
|
Double-Keying
|
This is where data is entered twice to confirm i.e passwords or e-mail addresses.
|
|
Check Digit
|
This can be used for numerical data like credit card numbers or ISBNs, where one digit is the result of a mathematic calculation performed on the others.
|
|
Some of the data is "lost" during compression
|
|
Lossy data types include JPEG, MPEG or MP3
|
|
Queues are FIFO(First In, First Out).
|
|
These would be used for
1. Holding tasks for the computer to run 2. A keypress buffer 3. Spooling output to a disk while waiting for a printer |
|
Graphs can relate any number of element to any other number of elements.
|
|
A Weighted Graph is where there is a value on each edge which represents the "cost" of traversing it.
|
|
Graphs can either be directed or undirected.
1. A directed graph is a graph wherein there is a one-way relationship between each node.
2. An undirected graph is a graph wherein the relationship is bidirectional between each node. |
|
What it looks like
|
What it is
|
|
Weird Double-Square Lookin Thing
|
External Entity
|
|
Rounded Square
|
Process
|
|
Rectangle Missing the Right Edge
|
Data Storage
|
|
Arrow
|
Represents the flow of data(should be labelled)
|
|
Constant Time
O(1) |
No matter how much data you give this algorithm, it will always execute in the same amount of time.
|
|
Linear Time
O(n) |
The time taken for the algorithm to run is directly proportional to the size of the input data.
|
|
Polynomial Time
O(n2) |
The time taken increases proportional to the square(or cube, or any other power greater than one) of the input size.
|
|
Exponential Time
O(2n) |
The time taken will double with every additional unit(or triple, etc- the 2 can be any number greater than one) of input data.
|
|
Logarithmic Time
O(Log(n)) |
The time taken increases logarithmically, so the rate of increasing time with respect to input size actually decreases.
|
|
No data is lost in the process, and the entire original file can be reconstructed.
|
|
Another type of lossless compression is via Dictionary Encoding, where the most frequent elements of data are removed and instead replaced with a "token" that points to the piece of data somewhere else in the file to prevent needless data duplication.
|
|
Also in Huffman Coding, the most frequent elements of data are given the shortest token to maximize compression.
|
|
One type of lossless compression is known as Run Length Encoding, where strings of the same data(e.g, "BBBBBBBB") are replaced with the number of times to place the data in a row when decompressing it.(8B)
|
No comments yet.
Cheatography n. The art of mapping complex subjects into clear, instantly navigable reference guides.
