Set 10 Flashcards
1
Q
What is representational abstraction?
A
A representation arrived at by removing unnecessary details
2
Q
What is abstraction by generalisation or categorisation?
A
A grouping by common characteristics to arrive at a hierarchical relationship of the ‘is a kind of’ type.
3
Q
What is information hiding?
A
The process of hiding all details of an object that do not contribute to its essential characteristics
4
Q
What is procedural abstraction?
A
- Procedural abstraction involves breaking down a complex model into a series of reusable procedures.
- The actual values used in a computation are abstracted away and a computational method is achieved
5
Q
How is functional abstraction different from procedural abstraction?
A
- Functional abstraction requires yet another abstraction from procedural abstraction
- While the result of a procedural abstraction is a computational method, the function disregards the particular computation method
6
Q
What is data abstraction? Give an example
A
- The process of isolating how a compound data object is used from the details of how it is constructed. Data abstraction forms the basis of abstract data types
- For example, a stack could be implemented as an array and a pointer for the top of the stack
7
Q
What is problem abstraction/reduction?
A
The process of removing details until the problem is represented in a way that is possible to solve, because the problem reduces to one that has already been solved
8
Q
What is (procedural) decomposition?
A
The process of breaking a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided
9
Q
What is (procedural) composition?
A
The process of combining procedures to form compound procedures
10
Q
What is automation? How is it achieved?
A
The process of putting models (abstractions of real world objects/phenomena) into action to solve problems. This is achieved by:
1. creating algorithms
2. implementing the algorithms in program code
3. implementing the models in data structures
4. executing the code.
11
Q
When is a problem “computable”?
A
If there is an algorithm (in principle) that solves the problem
12
Q
When is a problem “non-computable”?
A
If no algorithm can ever exist which solves the problem
13
Q
What is a intractable problem?
A
A computable problem for which a polynomial time (or better) algorithm does not exist
14
Q
How do programmers find “solutions” to intractable problems?
A
By developing tractable heuristic algorithms and methods, which find approximate (but not necessarily optimal) solutions.
15
Q
What is the trade-off that must be considered when developing heuristic algorithms?
A
speed vs correctness
16
Q
What is an undecidable problem? Give an example
A
- A decision problem that is non-computable
- e.g. the halting problem
17
Q
What is the halting problem?
A
The undecidable problem of determining whether any program will eventually halt on given particular input without running the program
18
Q
What is the significance of the halting problem?
A
The halting problem demonstrates that some problems are non-computable, meaning they cannot be solved by a computer
19
Q
Why can a Universal Turing Machine be considered to be more powerful than any computer that you can purchase?
A
Because it has an infinite amount of memory
20
Q
Name one example of a model of computation
A
Turing machine
21
Q
Describe the importance of Turing machines
A
- Turing machines provide a formal model of computation and provide a definition of what is computable
- They can be used to prove that there are problems which cannot be solved by computers
22
Q
What makes up a Turing machine?
A
- Finite set of states
- Set of transition rules
- Finite set of symbols
- Infinite tape with marked off squares
- Sensing read-write head that can travel along the tape, one square at a time
23
Q
What is a halting state in a Turing machine?
A
A state with no outgoing transitions
24
Q
What is meant by a Universal Turing machine?
A
- A Turing machine that can simulate the behaviour of any other Turing machine, by acting as an interpreter
- It faithfully executes operations on the data precisely as the simulated TM does
- Both the transition rules for the TM as well as the input data would be stored on the tape
25
What is another way to represent the state transition diagram of a Turing machine?
* Transition function
* δ (current state, input symbol) = (next state, output symbol, movement)
26
One example of where composition is used
In abstract data types, where a complex abstract data type is formed from smaller and simpler data types
27
Give three differences between symmetric and asymmetric encryption
**S**: Uses same key for both encryption and decryption
**A**: Doesn't
**S**: Have to distribute the key without interception
**A**: Don't
**S**: Faster
**A**: Slower, but provides both confidentiality and authentication
28
Asymmetric encryption: `A` sends to `B`
1. `A` encrypts the message with `B`'s public key
2. `B` decrypts with their own private key (the only key that can do this)
29
Asymmetric encryption: `A` sends to `B`, and `B` can verify that `A` is the sender
1. `A` encrypts the message with `B`’s public key *and* `A`’s private key
2. `B` will decrypt with `B`’s private and `A`’s public key
30
What is the purpose of digital signatures?
To confirm the identity of the sender, **and** to detect if a message or document has been tampered with
31
Describe how `A` can use a digital signature when sending a document to `B`
1. `A` **hashes** the document, creating a **message digest**
2. `A` encrypts this message digest with their private key. This encrypted hash is known as the **digital signature**
3. The digital signature is **appended** to the message
4. (This may now be encrypted with `B`’s public key, sent to `B`, and decrypted by `B` using their own private key as normal)
5. `B` **decrypts** the digital signature with `A`’s public key, to reveal the message digest. `B` also hashes **recalculates the hash** for the document. If the result of these procedures is the same, then the message has not been tampered with *and* the identity of the sender is authenticated.
32
Anyone could create a digital signature and claim they are a trusted individual. How do we solve this?
Digital certificates are used to verify the sender's identity
33
What is a digital certificate?
* An electronic document that authenticates a message sender or a website
* It contains the sender's public key as well as some information about them
34
How can a digital certificate be created for *A*? What do they contain?
A trusted individual (certificate authority) **signs** a copy of *A*’s public key as well as some information about *A*.
Digital certificates will contain:
- Serial number
- Name (e.g. domain name for website digital certificates)
- Expiration date
- Copy of the certificate holder’s public key
35
How are digital certificates used by modern web browsers?
- Modern web browsers check the digital certificate of each secure website as a standard security measure.
- If the certificate is suspicious or out of date, the site is blocked.
36
Why are key-exchange algorithms needed?
In order to distribute the key securely in symmetric encryption systems.
* Asymmetric encryption algorithms are nearly always much more **computationally expensive** than symmetric ones
* So in many cases it is common to exchange a **shared key** using a key-exchange algorithm, and then to transmit the data using that key and a **symmetric key algorithm**.
(e.g. SSH and SSL/TLS)
37
What is CRUD?
CRUD stands for...
The four fundamental operations for any database or content management system:
- **C**reate
- **R**etrieve
- **U**pdate
- **D**elete
38
What does REST stand for?
Representational State Transfer
39
What is the relationship between REST, CRUD and SQL?
REST enables CRUD to be mapped to SQL database functions
40
**Create** keywords: CRUD → HTTP request → SQL
Create → POST → INSERT
41
**Retrieve** keywords: CRUD → HTTP request → SQL
Retrieve → GET → SELECT
42
**Update** keywords: CRUD → HTTP request → SQL
Update → PUT → UPDATE
43
**Delete** keywords: CRUD → HTTP request → SQL
Delete → DELETE → DELETE
44
Explain how a REST API allows a client browser to access a database
The REST API allows JavaScript to talk to a database through HTTP.
1. The client browser creates a HTTP request, calling the REST API
2. The REST API is created and run on the server
3. The server responds to the client’s requests using either JSON or XML
4. The client’s browser processes the JSON or XML and displays the response to the user
45
What is the advantage of using REST?
* The client computer needs no knowledge at all of how the database server works
* So clients and servers can be developed independently
46
What are JSON and XML both examples of?
Standards for transferring data between a server and an application
47
What does JSON stand for?
Java script object notation
48
Give four advantages of JSON over XML
1. Easier for a human to read
2. More compact (so quicker to transmit)
3. Easier to create (as syntax is simpler)
4. Easier for computers to parse and therefore quicker to parse
49
What is thin-client computing?
* When the processing / storage is carried out on the server
* The **server** needs lots of RAM, many secondary storage devices, and more processors
* The client needs a high bandwidth internet connection
50
What is thick-client computing?
* When the processing / storage is carried out on the client
* The client needs greater RAM, secondary storage and processing capacity than more thin clients
* Less reliance on an internet connection to do stuff
51
Give three examples where thick-client computing is preferred
- gaming
- (professional) video editing
- simulation/research
52
Give three advantages of thick-client computing
1. Internet connection not needed to do useful stuff
2. More flexible in what can be done (not limited by what cloud-based services exist)
3. Users can more easily keep data private
53
Give three advantages of thin-client computing
1. Cheaper to purchase, due to the lower hardware specification
2. Simpler updating of software, as this is done by the server
3. Server is also responsible for backups
54
Give three disadvantages of thin-client computing
1. Higher bandwidth internet connection is needed to be useful
2. Limited to what cloud-based services exist and how they work
3. Potential privacy concerns as entrusting a third-party to look after your files
55
Give four reasons why setting up and maintaining client-server networks is more expensive (than P2P)
- The servers need to be more **powerful** machines
- The servers need more **secondary storage** space
- They need to be **always on**
- As more hosts connect to a P2P network, the resource supply increases. Whereas when more hosts connect to a single server, the **more powerful and expensive** the machines need to be
56
Give six differences between client-server and peer-to-peer networks
**CS** : The server has authority over the service
**P2P** : All computers have **equal status** - clients share resources *and* computing power
**CS** : Clients access resources from the server
**P2P** : Resources are stored on the computers, and any computer can access resources directly from any other - there is no dependence on a central server
**CS** : Server **failure** disrupts all computers on the network
**P2P** No single point of failure
**CS** : Configuration is more complex, and setting up and maintaining the network is more **expensive**
**P2P** : Cheaper to set up and maintain
**CS** : Supports centralised **backups**
**P2P** : Backups need to be made locally
**CS** : Improved **security** management, as security management can be centralised
**P2P** : Management of security must be managed individually on each computer
57
Give three examples of where a client-server network might be used
* Personal web server for hosting a simple website with a limited number of users
* Cloud-based gaming platforms
* College
58
Give three examples of where peer-to-peer networks are/could be used
* Home network with a small number of trusted devices
* Decentralised cryptocurrencies (e.g. Bitcoin)
* BitTorrent protocol
59
What is the purpose of wireless networks / WiFi?
To allow devices to communicate within a network without being physically connected to it
60
What is WiFi?
A type of wireless local area network (WLAN) that is based on international standards
61
Give two components needed for wireless networking
* Wireless network interface card
* Wireless Access Point
62
Give three ways to secure a wireless network
* Encryption of data using WPA or WPA2
* Disabling the SSID broadcast
* MAC address allow lists
63
What does WPA stand for?
Wifi Protected access
64
What is the main difference between WPA and WPA2?
WPA2 is more secure
65
What is an SSID?
* A **Service Set Identifier** (SSID) is a locally unique **identifier** for a wireless network
* They use alphanumeric characters that are specified during the setup of the wireless network
* This SSID is used by all devices which want to connect to that network
66
How can disabling the SSID broadcast improve security on a wireless network?
The SSID broadcast can be disabled in order to make it hidden, only allowing those who know the SSID to try to connect
67
How can a MAC address allow list be used to improve security on a wireless network?
- MAC address allow lists can be created to only allow specific devices to connect to a network
- Each MAC address is **unique to each NIC**
- The **WAP checks** the MAC addresses of devices trying to connect against a list of allowed devices
- Only devices with an **allowed** MAC address are able to connect
68
What does CSMA/CA stand for?
Carrier Sense Multiple Access with Collision Avoidance
69
What do RTS / CTS stand for?
Request to Send / Clear to send
70
How does CSMA/CA work (without RTS/CTS)?
1. When a device is ready to transmit, it **listens** to its communication channel to check if it is idle
2. If there is a **data signal present**, it means another transmission is in progress, so the device **waits** for a random period of time
3. When no data signal is present, the device **sends its data**
4. Once the destination device (e.g. WAP) receives the data, it will respond back with an **acknowledgment**
5. If this acknowledgement is not received, the sending device waits for a **random time period** and the process begins **again**
71
What extra steps are required in CSMA/CA in order for RTS/CTS to be used?
1. Before a device sends a message, a **Request to Send** is sent
2. The WAP responds with a **Clear to Send signal** to **only one** device at a time, and only that device transmits its data
3. If a CTS is not received the device must wait a random amount of time and try again
72
Describe the Hidden Node problem in the context of computers **A** and **B** both trying to transmit data to a WAP
If **A** is transmitting data to the WAP, and **B** is outside the transmission range of **A**, then **B** might start transmitting its own data, causing a collision
73
What is the key exchange problem?
How do we pass the key from sender to receiver without it being intercepted?
74
What is Big Data?
A catch-all term for data that won’t fit the usual containers, cannot be stored/processed on a single server, and that must be processed at very high speeds.
75
What are the three Vs of big data?
- (very large) **Volume** (of data)
- **Velocity** (at which data is generated)
- **Variety** (of data types in the data)
76
What does Volume mean?
Why is it a problem?
How is it solved?
***what it means***
- Data is too big to be stored/processed on a single server
***why it’s a problem***
- relational databases don’t scale well across multiple machines
- and the processing associated with the data must be split across multiple machines
***how it’s solved***
- Functional programming is a solution
77
What does Velocity mean?
The data is generated and/or processed at very high speed - need to respond in seconds or milliseconds
78
What does Variety mean?
- The data is in many forms such as structured, unstructured, text, multimedia.
- The most difficult aspect of Big Data involves its lack of structure.
79
What is the most difficult aspect of Big Data? Why?
Its **lack of structure** (under Variety). This poses challenges because:
- **Analysing** the data is made significantly more difficult
- **Relational databases are not appropriate** because they require data to fit into a row-and-column format
80
What technique is used to discern patterns in data and to extract useful information?
Machine learning
81
What is the advantage of functional programming for big data?
Its features make it easier to write
- Correct code
- Code that can be distributed to run across more than one server
82
Give four features of functional programming that make it suitable for Big Data
1. Immutable data structures
2. Statelessness
3. Higher-order functions
4. Programs do not specify order of execution (meaning they work well on parallel processing systems)
83
What about immutable data structures makes them suitable for Big Data?
- Immutable data structures cannot be changed during program execution
- Same input always gives same output
- Makes parallel processing extremely easy
84
What about statelessness makes it suitable for Big Data?
- Statelessness means there are **no side-effects** of computations
- so code is easy to write correctly, and it is easy to understand and predict how the program will behave
85
What about higher order functions makes them suitable for Big Data?
- Higher-order functions take a function as an argument, return a function as a result, or both.
- Higher-order functions can be easily parallelised
86
How is machine learning used in Big Data?
Machine learning is used to discern patterns in data and to extract useful information
87
What is meant by "parallel processing" in Big Data?
When more than one processor can work on different parts of a large data set at the same time without changing any other part
88
What is a graph schema?
* Graph schemas can be used to capture the structure of a dataset. They can be easily extended, without impacting existing facts (because the facts are immutable)
* Nodes are used to represents the core entities in the data set
* Edges are used to represent the relationships between the nodes
* Properties are used to capture information about the nodes
89
What is a fact in a fact-based model?
- Each fact within a fact based model captures a single piece of information.
- Each fact is immutable and timestamped
90
State the name of the problem that RTS/CTS overcomes
The Hidden Node problem
