How to Solve It by Computer

Given two glasses marked A and B. Glass A is full of raspberry drink and glass B is full of lemonade. Suggest a way of exchanging the contents of glasses A and RB.

Design an algorithm for the cyclic exchange a to b, b to c, and c to a.

Design an algorithm for the cyclic exchange d to c, c to b, b to a, and a to d.

Given two variables of integer type a and b, exchange their values without using a third temporary variable.

What happens when the arguments given to the procedure exchange are i and afi]?

Modify the algorithm above so that marks are read until an end-offile is encountered. For this set of marks determine the total number of marks, the number of passes, and the percentage pass rate.

Design an algorithm that reads a list of numbers and makes a count of the number of negatives and the number of non-negative members in the set.

Youare given the problem described above. However, assume that your program is to start out with the variable count initialized to the total number of students n. On termination, the value of count should again represent the number of students that passed the examination. If there were more passes than fails, why would this implementation be better than the original one?

For a given n, design an algorithm to compute 1/r!.

Fora given x and a given n, design an algorithm to compute x"/n!.

Design an algorithm to determine whether or not a number n is a factorial number.

Design an algorithm which, given some integer 7, finds the largest factorial number present as a factor in n.

Design an algorithm to simulate multiplication by addition. Your program should accept as input two integers (they may be zero, positive, or negative).

The binomial theorem of basic algebra indicates that the coefficient "C, of the r power of x in the expansion of (x + 1)" is given by "Ge tl " ri(n—r)t Design an algorithm that evaluates all coefficients of x for a given value of n.

Design an algorithm to find the sum of the first n terms of the series fe OlLtU+2+3!4 - +a! (n=0)

The exponential growth constant e is characterized by the expression 1,1,1,1 a a a at © Devise an algorithm to compute ¢ to n terms.

Design an algorithm to evaluate the function cos (x) as defined by the infinite series expansion 2 x4 x6 cos (x)=1-F +h =e aaa The acceptabie error for the computation is 10+.

Implement the Fibonacci algorithm as a function (hal accepts as input two consecutive Fibonacci numbers and returns as output the next Fibonacci number.

The first few numbers of ihe Lucas sequence which is a variation on the Fibonacci sequence are: 13 4 7 11 18 29... Design an algorithm to generate the Lucas sequence,

Given a=0, b=1, and c=1 are the first three numbers of some sequence. All other numbers in the sequence are generated from the sum of their three most recent predecessors. Design an algorithm to generate this sequence.

Given that two numbers d and ¢ are suspected of being consecutive members of the Fibonacci sequence design an algorithm that will refute or confirm this conjecture.

The ascending sequence of all reduced fractions between 0 and 1 which have denominators <r is called the Farey series of order a. The Farey series of order 5 is: O11121323421 1543525 345 8 Denoting this serics by % m1 ., Yo Vi Ye it can be shown that X=0 yo=l x=) ya and in general for k=1 (y.tn Xia? =| 5" Xin Le k+L +n) Vier = [| Vent Ye keh where [q| is the greatest integer less than or equal to g. Design an algorithm te generate the Farey series for a given n. (See Design an algorithny to getie rate the Paret series foragivenu: (See D. E. Knuth, The Art of Computer Programming, Vol. 1, Fundamental Algorithms, Addison-Wesley, Reading, Mass., p. 157. 1969.)

Generate the sequence where each member is the sum of adjacent factorials, i.e. A= +0! fe=2!41! fs=3!42! Note that by definition 0!= 1.

Design an algorithm that counts the number of digits in an integer.

Design an algorithm to sum the digits in an integer.

Design an algorithm that reads n single digits and converts them into one decimal integer; for example, convert {2, 7, 4, 9, 3} to 27493.

Modify the algorithm to incorporate the generalization suggested in note (7).

Design an algorithm that converts binary numbers to octal.

Design an algorithm that converts binary numbers to decimal.

Design an algorithm that accepts as input a decimal number and converts it to the binary-coded decimal (bed) representation. In the bed scheme each digit is represented by a 4-bit binary code.

Design an algorithm that accepts as input a decimal fraction and converts it to the corresponding binery fraction of a fixed accuracy converts it to the corresponding binary fraction of a fixed accuracy (e.g. 0.625,) = 0.101, = 1x2 '+0x«2 74+1x2 3).

Design an algorithm that will handle conversions to decimal where the inpui characier suing may contain a decimal point.

Design an algorithm to convert a decimal representation for a number to the corresponding character string representation.

Given that all ascii codes are less than 128, design an algorithm that reads a given set of data and decides whether or not it may contain decimal data.

Implement the square-root-finding algorithm that was originally proposed.

Design an algorithm that inputs n positive numbers and computes their geometric mean.

Design an algorithm that finds the integer whose square is closest to but greater than the integer number input as data.

Design and implement an algorithm to iteratively compute the reciprocal of a number.

Modify the algorithm so that the square root of n does not need to be explicitly computed.

Design an algorithm to produce a list of ali exact divisors of a given positive integer 7.

Design and implement an algorithm that finds the smallest positive integer that has n or more divisors.

For the integers in the range 1 to 100 find the number that has the most divisors.

It is possible to improve the efficiency of our smallest divisor algorithm by generating a sequence of ds that excludes multiples of 3 as well as multiples of 2. Implement an algorithm that includes this refinement.

An algorithm due to Fermat can be used to find the largest factor f (less than or equal to V/n) of an odd integer. Fermat established that the following relations hald form the following relations hold for n. n- fxg with f<g n=x?~y? with Osy<xen where x=[(f+g)/2]. y=(e-f1/2} The algorithm can be implemented by introducing two auxiliary variables x' and y' such that x'=2x+1 y'=2yt1 The odd values that these two variables can assume are: x’: An +1, Bn]+3, Avaj+s, ... ViL35.7.. Noting that successive squares can be generated by summing the odd sequence, the error ¢ (initially set to [| \/n}?—n]) when positive is reduced by subtracting successive y’ values until it is made zero or negative, and, when negative it is reduced by adding successive x’ values. This process terminates when e = 0, At this point the factor f can be found from f= |G! -y')/2} Implement Fermat's algorithm.

