CS502 GDB 1 Solution Fall 2022
CS502 GDB 1 Solution Fall 2022: Today we are sharing with your the Design and analysis of Algorithm (CS502) GDB Solution 2022.
Computational Model
Most contemporary (nonparallel) machines’ processing capacity appears to be well captured by this approach. Some components, including efficiency because of the locality of reference, which was discussed in the prior lecture, are not modeled. Beware of some “loopholes” (or covert methods of breaking the law). The concept, for instance, would enable the constant-time addition of two numbers with a billion digits. Theoretically, it is thus conceivable to arrive at absurd conclusions in the form of effective RAM programmers that cannot be effectively implemented on any system. The RAM model has, however, done a reasonable job of simulating conventional machine technology since the early 1960s and appears to be pretty sound.
Let’s run through an example to show how we evaluate algorithms. You want to choose the fastest vehicle. But pricey fast automobiles are not what you want. You are unable to choose between speed and cost. If there is another vehicle that is both faster and less expensive, you should not want a car. In terms of your selection criteria, we say that the fast, inexpensive automobile outperforms the sluggish, expensive car. So, given a group of vehicles, we wish to list those that are not controlled by any other vehicle.
Our mathematical analysis’s primary goal will be to gauge the execution time. The amount of space (memory) needed by the method will also be a consideration. The speed of the machine, the programming language, compiler optimization, and other factors will all affect how quickly an algorithm is implemented. We won’t include these technological difficulties in our analysis, despite their significance. We may count the steps of the pseudo-code that are executed, the number of times an element of P is accessed, or the number of comparisons that are carried out in order to calculate the running time of the brute-force 2-d maximum algorithm.
Iteration is an extremely effective method for recurring problems. However, it is simple to lose track of what is happening amid all the symbolic manipulations. Here is an excellent illustration of how iteration works. Any recurrence can be explained in terms of a tree, where each extension of the recurrence advances us by a level.
This method is being introduced because it exemplifies a crucial special instance of divide-and-conquer, which I refer to as the sieving technique. Divide-and-conquer is the process of splitting a large problem into a few smaller sub-problems, which are then solved recursively. The sieve technique is an exception, where there are only a few sub-problems.
Sorting will be the topic of the upcoming lectures. There are several justifications for sorting. Here are a few significant examples. Many sizable software systems include sorting techniques. To make these systems as efficient as possible, effective sorting algorithms must be created.
Three faster algorithms that don’t use comparisons will be discussed. The numbers to be sorted are assumed to be in the range of 1 to k, where k is a small number. To rate each integer in the final sorted array is the essential notion. Remember that the amount of components that are either fewer than or equal to an item determines its rank. We just copy the numbers to their ultimate position in an output array once we are aware of the ranks.
