Computer Science

1. What is a Natural Number and its Symbol? 2. What is a Real Number and its Symbol? 3. What is an Integer and its Symbol? 4. What is a Rational Number and its Symbol? Positive Integer (N) Any number (R) Any whole number (Z) Can be represented in a Fraction (Q) 5. What is a Ordinal Number? Position in a list 6. What is a Cardinal Number? Size of list 7. What is Absolute Error? Difference between actual answer and esti- mate 8. What is Relative Error? absolute error/true value 9. How does parity bit work? (Odd/Even) Bit (1/0) is added at end of code. Even parity - If there is an even number of 1's, 0 is added Odd parity - If there is an even number of 1's, 1 is added 10. What is Majority Voting? 3 bits are sent that are the same as the origi- nal bit, the majority amount received is taken as the original bit. 101 = 1. Good as corrects errors as well as spotting them. 11. What is Check digit? All numbers are added up, then the digits of the answer are added up, this is repeated until you are left with 1 digit. 3+4+2+8 = 17 1+7 = 8 12. What is Bit/ Colour depth? Amount of bits used to represent all the colours of an image. 17 colours requires 5 bits. 13. What is Metadata? Data about an image/ other data. -Time, Bit depth, Size 14. What is Analogue data? It is infinite and represented in wave form 15. What is Digital data? Represented in binary, finite and can be processed by a computer 16. Why are ADC's used? A computer needs to process analogue signal so data needs to be converted from Analogue to Digital. 17. What is Nyquist's theorem? Sound should be sampled at double the high- est frequency. 18. What is Sampling? The process of converting Analogue signals to Digital. -Specific readings of amplitude (Samples) are taken at regular intervals and converted and stored in binary. 19. What happens when sample rate increases? - Increase in file size - Increase in quality 20. What is Encryption? Converting Plaintext to Ciphertext to make it useless for anyone who intercepts it. 21. What is a Caeser Cipher? Moving the alphabet up and down or replacing letters with other letters. 22. What is a Vernam Cipher? Using a randomly generated key for both en- cryption and decryption. XOR gate is used. 23. What does a Vernam key have to be? - Randomly generated - Same length as plaintext 24. What does 'Computational- ly secure' mean? - Only used once - Kept securely When data cant be cracked in a reasonable amount of time. Vernam is and Caeser isn't. 25. What is RLE? RLE reduces the size of a file by removing repeated information. It is displayed as, the character of the re- peated information followed by the number of times it is repeated. 26. What is Asymmetric and symmetric encryption? 27. What is Dictionary-Based Compression? 28. What is lossless compres- sion? 29. What is Application soft- ware? Asymmetric - Data is Encrypted using re- ceivers Public Key and Decrypted using Re- ceivers Private Key Symmetric - The same keys are used for En- cryption and Decryption. Used with data with repeating values. - A library is created with repeating values that are used instead of the original characters to reduce file size Data is compressed and can be reconstructed if required as no data is lost. Designed to perform a task. 30. What is Utility software? - Keep computer safe (Encryption, Antivirus) - Maintenance (Data backup) 31. What is Library software? Collections of prewritten code that is used to optimize tasks. 32. What is an Assembler? Converts Assembly language to Machine Code 33. What is a Compiler? Converts High level code to machine code. 34. What is an Interpreter? Converts High level code to machine code (Line by line) 35. Advantages of Compiler - Only needs to execute once - Not needed for program to run - Quicker to run 36. Advantages of Interpreter - Translates code up until mistake - Code is more portable 37. What is a Bitmap Image? Collection of pixels. (Photos, complex images) 38. What is a Vector Graphic? Made out of Objects/ Shapes and properties of the objects. (Logos, simple images) 39. Advantages of Vectors - Take up less storage - Objects can be resized without loss of quality - Objects can be removed individually 40. Advantages of Bitmaps - Can represent more complex images - Wide range of colours 41. Advantages of High Level Code 42. Advantages of Low Level Code - Easy to spot mistakes - Easy to understand - Quicker to execute as don't need to be trans- lated - Take up less memory 43. What is a Half Adder? Adds up two values 44. What is a Full Adder? Adds 3 or more Binary values 45. What is the role of the Oper- ating System (OS)? - Links together Hardware, Software and the user - Controls start-up and shut-down - Recognises inputs - Controls how RAM is used - Decides where to store programs 46. What is Scheduling? Assigning access to certain resources to car- ry out a task. 47. What is Virtual Memory? Used when RAM is unavailable. 48. Why are I/O controllers used? 49. What does the CPU con- tain? 50. What is the Memory Read Control Signal? 51. What is the Memory Write Control Signal? Devices can not directly connected to the processor, converts signals so computer can understand. When a new device is connected, a device driver is installed which is used to interact with devices. - Busses - I/O controllers - Memory - Processor Data is placed on a Data Bus Data on Data Bus is written into addressed location 52. What is a Bus? Series of wires 53. What is a Data Bus? Carries data that is used Goes both ways 54. What is an Address Bus? Carries Address of memory location in 1 di- rection from processor to memory. 55. What is a Control Bus? Carries control signals from the processor to other components. 56. What is a Register? Memory location in the Processor 57. What does Main Memory do? Store data and instructions that need to be processed 58. Advantages of Von Neu- mann architecture 59. Advantages of Harvard ar- chitecture 60. What is Cache and why is it used? 61. What improves perfor- mance of a Processor? 62. What is Immediate address- ing? - Cheaper - Easier to set up - Data and Instructions can be accessed at the same time - Memory's can have different word length - Memory that can be Accessed quickly - Stores Frequently used Instructions - Lots of Instructions/ Data can be Stored in Cache - Near CPU - Amount of cores (More processes at once) - Clock speed (more cycles can be complet- ed) - Amount of Cache (reduces time fetching from main memory) - Word length (More data can be sent at once) - Address Bus width (More locations can be accessed) - Data Bus width (More data can be sent over a bus at a time) The data to be used is in the instruction / The Operand is the Datum 63. What is Direct addressing? The Instruction includes the location of the data to be used. 64. How do Barcodes work? Barcode reader reflects light of of Barcode and a different value is returned depending on light intensity (Black or White) 65. What is the Stored Program Concept? 66. How do you calculate the maximum number of de- Instructions are stored in main memory Instructions are fetched and executed by the Processor 2 ^ Number of bits allocated to Host ID (the 0's) minus 2. vices allowed on a Net- work? 67. Why is DHCP used? To allocate IP addresses on a network, used when there are a limited amount of IP ad- dresses. The Server offers an IP address to the device which can be accepted. The server confirms this. 68. How does CSMA work? Device waits until channel is idle Device sends RTS Router responds to RTS with CTS Device starts to transmit data when CTS is received Router sends Acknowledgement that data is received Ack is resent if not received Ack tells other devices that the channel is open 69. What can be used to protect a Wireless Network? 70. How does a Laser Printer work? 71. How does a Digital Camera work? - Disable SSID so network is hidden - Use MAC address whitelist so only known addresses can connect Printer generates Bitmap Image of page Drum is negatively charged Laser reflected by mirror is shone on Drum to Reverse charge Toner is given negative charge Toner sticks to Drum at Positive areas Paper passed over Drum and Toner sticks to it Heated rollers fuse the toner onto the paper Lens focuses light onto sensor Colour filter generates data for RGB values RGB values are converted into Binary and stored Image is recorded as a group of pixels 72. How does RFID work? Signal sent by RFID scanner Signal activates RFID tag Tag transmits data by radio wave 73. Advantages of Hard Disk - Lots of storage - Long lifespan - Good for PC's and servers 74. Advantages of SSD's - Fast access time as no moving parts - Low power consumption - Not easily damaged - Good for Laptops and Phones 75. Advantages of Optical Disk - None really - Good for sharing small volumes of data 76. How does a Hard Disk oper- ate? Data is split into tracks Read/ Write arm changes magnetic polarity of each magnet Disk continuously spins Data read when passed under arm 77. How does a SSD operate? Consists of NAND flash cells Data is stored by trapping electrical charge Whole page/ block must be deleted to edit data 78. How does a Optical Disk op- erate? Laser burns pits for 1's or 0's Laser is used to reflect light back If there is a pit, light is scattered If not, light it reflected back Data is stored on a 1 spinning track 79. What does the ALU do? Performs arithmetic and logic operations 80. What is the Fetch part of the FEC? The content of the PC is copied to the MAR The content of the MAR is transferred to main memory by the address bus The instruction is sent from main memory to 81. What is the Decode part of the FEC? 82. What is the Execute part of the FEC? the MBR by the data bus The PC is incremented by one The content of the MBR is copied to the CIR The content of the CIR is decoded by the control unit The decoded instruction is split into two parts: opcode and operand Any data required is fetched The instruction is carried out The result is stored in main memory 83. What is the Opcode? Type of operation 84. What is the Operand? Data that instruction is performed on 85. What is an Interrupt? Signals sent by hardware/ software to indi- cate that to the processor that a task/ process needs attention They stop the current process E.g. An input on a keyboard 86. How does Parallel data transmission work? 87. Advantages of Parallel transmission 88. Advantages of Serial trans- mission Several bits are sent at once on different ca- bles - More data can be sent at once - Cheaper as less cables - Better at longer distances - Data isnt Skewed (Arrives at different times) as there is only one cable - There is no Crosstalk (Cables touch and data jumps across) 89. What is Bit rate? Number of Bits sent per second 90. What is Bandwidth The max number of Bits that can be sent across a network over a given period of time 91. What is the formula for Bit rate? Baud rate x Bits per Baud 92. What is Baud rate? The rate at which signal changes 93. What is a Network? Two or more connected devices 94. How does a Star Network operate? Each device is connected to the central hub The central hub receives and delivers packets for the devices 95. Advantages of Star Network - If one cable fails, the Network can still func- tion - Easy to add/ remove Devices - Packets are sent directly to each device meaning other devices can't see them - No data collisions as each device has its own cable 96. Disadvantages of Star Net- work 97. How does a Bus Network operate? - Expensive as lots of cables - If the central hub fails, the network can't function A bus connects each device to main cable called a Backbone Terminators are placed at either end of net- work to stop signals reflecting back into the network 98. Advantages of Bus Network - Cheaper as less cables - No central hub so cheaper and less chance of network failure 99. Disadvantages of Bus Net- work - Packets all sent through Backbone so de- vices can see packets that aren't intended for them - Backbone is used by multiple devices so high chance of data collision - If Backbone fails so does Network 100. What is the difference be- tween Physical and Logical Network Topology Physical is how Hardware is connected (ca- bles) Logical is how Data packets flow around Net- work 101. What is a Protocol? Set of rules 102. What is Latency? Time between sending and the receiving of a message 103. What is Synchronous Trans- mission? 104. What is Asynchronous Transmission? 105. What is Hexadecimal used for? 106. What is Client-Server net- working? 107. What type of Networks is Client-Server good for and why? 108. Disadvantages of Client-Server Clock is used to synchronise Transmission Data is transmitted with Start and Stop bits. Colour Coding One or more servers provide services for clients on a Network Servers are more powerful than the clients The clients on the network request services from the servers, which then respond to the client with the requested service - Schools, Banks, Databases - Good as secure as Data is backed up in the Central server - Data is kept securely in the Central server (Anti-viruses, Encryption, Firewalls) - Good for Databases as it can be accessed at the same time on two devices as they have separate copies - Files more likely to be available as server rarely turned off - Expensive (Severs) - Hard to manage and set up 109. What is Peer-to-Peer net- working? 110. What type of Networks is Peer-to-Peer good for and why? 111. How do you subtract Binary numbers? 112. Why might files not run on certain Processors? 113. Advantages of Peer-to-Peer network? Services are shared between Clients All Clients have equal status All Clients need to be running for the network to work Large file-sharing services as cheap and easy to set up without the need for a server. Make the smaller one negative and add the larger one and the negative result. The Processors have different Instruction sets. Code is platform dependant. - Cheaper to set up and maintain (no central server) - Easier to set up 114. What is WiFi used for? A way of connecting to a wireless network 115. How are Wireless networks secured? Wireless networks are secured by encrypting transmitted data using WPA. It requires a new device to enter a password before joining. 116. What is the Internet? A worldwide network of interconnected net- works. 117. How are Packets sent through the Internet? 118. What does a Packet con- tain? When a packet is sent through a network, it passes through a number of routers before reaching its destination. A router uses the address on a packet to determine where to send the packet. Each time it passes through a router it is called a 'hop'. - Sender address - Destination address - Sequence number - Contains the number of packets in a message and identifies a packet's position in relation to others. Allows packets to be reassembled. - Packet's Data - Time to live - Max number of 'hops' 119. What does a Router do? - Forwards data packets to their network des- tination - Examine Data Packets - Manage congestion 120. What is a Domain name? A domain name identifies an organisation or individual on the Internet. e.g. Google 121. What is the function of a Firewall? It prevents Data Packets from entering a Net- work 122. What is Packet Filtering? Allowing/ Rejecting packets based on ports, protocols, destination or source (where it came from) 123. What is Stateful Inspection? It examines the contents of a packet before deciding whether to allow it through the fire- wall. 124. What is a Proxy server? An outward-facing computer that hides inside activity 125. What is a Digital Signiture? Can be used to verify the sender of a mes- sage To verify that a message has not been tam- pered with during transmission. 126. Describe the process of Hashing (encryption) A Hash of the message is created The value of the Hash will not be the same if the message is changed Hash is Encrypted with Senders Private Key and sent with message The message is rehashed when received If both Hashes match then the sender can be authenticated 127. What is a Digital Certificate? It is a file that verifies the identity of a device or user It contains Owner's name, an Expiry date, the Owner's Public Key and the Digital Signature 128. What is Packet Switching? Message is split into multiple packets, and sent to its recipient via the best possible route before being reassembled with other packets. 129. What is Malware? Software with malicious intent 130. What is a Trojan horse? Programs that claim to perform one function but actually do another 131. What is a Worm? Malware that can replicate itself across within a Network. 132. What is a Virus? Malware that can replicate itself across within a Network that requires a host cell. 133. How to prevent Malware? - Don't open links - Install Antivirus - Do regular updates 134. What does the Application layer do? 135. What does the Link layer do? 136. What does the Transport layer do? Selects Protocol Interacts with user via Email/ Browser - Controls Physical connections between pieces of Hardware - Adds MAC addresses to packets - Creates end to end connection between Sender and Receiver. - Divides Data into Packets and reassembles Data after. - Error correction and detection - Allocates Port Numbers. 137. When is NAT used? When a device on a private network needs to communicate with a device on the Internet. 138. What does the Network lay- er do? - Adds Source and Destination IP addresses - Involved with Router 139. What is Secure Shell (SSH)? Used for remote management of computers, allowing computers to be accessed and con- trolled remotely. In order to access a remote computer, SSH requires a username / password combination 140. What is File Transfer Proto- col (FTP)? Allows the transfer of files between two com- puters on the Internet Upload/ Download/ Delete files on a server 141. What is the HTTP protocol? Allows a Device to load a Web Server 142. What is HTTPS? Same as HTTP, but encrypts information dur- ing transmission. Keeps information sent by clients secure and prevents information from being tampered with during transmission. 143. What is POP3? Allows a user to retrieve and download emails from a server 144. What is SMTP? Used to send emails 145. What is the purpose of a Subnet Mask? 146. What is an example of a ADC? A Subnet Mask is used to divide an IP address into two parts, Network ID and Host ID Can be used to tell if two devices are part of the same Subnet (part of a network) MIDI - Stores sound from instruments using event messages like Volume, Duration and Instrument 147. Advantages of MIDI? - No background noise - Music can be altered without loss of quality - Lossless compression is used - Takes up low storage 148. Give an example of what a DAC is used for? Headphones, Speakers 149. What is NAT? Device sends packets through the router Router makes a record of the packet before replacing the private IP address of the com- puter with its own routable IP address. The response is sent to the router's public IP address, which then forwards the response to the correct private IP address by using the record it made when sending the packet. 150. What is Port Forwarding used for? 151. How does Port Forwarding work? When a device needs to connect with a Server that is on a Private Network Packets are sent to the Router of the Serve that the client wishes to access The packets contain the Port Number of the Application that the Device requires The Private Network's router then forwards the packets to the server using NAT 152. What does CRUD stand for? Create (INSERT), Read (SELECT), Update, Delete 153. What is CRUD used for? Used to edit Databases 154. What is REST used for? Used to edit Online Database applications 155. Advantages of JSON over XML 156. Advantages of XML over JSON 157. What is Thin-Client comput- ing? - More compact - Easier to read - Easier to create - Faster for computers to process It is more flexible Most of Processing and Storage done by Server 158. What is API?: Rules relating to how different apps commu- nicate with each other/ use each other 159. What is Thick-Client com- puting? 160. Advantages of Thick-Client computing? 161. Advantages of Thin-Client computing? 162. Disadvantages of Thin-Client computing? 163. Disadvantages of Thick-Client computing? Processing and storage is done by clients so there is no need for a Server - Reliable as doesn't rely on Central Server - Doesn't require constant connection to a Server - No cost to maintain - Less Data collisions - Updates can be done on Server for all clients - Easy and cheap to add new Clients - Control over Security of network - Server is expensive to buy and maintain - More Data collisions as lots of traffic to Serv- er - Expensive to add new Clients - Harder to maintain as no central control over Updates or Security 164. What is a Linked List? A list connected by Pointers. Each Node contains Data and a Pointer that points towards the next item in the List 165. What is the Difference be- tween Static and Dynamic Data Structure? 166. What is an Example of Dy- namic Data Structure? Static Data Structures can't be resized during Run Time, whereas Dynamic can. (Static can but not without creating a new Array) A List 167. What is an Example of Static An Array Data Structure? 168. 168. What are Advantages of us- ing Arrays over Lists? 169. What are Advantages of us- ing Lists over Arrays? 170. What are Disadvantages of Arrays? - Allow Random Access (Able to go to any Element First) - Use less Memory as no Pointer - Able to change size During run time - Store at any place in Memory - Easy to Insert New Items as just change the Pointers - Fixed Space in Memory needs to be Allocat- ed as terms have to be in a row - Hard to add New Items as Shuffling may be Required 171. What is the HEAD of a list? First element 172. What is the tail of a List? Everything after the first element 173. What are Disadvantages of Lists? 174. How do you add an Element to a List? 175. How do you remove an Ele- ment from a List? 176. How do you add/ remove an Element from an Array? 177. What is the HEAP in Dynam- ic Data Structure? 178. What does the Start and Stop Bit do? - Uses More Memory as Pointers are used - Can only be traversed in one Direction un- less Recursion is used - Slow to access certain Elements A location is taken from the top of the HEAP and Data is written into that Location and the next (Pointer) The Pointers are Adjusted The Location is returned to the HEAP and the pointers are adjusted Create/ Remove a Memory Location and Shuffle other Elements to add/ remove a space Stores Unused memory Addresses Start - Wakes Receiver Stop - Allows Receiver to Process Received Bits 179. What is a Recursive Subrou- A Procedure that calls itself tine? 180. What is a BASE CASE in Re- cursion? 181. What are the components of a Stack Frame? 182. Why are Stacks used in Re- cursive Subroutines? 183. Why would you make a function Public? 184. Why would you make a function Private? 185. What is an Event Driven Program? 186. What are the Circles / Nodes and arrows called in an Ad- jacency Matrix? 187. What is an Adjacency Ma- trix? A condition that must be met in order for the recursion to end. - Parameters - Local Variables - Return Address To be able to store the Return Addresses as procedures must be returned to in reverse order If you need to access it from outside the Class It can't be accessed from Outside the Class A program that responds to events that take place, such as the user clicking a button Nodes = Vertices Arrows = Edges A table that represents the connections be- tween Vertices in a Graph 188. What are the Disadvantages - It repeats data of using an Adjacency Ma- trix? 189. When would you use an Ad- jacency Matrix? - Records areas that aren't connected When there are lots of Edges between Ver- tices 190. What is an Adjacency List? A way to represent a Graph by showing the connections of each individual Vertex (Node) 191. When would you use an Ad- jacency List? 192. What are the three Charac- teristics of a Tree? 193. How to draw a Weighted Ad- jacency Matrix? 194. How do you represent a Tree using 3 Arrays? 195. How do you represent a Tree using One Array of Records 196. What is the Root Node in a Tree? 197. What is a Leaf Node in a Tree? 198. How can a Stack be used for a Repeat action? When there are few edges - All connected - No direction of Edges/ Branches - No loops/ Cycles Write the Weight/ Value instead of a 1 - 1 array for Data - 1 array for right pointer - 1 array for left pointer - Record created to store Data and Pointers - One left Pointer - One right Pointer The top Node A node with no Children/ Pointers 1. Stack is used to store the Users Actions 2. Each time an Action is done, it is pushed to the top of the Stack unless it is a Repeat action 3. When Repeat action is used, the top item on the Stack indicates the action to complete 199. How can a Stack be used for an Undo action? 200. What happens when a Stack gets overfilled? 201. What happens when an ac- tion is done to an Empty Stack 202. What is the Order of Tra- versal using a Depth First Search? 203. What is the Order of Tra- versal using a Breadth First Search? 204. How can a Node Become Completely Explored? 205. What type of Diagram is Breadth and Depth Search Used on? 206. What type of Diagram are the Post, Pre and In Order Algorithms used on? 1. Stack is used to store the Users Actions 2. Each time an Action is done, it is pushed to the top of the Stack unless it is an Undo action 3. When Undo action is used, the top item is removed from the Stack Stack Overflow Stack Underflow Keep Going Left until you cant, then go back to the last Node and try to go Right, Repeat ABCDEFGHIJ If all Adjacent Nodes have been Discovered Graph Tree 207. How do you use Pre Order Traversal? 208. How do you use In Order Traversal? 209. How do you use Post Order Traversal? 210. What are the two ways of measuring the Complexity of an Algorithm? 211. Order these time complexi- ties from worst to the best O(nlogN), O(1), O(logN), O(n!), O(n^2), O(N), O(K^n) 212. What is the time complexity of Binary Search? 213. What is the time complexity of Merge Sort? 214. What is the time complexity of Bubble Sort? 215. What is the time complexity of Linear Search? 216. How can you make a Bubble Sort more Efficient? Mark left hand side of each Node Starting from the left, output each Node after you pass it Mark bottom side of each Node Starting from the left, output each Node after you pass it Mark right hand side of each Node Starting from the left, output each Node after you pass it - Time taken - Space taken O(1) O(logN) O(n) O(nlogN) O(n^2) O(K^n) O(n!) O(log n) O(nlogn) O(n^2) O(n) Decrease the number of Innerloops by one each time an Outerloop is completed Set a Boolean SwapsMade to True every time 217. What is a Tractable Prob- lem? 218. What is an Intractable Prob- lem? 219. What is a Decidable Prob- lem? 220. What is a Higher Order Function? 221. Why is the time complexity for Bubble Sort n^2? a Swap is made that resets back to False at the Start of the Outerloop, if SwapsMade = False at the end of a pass, exit the loop A problem that can be solved in a Reasonable amount of time A problem that can't be solved in a Reason- able amount of time A problem that can be solved by an algorithm A Function that takes another Function as a Parameter or a Function that returns a Func- tion There are two loops within each other/ loops are nested Each loop loops N times 222. What is a Set? An unordered collection of values without any duplicates 223. What is the Set Comprehen- sion for X is an Integer and between -3 and 3 and dis- play X*3 224. What is the Set Comprehen- sion Formula? {x*3 | x Z ^ x-4 ^ x4} {x | x ... ^ x...} Output x Where is a (Insert Symbol e.g. Z) And x is greater than... 225. What is a Subset? If A is a subset of B if all elements of A are also elements of B A†B 226. What is a Proper Subset? When all of a sets elements are in another set Cant be equal to the other set. 227. What is a Countable Set? A finite set where the elements can be count- ed using natural numbers. (All Integers but not Not Real Numbers) 228. What is a Membership of a Set? 229. What is the Union Between Set A and B? (A U B) Set A: {2,4,6,8} Set B: {1,2,3,4,5,6} 230. What is the Intersection be- tween Set A and B? (A ) B) Set A: {2,4,6,8} Set B: {1,2,3,4,5,6} 231. What is the Difference be- tween Set A and B? (A/B) Set A: {2,4,6,8} Set B: {1,2,3,4,5,6} 232. What does the Regular ex- pression a* mean? 233. What does the Regular ex- pression a+ mean? 234. What does the Regular ex- pression ab?c mean? 235. What does the Regular ex- pression a | b mean? 236. What does the regular ex- pression a+(bc)* mean? 237. Is A a Proper Subset of B? A: {1,2,3} B: {1,2,3} If an Item is in a Set e.g. 3 R If an Item is not in a Set -3.2 N A U B: {1,2,3,4,5,6,8} All Items across both Sets A ) B: {2,4,6} Items that are in both Sets AB: {8} Items that are exclusive to the first Set 0 or more repetitions of a 1 or more repetitions of a The previous character (b) is optional a or b 1 or more a's followed by 0 or more bc's No A is only a Subset of B as it contains all of B's values 238. What is the Cartesian Prod- uct of Set A and B? A: {x,y} B: {z} 239. Is Sorting a List Tractable or Intractable? 240. What is the Time Complexi- ty of a Hashing Table? 241. What is a way to reduce Col- lisions in a Hash Table? {x,z} {y,z} Tractable O(1) Add more indexs 242. What is Open Hashing? If there is a Collision put the data in the next free index 243. What is Closed Hashing? If there is a Collision, use a separate column for Pointers that point to the Data 244. How does Hashing Work? Hash Algorythm applied to key Hash Algorythm is usually a MOD function The Result is where the Data should be Stored If Location is full then use the next free loca- tion 245. What is a Collision on a Hash Table? 246. What are the Steps of Re- hashing to increase Stor- age? When two values produce the same hash and data in the table could be overwritten. A new Hash Table is created with more Indexs Each Value is inserted into the new table us- ing the new Algorythm 247. Why is Hashing used? To speed up searching, adding and deleting of records 248. What is an Advantage of a List over Hashing? No empty records so uses less memory 249. What is a Binary Tree? - Max two branches per node - Has a Root 250. How can Data be Collect- ed from WiFi Networks from outside of the Network? 251. How to prevent Data be- ing Collected from WiFi Net- works from outside of the Network? 252. Why is Reverse Polish used? 253. Explain how a stack could be used in the process of evaluating an expression in Reverse Polish notation 254. What is the Halting Prob- lem? 255. Represent 3 + 4 * 2 - 1 in Reverse Polish 256. Is the Halting Problem De- cideable? 257. What is a Universal Turing Machine? 258. How does a Laser Printer Work? .. It is possible for WiFi Signals to travel over a large distance and any Wifi Receiver in the area can read the Data Packets. - Encrypt data using WPA / WPA2 - Disable SSID - Use a Wired Network - No need for Brackets - Easier for Computer to Evaluate - No need for Backtracking - Add values to Stack - When Operator reached, pop first 2 values of Stack and perform the operation - Add the result back onto the Stack Determining if a program will Halt, without running the program 342*+1- No Capable of Representing any FSM Faithfully executes operations on the Data precisely as usual Printer generates Bitmap Image of page Drum is negatively charged Laser reflected by mirror is shone on Drum to Reverse charge Toner is given negative charge Toner sticks to Drum at Positive areas 259. What does a Turing Machine consist of? 260. Why is a Universal Turing Machine better than any Computer? 261. Why is Sorting a List a Tractable Problem? 262. What approach would a Pro- grammer take to an In- tractable Problem? 263. When do Turing Machines Stop? 264. What is Representational Abstraction? 265. What is Abstraction by Gen- eralisation? Paper passed over Drum and Toner sticks to it Heated rollers fuse the toner onto the paper - Infinite Tape - Read/Write Head - Set of Accepting/ Halting States It has an Infinite amount of Memory Time Complexity is Polynomial or Better, no matter how long the list Using Heuristic to create an Algorithm that makes a guess or provides a Solution close to the Answer/ one that only works in some cases. When they reach their Halting Point Removing Unnecessary Details Grouping by Common Characteristics 266. What is Information Hiding? Hiding all details of an object that do not con- tribute to its Essential Characteristics (Hiding Make of Car when working out how many Cars will fit on a Ferry and focusing on Size and Weight) 267. What is Procedural Abstrac- tion? 268. What is Functional Abstrac- tion? Breaking down a complex model into a series of Reusable Procedures Hiding the Method from the rest of the Solu- tion 269. What is Data Abstraction? Hiding how Data is Represented 270. What is Problem Abstrac- tion? 271. Which Time Complexities are Intractable 272. What is the Dot Product of A and B? a = [4, 3] b = [4, 2] Removing Details until the Problem reduces to one which has already been solved O(k^n) O(n!) 4x4 = 16 2x2 = 6 22 273. What is Automation? Models are put into action to solve problems 274. Why are Databases Nor- malised? 275. What is Procedural Decom- position? 276. Is the set of Strings Defined by a Regular language al- ways Finite in Size? 277. Can FSM's represent all Regular Languages? 278. What are the Steps involved in Adding an Item to a Lin- ear Queue? 279. What are the Steps involved in Adding an Item to a Prior- ity Queue? 280. Why Does a Vector Graphic take up less Storage than a Bitmap? - To Eliminate Data Redundancy - To Reduce Repeated Data Breaking a problem into smaller problems Each of which solves an identifiable task Each of which might be further divided No Yes Check if Queue is full If not, add 1 to the Value of the Rear Pointer Add Item to Index of Rear Pointer Start from Rear Pointer Move each Index down until an Item has a Higher or More Equal Priority Add Item to empty Index Bitmap has to store Colour of Each Pixel, Vector doesn't. A Large Image can be comprised of few Ob- 281. What is the Relationship be- tween Bit Rate and Band- width? 282. Create a Database Table for Facility when FacilityID is a Primary Key Facility(FacilityID, Descrip- tion, MaxPeople, PricePer- Hour) 283. What are the 3 Headings for a Database Query? 284. Why is a Laser Printer with a Wireless Network Adapter appropriate for a Small Net- work? jects in a Vector but requires thousands of pixels. Vector Graphics have to store the Properties of each Object which doesn't require a lot of Memory Directly Proportional Create Table Facility( FacilityId INT Primary Key Description VARCHAR(100) MaxPeople INT PricePerHour Currency) SELECT FROM WHERE - Low Cost per page (Toner Cheaper than Ink) - High Speed - Easy to Share Printers between many de- vices - Can connect to Printer Wirelessly 285. What is System Software? Software used to Manage a Computer 286. What does the Control Unit do? 287. Why is Hashing used for En- cryption? 288. What is the Difference be- tween Global and Local Variables? Controls Fetch Execute Cycle Determines Type of Instruction Executes some Instructions The Hash Function can't be reversed to form the key Global Variables can be Accessed from the Entire Solution 289. What are Advantages of Lo- cal over Global Variables? - Dont use Memory when havent been called so Memory can be reused - Local Variables only exist while the Subrou- tine is executing