Description
1) Consider a text with n zeros. How many character comparisons (in terms of n) will the brute-force
string matching algorithm make in searching the pattern 0010? What is the worst case input pattern
of length 3 (3 bits) for the brute-force algorithm?
2) Apply brute-force algorithm for the travelling salesman problem.
3) Design a decrease-by-half algorithm for computing log 𝑛 (base 2). Calculate its time efficiency.
4) A bottle factory produces bottles of equal mass. During a production, the weight of one of the
bottles is set incorrectly. The factory scale will be used to find this bottle. Design a decrease-andconquer algorithm which finds the that bottle. Analyze the worst-case, best-case and average-case
complexities of your algorithm. Explain your algorithm in the report file.
5)
Assume you have 2 arrays which are both unsorted. Provide a divide and conquer algorithm which
finds the x
th element of the merged array of these two arrays. Write the pseudocode of your
algorithm and calculate its worst-case running time. Tabu: Merging these arrays at first and then
finding the x th element is forbidden.
