Set 10 Flashcards
What is representational abstraction?
A representation arrived at by removing unnecessary details
What is abstraction by generalisation or categorisation?
A grouping by common characteristics to arrive at a hierarchical relationship of the ‘is a kind of’ type.
What is information hiding?
The process of hiding all details of an object that do not contribute to its essential characteristics
What is procedural abstraction?
- 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
How is functional abstraction different from procedural abstraction?
- 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
What is data abstraction? Give an example
- 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
What is problem abstraction/reduction?
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
What is (procedural) decomposition?
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
What is (procedural) composition?
The process of combining procedures to form compound procedures
What is automation? How is it achieved?
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.
When is a problem “computable”?
If there is an algorithm (in principle) that solves the problem
When is a problem “non-computable”?
If no algorithm can ever exist which solves the problem
What is a intractable problem?
A computable problem for which a polynomial time (or better) algorithm does not exist
How do programmers find “solutions” to intractable problems?
By developing tractable heuristic algorithms and methods, which find approximate (but not necessarily optimal) solutions.
What is the trade-off that must be considered when developing heuristic algorithms?
speed vs correctness
What is an undecidable problem? Give an example
- A decision problem that is non-computable
- e.g. the halting problem
What is the halting problem?
The undecidable problem of determining whether any program will eventually halt on given particular input without running the program
What is the significance of the halting problem?
The halting problem demonstrates that some problems are non-computable, meaning they cannot be solved by a computer
Why can a Universal Turing Machine be considered to be more powerful than any computer that you can purchase?
Because it has an infinite amount of memory
Name one example of a model of computation
Turing machine
Describe the importance of Turing machines
- 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
What makes up a Turing machine?
- 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
What is a halting state in a Turing machine?
A state with no outgoing transitions
What is meant by a Universal Turing machine?
- 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
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)
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
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
Asymmetric encryption: A sends to B
-
Aencrypts the message withB’s public key -
Bdecrypts with their own private key (the only key that can do this)
Asymmetric encryption: A sends to B, and B can verify that A is the sender
-
Aencrypts the message withB’s public key andA’s private key -
Bwill decrypt withB’s private andA’s public key
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
Describe how A can use a digital signature when sending a document to B
-
Ahashes the document, creating a message digest -
Aencrypts this message digest with their private key. This encrypted hash is known as the digital signature - The digital signature is appended to the message
- (This may now be encrypted with
B’s public key, sent toB, and decrypted byBusing their own private key as normal) -
Bdecrypts the digital signature withA’s public key, to reveal the message digest.Balso 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.
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
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
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
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.
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)
What is CRUD?
CRUD stands for…
The four fundamental operations for any database or content management system:
- Create
- Retrieve
- Update
- Delete
What does REST stand for?
Representational State Transfer
What is the relationship between REST, CRUD and SQL?
REST enables CRUD to be mapped to SQL database functions
Create keywords: CRUD → HTTP request → SQL
Create → POST → INSERT
Retrieve keywords: CRUD → HTTP request → SQL
Retrieve → GET → SELECT
Update keywords: CRUD → HTTP request → SQL
Update → PUT → UPDATE
Delete keywords: CRUD → HTTP request → SQL
Delete → DELETE → DELETE
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.
- The client browser creates a HTTP request, calling the REST API
- The REST API is created and run on the server
- The server responds to the client’s requests using either JSON or XML
- The client’s browser processes the JSON or XML and displays the response to the user
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
What are JSON and XML both examples of?
Standards for transferring data between a server and an application
What does JSON stand for?
Java script object notation
Give four advantages of JSON over XML
- Easier for a human to read
- More compact (so quicker to transmit)
- Easier to create (as syntax is simpler)
- Easier for computers to parse and therefore quicker to parse
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
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
Give three examples where thick-client computing is preferred
- gaming
- (professional) video editing
- simulation/research
Give three advantages of thick-client computing
- Internet connection not needed to do useful stuff
- More flexible in what can be done (not limited by what cloud-based services exist)
- Users can more easily keep data private
Give three advantages of thin-client computing
- Cheaper to purchase, due to the lower hardware specification
- Simpler updating of software, as this is done by the server
- Server is also responsible for backups
Give three disadvantages of thin-client computing
- Higher bandwidth internet connection is needed to be useful
- Limited to what cloud-based services exist and how they work
- Potential privacy concerns as entrusting a third-party to look after your files
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
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
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
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
What is the purpose of wireless networks / WiFi?
To allow devices to communicate within a network without being physically connected to it
What is WiFi?
A type of wireless local area network (WLAN) that is based on international standards
Give two components needed for wireless networking
- Wireless network interface card
- Wireless Access Point
Give three ways to secure a wireless network
- Encryption of data using WPA or WPA2
- Disabling the SSID broadcast
- MAC address allow lists
What does WPA stand for?
Wifi Protected access
What is the main difference between WPA and WPA2?
WPA2 is more secure
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
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
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
What does CSMA/CA stand for?
Carrier Sense Multiple Access with Collision Avoidance
What do RTS / CTS stand for?
Request to Send / Clear to send
How does CSMA/CA work (without RTS/CTS)?
- When a device is ready to transmit, it listens to its communication channel to check if it is idle
- If there is a data signal present, it means another transmission is in progress, so the device waits for a random period of time
- When no data signal is present, the device sends its data
- Once the destination device (e.g. WAP) receives the data, it will respond back with an acknowledgment
- If this acknowledgement is not received, the sending device waits for a random time period and the process begins again
What extra steps are required in CSMA/CA in order for RTS/CTS to be used?
- Before a device sends a message, a Request to Send is sent
- The WAP responds with a Clear to Send signal to only one device at a time, and only that device transmits its data
- If a CTS is not received the device must wait a random amount of time and try again
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
What is the key exchange problem?
How do we pass the key from sender to receiver without it being intercepted?
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.
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)
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
What does Velocity mean?
The data is generated and/or processed at very high speed - need to respond in seconds or milliseconds
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.
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
What technique is used to discern patterns in data and to extract useful information?
Machine learning
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
Give four features of functional programming that make it suitable for Big Data
- Immutable data structures
- Statelessness
- Higher-order functions
- Programs do not specify order of execution (meaning they work well on parallel processing systems)
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
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
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
How is machine learning used in Big Data?
Machine learning is used to discern patterns in data and to extract useful information
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
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
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
State the name of the problem that RTS/CTS overcomes
The Hidden Node problem