Implement a ged algorithm that uses a while-loop rather than a repeat-loop.

Design a gcd algorithm that does not use either division or mod functions.

Design an algorithm that will find the ged of n positive non-zero integers.

Ifthe twointegers whose ged is sought may contain multiples of two, then a better way to proceed is by first reducing each of the integers by their common multiples of two, taking into account their contribution to the ged. When one integer contains multiples of two it is best to remove these contributions before proceeding with the standard gcd mechanism. Try to incorporate these ideas into a more efficient ged algorithm.

Design an algorithm io find aii common prime divisors of iwo numbers, (Hint:

It is well known that adjacent Fibonacci numbers do not share a common divisor greater than 1 (they are relatively prime). Design an algorithm that tests this observation for the first m integers.

Design an algorithm to compute the smallest common multiple (scm) of two non-zero positive integers 7 and p. The scm is defined as the smallest integer m such that # and p divide exactly into m.

Design an algorithm to compute the smallest common divisor other than one of two positive non-zero integers.

Given the two fractions a/b and c/d, design an algorithm that computes their sum in terms of the smallest common denominator.

Atthe cost of some additional storage the prime-testing loop can be simplified and speeded up. This involves moving the step for updating the mudtiple array outside this loop. Try to modify the algorithm to incorporate this refinement.

It is possible to implement a sieving algorithm which crosses out each composite (non-prime) number exactly once rather than a number of times. The algorithm is based on the idea that any non-prime x can be written as x = pg where k> | and q is a prime =p. Try to implement this algorithm (ref. D. Gries and J, Misra, “A linear sieve algorithm for finding prime numbers”, Comm. ACM, 21, 999-1003 (1978)).

Another interesting sequence of numbers is produced by starting out with the lst of all integers 1, 2, 3, .... 1. From this list every second number is removed to produce a new list. From the new list every third number is removed to give yet another list. Every fourth number is removed from this list and so the process continues. The numbers that remain after this process are called the lucky numbers. The first seven lucky numbers are 1,3, 7,9, 13,15, 21, .... Design an algorithm to list the lucky numbers in the first # integers.

The largest known primes are calied the Mersenne primes. They are of the form 2”~1 where p is prime. A test called Lucas’ test can be used to check whether a number of this form is prime. The test can be stated as follows, If p>2 then 2’~1 is prime only if 1-2 = Owhere the sequence / can be generated using = 4, 1.1. = (2-2) mod (2’—-1). Design an algorithm to generate the Mersenne primes in the first 4 integers.

Implement a version of the prime factorization algorithm that incorporates a sieve of Eratosthenes procedure.

implement a prime factorization algorithm that eliminates only niultiples of 2, 3 and 5 as divisors and compare il with 3.5.1 in terms of the number of divisions made.

Amicable numbers are pairs of numbers each of whose divisors add ty the other nuniber, (Note: 1 is included as a divisor but the numbers are not included as their own divisors.) Design and implement an algorithm that tests whether a given pair of numbers are amicable numbers.

A perfect number is one whose divisors add up to the number. Design and implement an algorithm that prints all perfect numbers between 1 and 500,

Confirm that the algorithm repeats after generating m random numbers. Compute the mean vaiue and variance for the set of mt pseudo-random numbers.

Check the uniformity of the distribution produced by the linear congruential method for m = 4096 by accumulating random numbers in blocks of 64 in the range 0-+4095 (e.g. the first block is 0-+63). Make a plot of the resulting histogram.

Uniformly distributed random numbers {r} can be used to generate arandom set that are exponentially distributed {x} using the formula Xx, aul log, (i~7) i= ~y loge 7 where A is a parameter of the exponential distribution. Implemeat the algorithm,

The polar method can be used to generate normally distributed random numbers in the range 0 to Lt. Itinvolves first generating two uniform random numbers r, and r,. Then if the expression for d below is =1 two normally distributed random numbers can be computed asm, and #,, Theat is. computed de ay snd ety. That is; d= (2r,~1)?+(2r,-1)? 2 lo; i n =0r-1(2 a) - 1 = (Or, -1)(—2 toed) Use these expressions te generate normally distributed random numbers.

Design an algorithm for power evaluation that is built upon a base 3 strategy rather than the current base 2 method. Compare the resulls for this new method with the current algorithm.

Design a complete precision power evaluation algorithm for values of x" that may exceed the compuler’s integer representation limit,

It is sometimes important to establish that a number is not a prime. To do this we can use a result that follows from the work of Fermat. ii is possible to show that for ali prime aunibeis cacept 2, the following condition holds: 2°! mod p=i This test can be performed in the order of log,(p) steps. Design an algorithm to test a number for non-primality. For simplicity, choose a prime such that 2! does not exceed your computer's integer word size representation limit.

Develop a recursive implementation that incorporates the ideas above for calculating the n' Fibonacci number. Compare the performance of the recursive method with the iterative solution,

What sequence of pairs of Fibonacci numbers would be needed to compute the 23" Fibonacci number using the present algorithm?

It is possible to multiply two numbers x and y by repeatedly halving y (ie. integer division) when it is even and reducing it by 1 when it is odd. When y is odd the current value of x is accumulated. When pis even, x is doubied. Impiemeni this muitiplication algorithm. (Nore: Doubling and halving operations correspond to “shift” operations which are very efficient on most computers.)

It is possible to compute n! in O(log, 1) steps. Try to develop such an algorithm for computing #! (Ref. A. Shamir, “Factoring numbers in O(log «) arithmetic steps”, Inf. Proc, Letts., 8, 28-31 (1979)).

What happens if the exchange process continues for rn steps rather than |n/2| steps?

Implement the array reversal algorithm suggested in note 6.

Design an algorithm that places the A clement of an ariay in position 1, the (k+1)" element in position 2, etc. The original 1% element is placed at (n—k+1) and so on.

Desigu au algoriilim thai rearranges the clements of au array so that all those originally stored at odd suffixes are placed before those at even suffixes. For example, the set i243 [4 45 [647 48h would be transformed to ap = 1 3 {547/244 16 [8

Modify the algorithm above so that a histogram is obtained only for each ten percentile range (e.g. 0-- 10%, 11-20%, ...) rather than for each individual mark.

Itis required to generate a histogram distribution for a set of daily average temperatures recorded in Antarctica. The temperatures are integer values in the range —40°C to +5°C. Design an algorithm to input n such temperatures and produce the appropriate distribution.

Modify the marks algorithm so that the mean and the median mark for the set are obtained. The median mark is that mark for which essentially half the candidates received thal mark or some smaller mark.

Design an algorithm to find the minimum in an array.

Design an algorithm to find the number of times the maximum occurs in an array of 2 elements. Only one pass through the array should he made.

Design aa algorithm to find the maximum in a set and the position (a) where it first occurs; (b) where it last occurs,

Design an algorithm that finds the maximum absolute difference between adjacent pairs in an array of n elements.

Design an algorithm that finds the second-largest value in an array of n elements.

Find the position of a number x, if it occurs, in an array of n elements.

Design an algorithm that finds the maximum by comparing each number with every other number and stops when it finds a number greater than or equal to all others. What happens when this method is implemented as efficiently as possible?

Design an algorithm to find the minimum, the maximum, and how many times they both occur in an array of n elements.

Find the minimum and maximum in an array of n elements using approximately 3n/2 comparisons by processing elements in pairs, comparing each pair's larger element with the current maximum and its smaller element with the current minimum.

Remove from an ordered array all numbers that occur more than once,

Delete from an ordered array all clements that occur more than k times.

Give an example of an array configuration that leads to (n - 2) squared data-movement operations.

Design an algorithm for storing an ordered array that contains many duplicates. Assume that the array has no negative elements.

Given a large ordered array in which repeated values commonly occur many times, design an adaptive duplicate-deletion algorithm that is more efficient than the preceding algorithm for this kind of data.

Implement the alternative partitioning method that advances i while a[i] is less than x, decreases j while a[j] is greater than x, and otherwise exchanges a[i] with a[j] before continuing.

Design an algorithm that extracts from a randomly ordered array all values lying within a specified range.

The problem of the Dutch national flag involves starting out with a row of n buckets, ie. buckei{1..n], each bucket containing a single pebble that is cither rod, white or bluc. The task is to arrange the pebbles so that all reds occur before all whites which in turn occur before all blue pebbles. Design and implement an algorithm to solve the Dutch national flag problem. {See E. W. Dijkstra, A Discipline of Programming, Prentice-Hall, Englewood Cliffs, N.J.. 1976. p.411.)

Implement and compare the two algorithms given for varying k values relative to n. For the comparison measure the number of exchanges in each case. Use a random number generator to produce suitable data sets.

For very small values of k relative ton (i.¢. for k< 10 and large n) itis possible to design a more efficient algorithm using the following idea. At cack stage in the algorithm the largest element in the first k values is exchanged with progressively smaller values in the set a{k+1], a[k+2], ..., a[n]. Design and implement this algorithm and compare it with the algorithm above for very small & relative to m.

Ifthe first k elements in the array are maintained as a heap or a tree data structure. we get a more efficient version of

The algorithm we have described can be improved by using a sampling method. The idea is to use say a 1% sample and find the k* smallest as the estimate of x (ref. R. W. Floyd und R. L. Rivest, “Expected time bounds for selection.” Comm. ACM, 18, 165-172, 1975). Implement and test this approach.

Implement the first design that was proposed for finding the longest monotone increasing subsequence.

Compare the performance of the algorithm in 4.7.1 with the algorithm above for (a) random data, (b) data with a long monotone increasing subsequence (say 0.511).

Design and implement an algorithm that prints out the longest inonotone increasing subsequence for a given set of data,

Design and implement an algorithm that determines the length of the longest monotone (it may be either increasing or decreasing) subsequence.

Design and implement an algorithm that uses the suggestion in note 7

Implement the first merging algorithm that was developed.

Design and implement a merging algorithm that reads the data sets from two files of unknown length. Use end-of. file tests to detect the ends of the data sets.

Design and implement a merging algorithm that uses only two arrays. It can be assumed that the sizes of the two data sets are known in advance. An interesting way to do this is to place the array with the biggest element so that it fills up the output (merged) array. The following diagram illustrates the idea (the & array has the largest clement). 1 m @ array nnn (2 b array Output array and temporary storage for b This simplifies the merge because when the merging of a is completed the remaining elements of A will he in place

Design an algorithm for merging three arrays.

In the special case where it is necessary to “merge” two tiles of m and n elements (where m= 1 and n is large) the problem is best solved by binary search. It is also possibic to show that conditions for merging are “best” when m = n. Noting these facts it is possible to implement a merging algorithm that couples a binary search with a normal merging operation in a way that allows the best features of both to be retained. This can be done by imagining that the larger of the two data sets is divided up into blocks equal to the size of the smaller data set. For example, [J ats. <_2> ee ee ee Se 8 re where the blocksize is 2' and ¢= [log, (n/m)|. The merge then starts by moving backwards in steps of size 2' through b[1. .2] until the last element in m is established to be within a given block of size 2'. The last element of a{1..m] can then be merged with the block in ¢ comparisons using a binary search. The process then repeats for a{m~ 1]. Implement this algorithm. (See F, W. Hwang and S. Lin, “A simple algorithm for merging two disjoint linearly ordered data sets”, SEAM J. Computing, 1, 31-39 (1972).)

Sort an array into descending order.

Implement a selection sort that removes duplicates during the sorting process.

Implement an algorithm that incorporates the idea in note 5, and work out the relative number of comparisons it makes.

Count the number of minimum updates the selection sort requires for sorted, reverse order, and random data.

The selection sort can be modified so that it will terminate as soon as it is established that the data set is sorted. This is done by counting the number of times the minimum is updated in each selection pass. It also involves some other changes. Implement this algorithm.

Implement a function that examines an array and returns the Boolean value sorted which is true if the array is in nondescending order and false otherwise.

Use a count of the number of comparisons and exchanges made lo compare the selection sort and bubblesort for random data.

Implement a version of the bubblesort that builds up the sorted airay from sinaliest io largest rather than as in ihe prescui algorithm.

Design and implement an algorithm that incorporates the suggestion in note 4 above.

Design and implement a modified bubblesort that incorporates exchanges in the reverse direction of fixed length.

Try to design a less efficient bubblesort than the present algorithm.

Compare the selection sort and insertion sort for random data, Use the number of moves and the number of comparisons to make the comparative study.

A small saving can be made with the insertion sort by using a method that does other than selection of the next element for insertion. Try to incorporate this suggestion. $4.3. Asaving on both comparisons and moves can be made by inserting more than one element into the ordered part with successive passes. Design such an algorithm that functions by inserting two elements with each pass through the outermost loop.

Save comparisons and moves by inserting two elements into the ordered part during each pass of the outer loop. Design such an algorithm.

The algorithm we have produced takes nu advantage of the fact the elements in positions a[1..i] are ordered. Use a binary search to speed up the location of the insertion position (see

Modify the insertion sort so that itis more balanced, To do this allow insertions at both ends of the array. You may also wish to include an exchange mechanism to speed up the algorithm even further.

The position of the last insertion can be ‘‘remembered” and employed when inserting the next element. Implement a version of the insertion sort that incorporates this idea.

Use a measure of comparisons and moves to compare the shellsort with a standard insertion sort. Use random data for the test.

Compare the performance of shellsort implementations that use respectively the sequence of decrements n/2, n/4, n/8, ..., 1 and 21, ..., 31, 15,7, 3, 1. Use random data sets and use the number of comparisons and moves as a measure.

Imploment a version of shellsort that incorporates a bubblesort in place of the insertion sort. Compare the performance of this implementation with that of the algorithm that incorporates an insertion sort.

Design an algorithm that compares a random and sorted array and establishes the average distance that elements must travel in moving from random to sorted order.

Modify the sheilsort so that the test “previous; is not needed in the innermost while-loop.

A cleaner version of shellsort can be obtained by altering the end from which the insertion is made at each step. This involves a slight modification of the idea suggested in note 5 of

The number of comparisons required by quicksort can be reduced by a few percent by using the median of three elements whenever a new guess at the median is required. A simple way to do this is to always select the median of the first, middle, and end values in the array segment being partitioned. Implement this refinement and compare it with the original version using the number of comparisons as a measure.

It was mentioned earlier (in note 5) that quicksort can be speeded up by using an inseriion suri whenever a segment less Gran about twelve elements needs to be sorted. Incorporate this suggestion.

The suggestion in the previous problem can result in a considerable overhead for the procedure calls to the insertion sort. An alternative and more effective approach is to postpone the insertion sorting until after all partitions have been reduced to a size of less than 12. Implement this version and devise suitable tests to compare it with the 5.6.2 implementation.

A significant saving in comparisons can be made by initially placing the partitioning valuc sclected into the first location of the range to be partitioned and proceeding with the partitioning from the second position. Implement this modification.

Design and implement binary-search versions using (a) while lower < upper + 1 and (b) while lower < upper - 1 as the loop condition.

Implement versions of the binary search that make the following paired changes to lower and upper: (a) lower := middle+1 } upper >= middle~1 | (b) lower := middle \ upper .~ middle }

Implement a binary search algorithm that calculates the middle using | (lower+upper)/2}.

Avariation on the basic binary algorithm involves not centering the algorithm around the /ower and upper limits. Instead, two alternate parameters are maintained, one that points to the middle of the array segment still ta be searched, and a secand marking the half width of that segment. A binary search algorithm that uses this approach is referred to as a uniform binary search. Design and implement a uniform binary search.

Develop an algorithm that uses a random number generator which always generates random numbers in the range lower...upper. in each instance the random number generated should take on the role of middle in the above algorithms. Compare the performance of this algorithm with the binary search algorithm in terms of the number of comparisons made.

Extend the hashing algorithm so that it works with words rather than numbers. One possible word hash is the sum of its letters' collating values; for example, ace has hash value 1 + 3 + 5 = 9.

Modify the hashing algorithm given so that it searches a tabie in which the words have been inserted in alphabetical order (see note 4 above).

it is not always convenient or possible to insert items into a hash table in order as required in the previous problem. An alternative approach that achieves the same effect is to proceed as follows when inserting a new element x. If x hashes to location & and the value there occurs alphabetically later than x, then interchange the roles of x and table[k] and repeat the process until an empty location is found. This has the effect of letting x take precedence in ordering over keys that were inserted earlier but occur alphabetically later.

Implement the linear quotient hashing method described in note 6 and compare its performance with the algorithm above for a load factor of 80%. Use a random number generator to provide the key set. Make tests for sets of both successful and unsuccessful searches.

Make a plot of load factor versus search cost (successful and unsuccessful} for load factors in the range 50% to 95% at 5% intervals (a) using the formulas given in note 1, and (b) by doing a simulation with random numbers.

Use random numbers to fill a table to 80% and do a profile of the number of values that were at their hash position, at their hash position+ 1, at their hash position +2 and so on.

If items are retrieved from a hash table with unequal frequencies a gradual speed-up in retrieval can be obtained by shifting each item as it is retrieved one position closer to its original hash position by performing an exchange. Implement this hash search method.

Modify the algorithm so that it removes multiple blanks other than those at the start of new paragraphs.

The algorithm we have developed may not reproduce the original text if the output was used as input. This would happen because if there was a space at the end of an input line it would be turned into two spaces in the reformatted output. Modify the algorithm so that it overcomes this problem.

Design an algorithm that reads and left justifies lines of text (as required in our algorithm). The beginning of each new paragraph should not be left justified. Note each new paragraph can be assumed to start with an upper case letter and be preceded by multiple blanks.

Design an algorithm that reads lines of text, reformats it and writes it out in pages of two columns (each forty characters wide) separated by a 10-space gap. The first column of the output should correspond to the first half of the input text page and the second colunin to the second half of the input text page. Each output page should contain 40 lines of text.

Implement the first text-formatting design proposed. Try to avoid (he need for shifting word fragments after the current line is printed.

Modify the current algorithm so that while it adheres to the basic template distribution idea, it does not add multiple extra spaces toa location before there has been one extra space added to each location.

Incorporate the suggestion in note 4.

Implement a version of the algorithm that passes the left and right justified line back to the calling procedure.

Include tests in the current algorithm to ensure that the line is not expanded if more than twice the number of existing spaces must be added lo the line.

Design and implement a simpler justification algorithm that does not require the use of a space table.

Design and implement an algorithm that reverses the justification process by removing multiple blanks. Paragraph indentations should be preserved.

Design and implement a left and right justification algorithm that inserts extra spaces after the longest word first, then after the second longest word and so on. In your implementation, by making certain assumptions, try to avoid having tu du a sort. This approach usually produces an aesthetically more pleasing output.

Modify this algorithm so that it will terminate on finding the first coumplieie word-inaich.

Design and implement a word-searching algorithm that on finding a mismatch with the current word simply reads characters to the start of the next word before attempting a match again.

Design and implement an algorithm that searches a text and saves the word that provides the best partial match (other than acomplete match) with the search word.

Design and implement an algorithm that prints a list of all words in the text that contain the search word as a prefix.

Implement a version of the current pattern searching algorithm that counts the number of times a given pattern occurs in a text. Your implementation should accommodate the fact that the search pattern may have repeating subsegments.

Design and implement an algorithm that will remove all occurrences of a particular pattern from a text.

Using English text and patterns determine the average behavior of the pattern searching algorithm in 6.4.1

Try te implement a pattern searching algorithm that has lincar rather than quadratic worst-case behavior.

Given two ordered sets of numbers A and B, determine whether or not the set A is contained within the set B.

Implement an algorithm that prints all patterns that are the same length as the search pattern but which may or may not differ from the pattern by one character.

In many applications, failure to match the first pattern character dominates. Restructure the algorithm to take advantage of this fact.

Try toconstruct a better recovery function based on the observation in note 6.

It is possible to implement a much cleaner and more efficient version of the algorithm that does not need to distinguish between zero-match and partial-match recovery states. To do this, a second table deta nade up of zeroes and ones appropriately placed can be used. The variable position will then be updated using position := position+ delta[match~1] Modify the partial match algorithm so that it appropriately generates the delta table and make changes to the search algorithm so that it takes advantage of the deita table.

Using the ideas present in the linear search algorithm, try to develop a sublinear search algorithm that is dominated by a mechanism that needs to examine only every A" character in the string. The value of k should be considerably less than half the search pattern length. (See T. A. Bailey and R. G, Dromey, “Fast string searching by finding subkeys in subiexi,* inf. Proc. Lens., 11, 130~3 (1980).)

Design a main program that calls the procedure quicksearch. The main program should be able to read and search successive blocks of text.

Test out the above procedure by counting the number of comparisons it has to make for words of various lengths (try lengths of 5, 10, 15).

Modify the procedure quicksearch so that the table indexing on characters is replaced by the use of sets.

A different approach to fast text searching is to step through the text in skips equal to the word length. As soon as we get a mismatch in trying to match the word sought we skip to the start of the next word. To do this it is necessary to build the “skip-to-the-next-word” links into the text. For example, LITHIS 18 ALGSENTENCE TO BE6SKIPOSEARCHED A “0” is used to indicate an end of line. In conducting this preprocessing it is often prudent to skip over small words (which we are usually not interested in searching for}. When words of three characters or Jess are ignored it is only necessary to examine about 10-20% of the text characters in conducting a search. The performance of this new algorithm will therefore frequently compare very favorably with the algorithm we have just developed. Design the necessary preprocessing and searching algorithms.

Another fast text searching algorithm involves stepping through the text and examining only every m" character (where mt is the search pattern length) and then taking appropriate action to confirm the match when text characters are encountered that belong to the pattern. (See C. Lakos and A. Sale, “Is disciplined programming transferrable?”, Aust. Comp. J., 10, 87-93 (1978).} Implement this algorithm.

Implement the main program that supplies data to, and receives data from, the push and pop procedures.

Design and implement a procedure that determines whether the parentheses in a character string representing an arithmetic expression are properly balanced.

Itis sometimes necessary to perform stack operations with variable leneth strings, Imnlement ouch and nop nrocedures that manisulste length strings. Implement pusk and pop procedures that manipulate such strings stored on a stack consisting of a fixed length character array.

Design and implement procedures that maintain two stacks within one array,

Modify the present algorithm so that the mod function is used to keep front and rear within the array bounds. Care should be takenin specifying the array bounds for this implementation (see note 6).

Design and implement queue insertion and deletion algorithms that allow all array elements to be occupied when the queue is full (see note 3).

Choose a queue of initial size n, then use a random number generator to simulate insertions and deletions (¢.g.0<0.5 = addition, 0.5< 1.0 > deletion) and determine what is the minimum array size that will support this queue without causing overflow,

A dequeue is a linear list that allows insertions and deletions al both ends. Implement procedures for maintaining a dequeue.

Implement a queue as a linked linear list such that it only occupies an amount of space proportional to the current queue size. (See algorithms 7.1, 7.3 and 7.4.)

Modify the list searching algorithm so that it will search a list that cannot be assumed to be ordered.

Design a list searching algorithm that incorporates a sentinel (see note 3).

Design andimplementa list searching algorithm that uses arrays for built the uames aud ihe puiniers.

Design and implement an algorithm that accepts as input an ordered list of search names. The task required is to establish and report the absence or presence of these search names in a second much longer ordered list.

Design and implement an algorithm that inserts items on the end of a list. Your algorithm should not have to search the list to perform the insertion.

Design and implement list insertion and deletion algorithms that use arrays to store both the names and the pointers. Unused (either initially unused or deleted) storage should be maintained as a free list. That is, all unused storage should be linked together in a list. When a new item is deleted it is placed on the end of the freelist and when a new item is inserted the space should be taken from the end of the freelist.

Design and implement an algorithm that merges two ordered linked lists.

Design algorithms that search and maintain a linked list by exchanging each retrieved item with its predecessor so that frequently retrieved items gradually migrate toward the front.

Another way of performing the task described in 7.4.4 is to always move an item to the head of the list after it is retrieved. Design and implement algorithms that search and maintain a linked list in this form.

Following the theme of the previous two problems include a frequency of retrieval parameter in each node and only shift an item higher in the list when tt has a higher frequency of retrieval than its predecessor. The retrieval parameter should be kept up to date.

Design and implement an algorithm that performs insertions and deletions on a doubly linked list. Ina doubly linked list each node has two pointers (except at the head and tail), one to its successor and one to its predecessor. (This allows for list traversal in both backward and forward directions.)

Design and implement a tree searching algorithm that uses arrays for the names and the left and right pointer sets.

Implement a tree search algorithm that employs a sentinel as described in note 5. Assume that the tree has been set up so that the sentinel node exists but has not been set.

Design a tree search algorithm that adds one to a counter stored in each node as it is encountered during a search.

Design and implement an algorithm that will search a tree structure that may have more than two nodes emanating from each node. As part of the design it will be necessary to construct a suitable data structure for storing such trees.

Design and implement tree insertion and deletion algorithms that use arrays for the names and left and right pointer sets. A linked free list should be used to keep track of unused storage. You should be able to design your algorithm such that only one procedure is needed to perform the role of the leftsubtree and rightsubtree procedures described above.

Design a tree-deletion algorithm that handles left and right subtrees symmetrically, using a variation of the right-subtree procedure to delete nodes in left subtrees as well.

Another deletion algorithm involves searching the right subtree for its leftmost node. This leftmost node is then moved to the position of the deleted node and the leftmost node is replaced by its right subtree. This rearrangement mechanism is useful because it does not change the average length of the tree. Figure 7.19, in which node (io) is to be deleted, explains the mechanism. Implement this mechanism. rm 6 & 0) * Naat a ° 7 oxi 7 9 13, a ee es wo f “\ Right subtree & Leftmost nade! \_ of leftmost } node 2) Gd) (a) (b) Fig. 7.19 (2) Before deletion; (b} After deletion.

Design and implement an algorithm that will convert a general multiway tree (each node may have more than two successors) to the corresponding ordered binary tree.

Design a non-recursive algorithm for inorder traversal of an ordered binary tree.

Design a recursive procedure for counting the number of nodes in an ordered binary tree.

Design a recursive procedure that counts the number of leaf nodes in an ordered binary tree.

Design and implement recursive tree insertion and tree deletion algorithms.

Design an algorithm that uses an ordered binary tree to sorta set of names. Once the tree has been created, print out the sorted result.

<A binary tree can be traversed without cither directly using a stack or employing recursion, This can be done by traversing the tree in triple order which is defined by the following steps (each node is visited 3 times): Triple order mechanism 1. visit current node 2. traverse its left subtree 3. visit current node 4. traverse its right subtree 5. visit current node, If we ensure each nil pointer is replaced by a reflexive pointer to the node itself the pointer adjustments given below can be used in a simple iterative scheme to traverse the tree in triple order. The algorithm can terminate when current = nil. Pointer adjustments for triple order traversal next := current? left; current} deft v= current} right; current} right := previous: previous := current, Current 7 Next, implement this method of tree traversal (see B. Dwyer, “Simple algorithms for traversing a tree without an auxiliary stack’, Inf. Prac. Letts., 2, 143-5 (1974)). Proc, Letts., 2, 143-5 (1974)).

