Set 8 Flashcards
Need to add time complexity cards. card 36 needs updating
Why is space complexity important to consider when analysing binary tree search?
Because the algorithm is recursive, it places a demand on the call stack
Merge sort complexity
O(n log n)
Give two reasons why smaller time complexity is better
- A quicker program could solve more of the same problem or run more programs in the same time period
- Computers consume electricity to run…
Give two reasons why a smaller space complexity is better
- A program that uses less memory could run off cheaper hardware (as less RAM is needed)
- Or a greater number of different algorithms can run on the same hardware simultaneously
What is the purpose of Dijkstras algorithm?
Can the graph be directed/weighted?
- Calculates the shortest path between a node and all other nodes in a graph
- Graph may be directed or undirected
- Graph must be weighted
What approach does merge sort take to sort a list?
Divide and conquer
What is bubble sort’s time complexity? Why?
O(n^2). Since it involves a for loop within a for loop. You need to do n passes of the list/array, and each pass involves swapping all the way down the list.
Hierarchy of complexities (polynomial, logarithmic, constant, exponential, linear)
constant < logarithmic < linear < polynomial < exponential
What is a first class object?
First class objects are objects which may:
- R - be returned in function calls
- A - be assigned as arguments
- V - be assigned to a variable
- E - appear in expressions
Functions are first-class objects in functional programming languages
What does function application mean?
Applying a function to its arguments
What does partial function application mean?
Parțial function application means only applying a function to some of its arguments. The result is a function.
What is the purpose of a domain name?
- A domain name identifies an organisation or individual on the internet.
- They use alphanumeric characters which make them easier for humans to remember than IP addresses
What is the purpose of a domain name server?
To translate a fully qualified domain name into its corresponding IP address
What is the domain name system?
- The domain name system is a distributed database of mappings from FQDNs to their corresponding IP addresses
- DNS servers are organised into a hierarchy
What happens is a domain name server cannot resolve a lookup?
The query will be passed to another DNS server
Who manages top level domains?
- An (internet) registry
- Each TLD may have restrictions as to who can use it
What are the main responsibilities of an internet registry?
To maintain a definitive register of who owns a specific domain.
To enter domain names to IP address mappings into the DNS system
The ensure domain names are unique, and only used by one organisation
Give two examples of top level domains
.uk .org
What is meant by baud rate?
The maximum number of signal changes in a medium per second
What is meant by bit rate?
The number of bits transmitted over a medium per second
Bit rate equation
bit rate of channel = (baud rate) x (number of bits per signal change)
What is Serial Data Transmission?
Bits are sent one after the other over a single wire from source to destination
What is Parallel Data transmission?
- Multiple bits are sent simultaneously over multiple wires from source to destination
- Each bit is sent down a different wire
Give two problems with Parallel Data transmission
- Unreliable because of skew
- Parallel wires also suffer from crosstalk
What is skew?
As each wire has slightly different properties, there is a possibility bits could travel different speeds over each of the wires and arrive at different times, meaning the signals might overlap
What is cross-talk?
Interference between different lines, which causes data corruption
Give three advantages of serial over parallel transmission
- Serial transmission doesn’t suffer from skew or cross-talk
- Serial is reliable over much longer distances
- Serial transmissions tends to be cheaper, as there is much less complexity and the physical size of cables is smaller
What is bandwidth? What unit is it measured in?
- A measure of the maximum capacity of a communication channel
- It is directly proportional to bit rate
- Measured in bits per second
What is latency?
A time delay before some component in a computer system responds to an instruction
What is synchronous transmission?
- Data is transferred at regular intervals, synchronised by a clock signal
- Receiver and transmitter clocks are synchronised
What is asynchronous transmission?
- Receiver and transmitter clocks only need to be synchronised for the duration of data transmission
- Blocks of data are sent as soon as they are ready
How are start and stop bits used in asynchronous transmission?
- Start bit is sent to synchronise the clock in the receiver to the transmitter clock
- Stop bit allows the receiver time to process the current block of data before another is sent
- Stop bit is opposite to start bit to allows the next start bit to be recognised
What is a worm?
A piece of malicious software that can self-replicate between computers, either within a network (such as the Internet) or by a user downloading and running and malicious files.
Unlike viruses, worms are complete programs - they do not require a host program to cause damage.
What is a virus?
- A virus is a small program of self-replicating software that is attached to other program or files
- Viruses require a host file in which to reside
What is a trojan?
- A type of malware that is disguised as a legitimate benign file that users can be tricked into opening
- They can delete and modify data and allow more malware in once they are opened
How can you prevent malware:
- Improving code quality
- Monitoring
- Protection (e.g. up to date antivirus programs)
