Give a divide-and-conquer algorithm with a time complexity of 0 (logn) to solve the problem of...

 

Transcribed Image Text:

Give a divide-and-conquer algorithm with a time complexity of 0 (logn) to solve the problem of Finding the Single Letter. Finding the Single Letter: Given a string where all unique letters are supposed to appear twice one after one (e.g., "aa"). There may occur an error where one letter appears only once. Can you find the position of that single letter? Inputs with more than one single letter (e.g., "bbaddc") or letters occurring more than twice (e.g., "aaaa") are considered invalid. We assume all inputs are valid and you do not need to handle any exceptions. Examples: Input "ccddabbffgg" returns 4 Input "ddccaahhbb" returns None Input "iihhjjyyc" returns 8 In your T2-1.py file, provide 1) (7 marks) the pseudocode of your divide-and-conquer algorithm in the prologue docstrings, 2) (3 marks) the explanation of its complexity in the prologue docstrings, 3) (15 marks) a Python function find_single that implements your algorithm. Your program will be marked on correctness (8 marks), style and logic (4 marks), and comments and readability (3 marks). Give a divide-and-conquer algorithm with a time complexity of 0 (logn) to solve the problem of Finding the Single Letter. Finding the Single Letter: Given a string where all unique letters are supposed to appear twice one after one (e.g., "aa"). There may occur an error where one letter appears only once. Can you find the position of that single letter? Inputs with more than one single letter (e.g., "bbaddc") or letters occurring more than twice (e.g., "aaaa") are considered invalid. We assume all inputs are valid and you do not need to handle any exceptions. Examples: Input "ccddabbffgg" returns 4 Input "ddccaahhbb" returns None Input "iihhjjyyc" returns 8 In your T2-1.py file, provide 1) (7 marks) the pseudocode of your divide-and-conquer algorithm in the prologue docstrings, 2) (3 marks) the explanation of its complexity in the prologue docstrings, 3) (15 marks) a Python function find_single that implements your algorithm. Your program will be marked on correctness (8 marks), style and logic (4 marks), and comments and readability (3 marks).

Answer rating: 100% (QA)

The problem statement shows that we need to develop a divideandconquer algorithm to find the position of a single letter in a string where all unique ... View the full answer