HW2
Submit a single .pdf for the written problems and .java codes for the coding problems to me via email by the date of the deadline (11:59 pm)
(1) Please show ALL of your work (Step by Step).
******************************************** Written ********************************************
1. [Written 10pt] Design a brute-force algorithm and a linear-time algorithm for computing the value of a polynomial
p(x)=a_n x^n + a_{n−1} x^{n−1} + ... + a_1x + a_0
at a given point x0 and determine their worst-case efficiency class.
2. [Written 10pt] Prove that if bubble sort makes no exchanges on its pass through a list, the list is sorted and the algorithm can be stopped.
3. [Written 10pt] Determine the number of character comparisons made by the brute-force algorithm (in the book) in searching for the pattern GANDHI in the text THERE_IS_MORE_TO_LIFE_THAN_INCREASING_ITS_SPEED. Assume that the length of the text—it is 47 characters long—is known before the search starts.
4. [Written 10pt] The closest-pair problem can be posed in the k-dimensional space, in which the Euclidean distance between two points p′(x′1, . . . , x′k) and p′′(x′′1, . . . , x′′k) is defined as below.
What is the time-efficiency class of the brute-force algorithm for the k- dimensional closest-pair problem? (Hint: The running time should depend on k and n).
5. [Written 6pt] Find the convex hulls of the following sets and identify their extreme points (if they have any):
(Hint: Revisit the definition of convex hulls and extreme points in the book)
a. a line segment
b. a square
c. the boundary of a square
6. [Written 10pt] What modification needs to be made in the brute-force algorithm for the convex-hull problem to handle more than two points on the same straight line?
7. [Written 10pt] Given n positive integers, partition them into two disjoint subsets with the same sum of their elements. (Of course, the problem does not always have a solution.) Design an exhaustive-search algorithm for this problem.
8. [Written 10pt] A magic square of order n is an arrangement of the integers from 1 to n^2 in an n × n matrix, with each number occurring exactly once, so that each row, each column, and each main diagonal has the same sum.
a. Prove that if a magic square of order n exists, the sum in question must be equal to n(n2 + 1)/2.
b. Design an exhaustive-search algorithm for generating all magic squares of order n.
9. [Written 10pt] Consider the following graph (see below).
a. Write down the adjacency matrix and adjacency lists specifying this graph.
b. Give a DFS ordering and a BFS ordering of the graph.
10. [Written 10pt] Explain how one can identify connected components of a graph by using a DFS or a BFS.
11. [Written 10pt] A graph is said to be bipartite if all its vertices can be partitioned into two disjoint subsets X and Y so that every edge connects a vertex in X with a vertex in Y. (One can also say that a graph is bipartite if its vertices can be colored in two colors so that every edge has its vertices colored in different colors; such graphs are also called 2-colorable.) For example (see below), graph (i) is bipartite while graph (ii) is not.
Design a DFS-based or a BFS-based algorithm for checking whether a graph is bipartite.
12. [Written 10pt] Given an 8-pint jug full of water and two empty jugs of 5- and 3-pint capacity, get exactly 4 pints of water in one of the jugs by completely filling up and/or emptying jugs into others.
a. Discuss how you can solve this puzzle by using breadth-first search.
b. Solve this puzzle.
******************************************** Coding ********************************************
1. [Coding 10pt] Consider the problem of counting, in a given text, the number of substrings that start with an A and end with a B. For example, there are four such substrings in CABAAXBYA. Design a brute-force algorithm and a linear-time algorithm for this problem and determine their efficiency class.
Please include some test cases to verify the correctness of your algorithm.
