## 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.