Q1.
Write a program called "LinearStringSearch.java" that looks for a target string value in an array of string values. Initialize the array with 10 random strings. The target string should be searched from the beginning of the array to the end of the array. Then, modify the algorithm so that after completing the first search from the beginning of the array to the end, a "second search" for the string in the array is conducted, except that the second search starts from the end of the array and moves towards the beginning of the array.
Print on console, using the index of the target string, which of the two, the beginning-to-end or the end-to-beginning search, found the target string quicker. Ignore outcomes if the target string is not found in the array.
Assuming that statistics on these two types of searches for the last 1000 runs are made available, discuss whether it is advantageous or not to use the statistics to opt one type of search over the other. For example, the statistics could indicate that out of 1000 search runs, 780 runs produced faster results when searching from end to beginning. Modify the program to include this particular functionality so that
a) the algorithm either searches beginning-to-end or end-to-beginning depending on this statistic
b) the algorithm updates the statistic using the outcome of the current search - that is, if the current search is faster for an end-to-beginning search, then increment the statistic by 1 to 781; else decrement the statistic by 1 to 779.
Q2.
Cattell-Horn-Carroll's theory attempts to measure intelligence quotient (IQ) in terms of the ten factors listed below. These ten factors take on different values. The IQ is calculated as a sum of the values of the ten factors. Write a Java program to input, calculate, and print the IQ of a person based on this theory.
- Fluid intelligence (Gf): the broad ability to reason, form concepts, and solve problems using unfamiliar information or novel procedures.
Input the Gf value interactively from the console. The value of Gf ranges from 1 to 15.
- Crystallized intelligence (Gc): the breadth and depth of a person's acquired knowledge, the ability to communicate one's knowledge, and the ability to reason using previously learned experiences or procedures.
Possible values of Gc are 'excellent', 'acceptable', and 'poor'. The value of Gc (excellent, acceptable, or poor) is known and should be encoded in the program by default. if excellent, gc contributes a value of 15 to iq; if acceptable, Gc contributes a value of 8 to IQ; and if poor, Gc contributes a value of 3 to IQ.
- Quantitative reasoning (Gq): the ability to comprehend quantitative concepts and relationships and to manipulate numerical symbols.
The value of Gq is 'true' or 'false', and is to be input interactively from the console. If true, Gq contributes a value of 10 to IQ; if false, Gq does not contribute to IQ at all.
- Reading and writing ability (Grw): basic reading and writing skills.
Possible values of Grw are 'brilliant', 'good', 'normal', and 'poor'. The value of Grw is known and should be encoded in the program by default. If brilliant, Grw contributes a value of 15 to IQ; if good, Grw contributes a value of 10 to IQ; if normal, Grw contributes a value of 6 to IQ; if poor, Grw contributes a value of 2 to IQ.
- Short-term memory (Gsm): the ability to apprehend and hold information in immediate awareness and then use it within a few seconds.
Possible values of Gsm are 'good' and 'bad'. Input Gsm values interactively from the console. If good, Gsm contributes a value of 15 to IQ; if bad, Gsm contributes a value of 5 to IQ.
- Long-term storage and retrieval (Glr): the ability to store information and fluently retrieve it later in the process of thinking.
The values of Glr are in the range of 1 to 15. The value of Glr is known and should be encoded in the program by default.
- Visual processing (Gv): the ability to perceive, analyze, synthesize, and think with visual patterns, including the ability to store and recall visual representations.
The values of Gv are in the range of 1 to 10. The value of Gv is known and should be encoded in the program by default.
- Auditory processing (Ga): the ability to analyze, synthesize, and discriminate auditory stimuli, including the ability to process and discriminate speech sounds that may be presented under distorted conditions.
The values of Ga are in the range of 1 to 5. Input the Ga value interactively from the console.
- Processing speed (Gs): the ability to perform automatic cognitive tasks, particularly when measured under pressure to maintain focused attention.
Gs can be calculated as a relation to the person's age. The age should be input interactively from the console. The age is in the range from 21 to 75. Gs is calculated using the formulation [100 - age] / 10.
- Decision/reaction time/speed (Gt): reflect the immediacy with which an individual can react to stimuli or a task. Gt is a function Gs and is calculated by the formula: [10 - Gs].
Q3.
An alternative to bubble sort is bi-directional bubble sort where the algorithm compares each adjacent pair of elements in the input array. The values are swapped as per the comparison function. Bi-directional bubble sort is also known as cocktail shaker sort, shaker sort, or double-direction bubble sort. Given below is a piece of implementation of the same.
public class ShakerSort {
public static void ShakerSort(int[] a) {
for (int p = 1; p <= a.length / 2; p++) { // phase p of Shaker sort
// first do left-to-right bubbling pass
for (int i = p - 1; i < a.length - p; i++)
if (a[i] < (a[i+1]))
myswap(a, i, i + 1);
// now do right-to-left bubbling pass
for (int i = a.length - p - 1; i >= p; i--)
if (a[i] < (a[i-1]) < 0)
myswap(a, i, i - 1);
}
}
}
Suppose we are to sort the elements [6,5,2,8,3,1]. The number of phases is computed as 3 (as per the code above). In the left to right bubbling pass of the first phase, the pair (6,5) is compared and swapped to get the array [5,6,2,8,3,1]. Next the pair (6,2) is compared and swapped to get [5,2,6,8,3,1]. The next comparison (6,8) causes no swap. When 8 and 3 are compared, a swap is done to get [5,2,6,3,8,1]. The final comparison of this pass is (8,1). Following the swap, we get [5,2,6,3,1,8]. Now the right-to-left pass begins. The pair (3,1) is compared first, a swap is done, and we get the array [5,2,6,1,3,8]. Next the pair (6,1) is compared, and we get [5,2,1,6,3,8]. At the end of the right-to-left pass we have [1,5,2,6,3,8]. Phase 2 works on the segment [5,2,6,3]. After the left-to-right pass, we have [2,5,3,6]; and after the right-to-left pass, we have [2,3,5,6]. The third phase works on the segment [3,5].
Suppose we start with an array a[0: n-1] of elements to be sorted. After the left-to-right bubbling pass of phase 1, the largest element is in the rightmost position. So the right-to-left pass needs to be concerned only with elements in positions 0 through n-2 of the array. Following the right-to-left pass, the smallest element is in position 0 of the array.
Consequently, the next phase needs to be concerned only with the elements in positions 1 through n-2.
In general, the left-to-right pass of phase p of shaker sort needs to be concerned only with elements in positions p-1 through n-p, and the right-to-left pass of this phase needs to be concerned only with elements in positions n-p-1 through p.
Use the code given above to develop the program as "ShakerSort.java" and identify its complexity. Discuss its advantages compared to a regular bubble sort. What happens when n is odd?
Q4.
Implement the following application using a singly linked list. This application accepts from console and stores a list of 10 names (first name followed by last name) of your friends in the singly linked list. The order of arrival of these names determines the sequence of names in the linked list.
Implement a method that sorts the original sequence into a new sequence based on the alphabetical order of the last names. Modify the program using a doubly-linked list data structure, and add a method that searches for the first name of a friend.
Finally, discuss what would happen when you link the last entry in the list with the first entry of the list.