Question 1: Explain the difference between linear search and binary search algorithms.

Answer: Linear search checks each item in a list sequentially until the target is found or the list ends. Binary search repeatedly divides a sorted list in half to find the target, making it faster for large datasets.

Question 2: Given a list of numbers: 3, 7, 12, 19, 25, 30. Describe how a binary search would locate the number 19.

Answer: Binary search would start by comparing 19 to the middle element (12). Since 19 is greater, it searches the upper half: 19, 25, 30. Next, it compares 19 to 19, finds a match, and terminates.

Question 3: Describe a scenario where linear search is more appropriate than binary search.

Answer: Linear search is suitable when the list is unsorted or very small, as it does not require sorting and can find the target in any list regardless of order.

Question 4: Complete the truth table for a NAND gate with inputs A and B:

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

Question 5: Draw a logic circuit for a NOT gate connected to an AND gate that has two inputs A and B. Label each gate clearly.

Answer: A correct sketch would show a NOT gate with input A, with its output connected to one input of the AND gate. The other input of the AND gate is B. The circuit should be clearly labeled.

Question 6: Using logic gates, create a circuit that outputs true only when either input A or input B is true, but not both (exclusive OR).

Answer: The circuit should include an XOR configuration, typically constructed with AND, OR, and NOT gates to ensure output is true only when exactly one input is true.

Question 7: Explain how a binary search algorithm improves efficiency over linear search in large datasets.

Answer: Binary search reduces the number of comparisons by dividing the search interval in half each time, making it much faster than linear search, especially with large sorted datasets.

Question 8: Describe the process of searching for a specific word in a sorted dictionary using binary search.

Answer: Start at the middle word, compare it to the target. If the target comes before, search the lower half; if after, search the upper half. Repeat until the word is found or the search interval is empty.

Question 9: Sketch a truth table for an AND gate with two inputs, A and B. Include all possible combinations of inputs and the corresponding output.

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

Question 10: Draw a logic circuit that implements the following condition: output is true only if both inputs A and B are false.

Answer: A correct circuit would involve NOT gates taking inputs A and B, with their outputs connected to an AND gate. The final output is true only when both A and B are false, achieved by inverting the inputs before AND.

Question 11: Explain why binary search requires the list to be sorted before searching.

Answer: Binary search relies on dividing the list based on comparisons to the middle element, which only works correctly if the list is sorted. Without sorting, the search won't reliably find the target.