Implement the two recursive versions of quicksort given and compare the maximum depth of recursion they require for random data.

Compare the execution time differences for the two recursive implementations for: (a) a data set yielding worst-case performance, (b) random data.

Compare the execution time differences for the better recursive and stack implementations of quicksort on your particular computer.

Modify the quicksorr2 algorithm so that it generates a histogram of the frequency of calls made for segment sizes in the range 1 to n. What conclusions can you draw from this profile?

A modified recursive quicksort can be impiememted based on the final partitioning mechanism used in

Implement a recursive algorithm that generates the "U, permutations with unrestricted repetitions in reverse lexical order.

Asit happens in this particular problem, it is possible to construct a simple iterative solution if one adopts the mechanism for converting numbers from base 10 to base r. Try to implement this simple iterative solution to the problem.

Another simple (although not so efficient) way to generate these permutations in lexical order is. to start with the permutations {i, 1,1, ..., 1} The next permutation in each case is generated by scanning the current permutation from right to left until we encounter an element that has not attained its maximum value. This element is incremented by one, and all elements to the right of it are reset to their lowest allowable values and so the process repeats. Implement this algorithm.

Design an algorithm that accepts as input a given permutation of the “U, set and returns as oulpul (a) the permutation that directly precedes it, (b) the permutation that directly follows it in lexical order.

