WOKAS blogger

The file HashInt.txt (in a separate file) contains 100,000 integers all randomly chosen between 1 and 1,000,000 (there might be some repetitions).This is considered as an array of integers where the ith row of the file gives you the ith entry of the array. Given below are 9 "target sums", in increasing order: 231552, 234756, 596873, 648219, 726312, 981237, 988331, 1277361, 1283379. You are required to implement the hash table-based algorithm and determine, for each of the 9 target sums x, whether or not x can be formed as the sum of two entries in the given array. Your answer should be in the form of a 9-bit string, with a 1 indicating "yes" for the corresponding target sum and 0 indicating "no". For example, if you discover that all of the target sums except for the 5th and the 7th one (i.e., except for 726312 and 988331) can be formed from pairs from the input file, then your answer should be "111101011" (without the quotes). The answer sho

The greedy algorithm always adopts the best solution at the given time, with no regard for how that choice will affect to future choices. Using a greedy algorithm generally indicates that the implementer hopes that the series of “best” local choices made will lead to a final “best” choice. If so, that the algorithm has produced an optimal solution. If not sub optimal solution has been found. This coin changing problem is following a greedy algorithm strategy. Let’s say some one buy some items at the store and change from his purchase is 103. This 103 can give minimum units of denominators of that particular country. To solve such kind of problems we can use greedy strategy, 100’s > 1, 2’s > 1, 1’s > 1. That is the smallest number of units of coins that will equal to 103. It has been proven that optimal solutions for coin changing can always current denominations of coins. However if we introduce some other denomination to the mix, the greedy algorithm doesn’t produce an