CSE 321
Homework 4
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 xth 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.