Make a modification to the permutation generation algorithm so that it only prints those permutations that add up to a given value 5. A separate loop to do the summing should not be used.

When our algorithm is used to generate the first 2" binary integers we notice that much of the time more than one binary digit must be changed in going from one integer to the next. Another approach to generating this set (not in lexical order) is to arrange the computation su that undy une binary digit is changed iu going fom one representation to the next. The way this is done is as follows. ‘The digit that must be changed to generate the k" binary representation from the (k~1)" representation is equal to one plus the power of the largest power of 2 that exactly divides k. The algorithm should start with all binary digits set to zero. Implement this algorithm. These representations are called gray codes.

Modify the given algorithm so that it prints out all combinations up to ry ata time in lexical order.

Implement a recursive algorithm that generates the *C, combinations in reverse lexical order.

Design a combination generation algorithm that accepts as input a set of n characters and produces as output all combinations of size r of these characters.

Another simple way to generate combinations in lexical order is to start with the combination {1, 2, 3, ..., r}. The next combination in each case is generated by scanning the current combination from right to left until we encounter an element that has not attained its maximum value. This element is incremented by onc, and all clements to the right of it are set to their lowest allowable values and so the process repeats. Implement this combination generation algorithm and compare its performance with our original algorithm.

Design an algorithm that accepts as input a given combination of the “C, set and returns as output the next combination in lexical order.

In many instances, the algorithm we have produced must change more than one element in going from one combination to the next. Try to design a combination generation algorithm that only needs to make one change in going from one combination to the next. (Ref. P. J. Chase, “Combinations of m out of n objects”, Comm. ACM, 13. 368 (1970).)

Modify the algorithm given to incorporate the improvements suggested in note 3.

Implement a recursive algorithm that generates all n factorial permutations of the first n integers. Use an internal call of the form permutations(n - 1), rather than permutations(k + 1).

Given a permutation of the ten digits, return the next permutation in lexical order; for example, the successor of 7901638542 is 7901642358.

Design a recursive algorithm for generating permutations in lexical order that is based on the mechanism used to solve problem 8.6.3.

Implement the suggestion made in note 8 and compare the number of exchanges for this new implementation with the original and the results from problem 8.6.3.