Set 8

Question 1

Why is space complexity important to consider when analysing binary tree search?

Answer 1

Because the algorithm is recursive, it places a demand on the call stack

Question 2

Merge sort complexity

Answer 2

O(n log n)

Question 3

Give two reasons why smaller time complexity is better

Answer 3

• A quicker program could solve more of the same problem or run more programs in the same time period
• Computers consume electricity to run…

Question 4

Give two reasons why a smaller space complexity is better

Answer 4

• 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

Question 5

What is the purpose of Dijkstras algorithm?
Can the graph be directed/weighted?

Answer 5

• Calculates the shortest path between a node and all other nodes in a graph
• Graph may be directed or undirected
• Graph must be weighted

Question 6

What approach does merge sort take to sort a list?

Answer 6

Divide and conquer

Question 7

What is bubble sort’s time complexity? Why?

Answer 7

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.

Question 8

Hierarchy of complexities (polynomial, logarithmic, constant, exponential, linear)

Answer 8

constant < logarithmic < linear < polynomial < exponential

Question 9

What is a first class object?

Answer 9

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

Question 10

What does function application mean?

Answer 10

Applying a function to its arguments

Question 11

What does partial function application mean?

Answer 11

Parțial function application means only applying a function to some of its arguments. The result is a function.

Question 12

What is the purpose of a domain name?

Answer 12

• 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

Question 13

What is the purpose of a domain name server?

Answer 13

To translate a fully qualified domain name into its corresponding IP address

Question 14

What is the domain name system?

Answer 14

• The domain name system is a distributed database of mappings from FQDNs to their corresponding IP addresses
• DNS servers are organised into a hierarchy

Question 15

What happens if a domain name server cannot resolve a lookup?

Answer 15

The query will be passed to another DNS server

Question 16

Who manages top level domains?

Answer 16

• An (internet) registry
• Each TLD may have restrictions as to who can use it

Question 17

What are the main responsibilities of an internet registry?

Answer 17

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

Question 18

Give two examples of top level domains

Answer 18

.uk .org

Question 19

What is meant by baud rate?

Answer 19

The maximum number of signal changes in a medium per second

Question 20

What is meant by bit rate?

Answer 20

The number of bits transmitted over a medium per second

Question 21

Bit rate equation

Answer 21

bit rate of channel = (baud rate) x (number of bits per signal change)

Question 22

What is Serial Data Transmission?

Answer 22

Bits are sent one after the other over a single wire from source to destination

Question 23

What is Parallel Data transmission?

Answer 23

• Multiple bits are sent simultaneously over multiple wires from source to destination
• Each bit is sent down a different wire

Question 24

Give two problems with Parallel Data transmission

Answer 24

• Unreliable because of skew
• Parallel wires also suffer from crosstalk

Question 25

What is skew?

Answer 25

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**

Question 26

What is cross-talk?

Answer 26

Interference between different lines, which causes data corruption

Question 27

Give three advantages of serial over parallel transmission

Answer 27

1. Serial transmission doesn't suffer from **skew or cross-talk** 2. Serial is **reliable** over much longer distances 3. Serial transmissions tends to be **cheaper**, as there is much less complexity and the physical size of cables is smaller

Question 28

What is bandwidth? What unit is it measured in?

Answer 28

- A measure of the maximum capacity of a communication channel - It is directly proportional to bit rate - Measured in bits per second

Question 29

What is latency?

Answer 29

A time delay before some component in a computer system responds to an instruction

Question 30

What is synchronous transmission?

Answer 30

- Data is transferred at regular intervals, synchronised by a clock signal - Receiver and transmitter clocks are synchronised

Question 31

What is asynchronous transmission?

Answer 31

- 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

Question 32

How are start and stop bits used in asynchronous transmission?

Answer 32

- 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

Question 33

What is a worm?

Answer 33

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.

Question 34

What is a virus?

Answer 34

* 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

Question 35

What is a trojan?

Answer 35

* 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

Question 36

How can you prevent malware?

Answer 36

1. Improving code quality 2. Monitoring 3. Protection

Question 37

How can you prevent malware? (BONUS EXTENSION MATERIAL)

Answer 37

**Monitoring** Firewall could block packets from sources Proxy server could receive/check downloaded files; Spam filters can block emails from suspicious sources Web filters can check websites against a list of websites known for having content that might contain a virus; Digital certificates can be used to verify the source of a downloaded file; Digital signature can be used to verify that a file has not been changed **Protection** Enable automatic update of applications Use a virtual machine to execute programs Set access rights to minimise risk of viruses being able to access sensitive files Disable execution of macros in documents from outside sources Restrict execution of software from unverified sources Encrypt files so that data cannot be extracted from them Backup data and keep offline so it can be recovered Disable the use of external drives Use a computer with the Harvard architecture to prevent data being executed as code Use a MAC address allow list so that only known devices can join a network **Code Quality** Ensure code does not allow buffer overflow Test software for security vulnerabilities Carry out a code review so the code is independently checked by another programmer Use code analysis software to identify flaws Only use libraries from the internet if required