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

What is the Merge sort algorithm’s 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 so a program taking less time to run will cost less money

Question 4

Give two reasons why a smaller space complexity is better

Answer 4

• A program that uses less memory could be run on 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 up to n comparisons.

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

One or more arguments to a function are fixed, creating a new function with fewer arguments.

Question 12

What is a URL?

Answer 12

• A Uniform Resource Locator (URL) is the address of a webpage or other internet resource
• It indicates the location of a resource as well as the protocol used to access it.

Question 13

What is a domain name server?

Answer 13

A server that contains databases which map FQDNs to their corresponding IP addresses.

Question 14

‘www.w3schools.com’ is an example of a…

Answer 14

Fully qualified domain name

Question 15

‘www’ is an example of a…

Answer 15

Host name or subdomain

Question 16

‘w3schools.com’ is an example of a…

Answer 16

Domain name

Question 17

‘/cs/cs_operators.asp’ is an example of a…

Answer 17

Path

Question 18

Describe how domain names are organised

Answer 18

• Hierarchical organisation
• Top level domains are com/org/uk etc
• Second level domains are ac/co etc
• Domains can have subdomains created for them

Question 19

What is the purpose of a domain name?

Answer 19

• 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 20

What is the purpose of a domain name server?

Answer 20

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

Question 21

What is the domain name system?

Answer 21

• 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 22

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

Answer 22

The query will be passed to another DNS server

Question 23

Who manages top level domains?

Answer 23

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

Question 24

What are the three main responsibilities of an internet registry?

Answer 24

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 25

Give two examples of top level domains

Answer 25

.uk .org

Question 26

What is meant by baud rate?

Answer 26

The maximum number of times that a signal **changes per second**.

Question 27

What is meant by bit rate?

Answer 27

The number of bits transmitted over a medium per second

Question 28

Bit rate equation

Answer 28

bit rate of channel = (baud rate) x (number of bits per signal change/sample/word length)

Question 29

What is Serial Data Transmission?

Answer 29

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

Question 30

What is Parallel Data transmission?

Answer 30

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

Question 31

Give two problems with Parallel Data transmission

Answer 31

- Unreliable over long distances because of **skew** - Parallel wires also suffer from **crosstalk**

Question 32

What is skew?

Answer 32

As each wire has slightly **different properties**, there is a possibility bits could travel at **different speeds** over each of the wires and arrive at **different times**, meaning the signals might **overlap**

Question 33

What is cross-talk?

Answer 33

Interference between different lines, which causes data corruption

Question 34

Give three advantages of serial over parallel transmission

Answer 34

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 35

What is bandwidth? What unit is it measured in?

Answer 35

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

Question 36

What is latency?

Answer 36

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

Question 37

What is synchronous transmission?

Answer 37

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

Question 38

What is asynchronous transmission?

Answer 38

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

How are start and stop bits used in asynchronous transmission?

Answer 39

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

What is a worm?

Answer 40

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 41

What is a virus?

Answer 41

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

What is a trojan?

Answer 42

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

How can you prevent malware?

Answer 43

1. Improving code quality 2. Monitoring 3. Protection

Question 44

Describe Monitoring, Protection, and Code quality measures that can be used to reduce the threat posed by viruses. Give 2 points for each of monitoring, protection and code quality.

Answer 44

**Monitoring** Any 2 from: -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** Any 2 from: -Anti-virus; -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** Any 2 from: -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;