Question 1: Explain the difference between linear search and binary search. Include one advantage of each method.

Answer: Linear search checks each element sequentially until the target is found; binary search repeatedly divides a sorted list to locate the target. Advantage of linear search: simple to implement; advantage of binary search: faster on sorted lists.

Question 2: Describe a scenario where linear search would be more appropriate than binary search.

Answer: When the list is unsorted or small, making linear search more practical due to its simplicity.

Question 3: Given an unsorted list of numbers, outline the steps to perform a linear search for a specific number.

Answer: Start from the first element, compare it to the target number. If it matches, return the position; if not, move to the next element and repeat until the number is found or the list ends.

Question 4: Complete the following truth table for the AND logic gate: | Input A | Input B | Output | |---------|---------|---------| | 0 | 0 | ? | | 0 | 1 | ? | | 1 | 0 | ? | | 1 | 1 | ? |

Answer: 0, 0, 0, 1

Question 5: Complete the truth table for the OR logic gate based on the following headers.

Answer: 0, 1, 1, 1

Question 6: Draw a logic circuit that uses AND, OR, and NOT gates to implement the following function: Output is true only when exactly one of two inputs is true.

Answer: A correct sketch would include two inputs, an XOR gate (or equivalent combination using AND, OR, NOT), with the appropriate connections. If not using an XOR gate directly, the circuit should be equivalent: (A AND NOT B) OR (NOT A AND B).

Question 7: Sketch a flowchart to describe the process of searching for a specific name in a list of names.

Answer: A flowchart should include: start, input list and target name, initialize index to 0, check if current element matches target, if yes, output 'found' and end, if no, increment index and repeat until end of list. If not found, output 'not found'.

Question 8: What is the time complexity of linear search in Big O notation? Briefly justify your answer.

Answer: O(n) because in the worst case, linear search checks each element once until it finds the target or reaches the end of the list.

Question 9: What is the main advantage of binary search over linear search? Under what condition can binary search be used?

Answer: Binary search is faster, with a time complexity of O(log n). It can only be used when the list is sorted.

Question 10: Explain how a search algorithm could be optimized for very large datasets.

Answer: Using efficient algorithms like binary search on sorted data, or employing data structures like binary search trees or hash tables to reduce search time.

Question 11: Design a simple search algorithm outline for finding a number in a sorted list. Include steps briefly.

Answer: Start with two pointers: low at start, high at end. While low <= high, find mid. If mid element equals target, return position. If mid element is greater than target, set high to mid - 1; if less, set low to mid + 1. Repeat until found or search space is empty.