Question 1: Explain what data compression is and why it is useful in computer science.

Answer: Data compression is the process of reducing the size of data to save storage space or speed up transmission. It is useful because it makes data transfer faster and saves storage resources.

Question 2: Describe the difference between lossless and lossy compression.

Answer: Lossless compression reduces file size without losing any information, allowing the original data to be perfectly reconstructed. Lossy compression reduces file size by removing some data, which may result in a loss of quality or detail.

Question 3: A text file contains the word 'compression' repeated 1000 times. If each word is stored as 10 bytes uncompressed, what is the size of the file? How might compression reduce this size?

Answer: Uncompressed size = 1000 words x 10 bytes = 10,000 bytes. Compression could reduce this size by removing duplicate data, potentially reducing the size significantly, especially if a lossless algorithm is used.

Question 4: Complete the truth table for an AND gate with two inputs, A and B.

Answer: A | B | Output ---|---|--------- 0 | 0 | 0 0 | 1 | 0 1 | 0 | 0 1 | 1 | 1

Question 5: Draw a logic circuit for an OR gate with two inputs labeled A and B. Include the appropriate logic gate symbol and label the inputs and output.

Answer: A correct sketch will show an OR gate symbol with two input lines labeled A and B entering the gate, and one output line labeled 'Output'.

Question 6: Explain why run-length encoding is effective for compressing simple images with large areas of uniform color.

Answer: Run-length encoding compresses data by replacing sequences of the same value with a count and the value. It is effective for simple images with large uniform areas because it reduces repeated data into shorter representations.

Question 7: Describe a scenario where lossy compression would be preferred over lossless compression.

Answer: Lossy compression is preferred in scenarios like compressing photographs or videos where slight loss of quality is acceptable to greatly reduce file size, such as in online streaming or sharing images on social media.

Question 8: Sketch a diagram showing how Huffman coding assigns shorter codes to more frequent characters and longer codes to less frequent characters.

Answer: A correct sketch will show a binary tree with more frequent characters connected closer to the root, receiving shorter binary codes, while less frequent characters are connected further down with longer codes.

Question 9: Explain how dictionary-based compression methods, such as LZ77, work to reduce data size.

Answer: Dictionary-based methods identify repeated sequences of data and replace them with references to earlier occurrences stored in a dictionary, reducing the overall size by avoiding duplicate data.

Question 10: Design a simple scheme for compressing a string of lowercase letters where the most common letter is 'e'. Describe how your scheme would encode the string 'beetle'.

Answer: One possible scheme assigns a shorter code to 'e' (e.g., '0') and longer codes to other letters (e.g., 'b'='10', 't'='110', 'l'='111', etc.). For 'beetle', encoding might be: b='10', e='0', e='0', t='110', l='111', e='0'. The compressed sequence would be '10 0 0 110 111 0'.