Algorithms in C++,

Introduction to Algorithm Analysis

Candice R. James

Allied American University

Author Note

This paper was prepared for Algorithm Design and Analysis, Module One Homework, taught by Biswajit Panja.

Directions: Please complete each of the following exercises. Please read the instructions carefully.

For all “short programming assignments,” include source code files in your submission.

1. The following questions refer to the connectivity problem.

a. Explain the difference between the quick-find algorithm and the quick-union algorithm.

Quick find :is an algorithm that places emphasis on finding out if two nodes are connected or not. We can use a typical array to represent a set of nodes and their connections to each other. {1,2,3,4,5};

Indexes of the array are the nodes and the values of the array are the connections. When the value of one index equals that of another node’s value, then the two nodes are connected.

Quick Find approach has a very fast method to check connectivity. To check the connectivity, you just need to access the array twice. However, union is extremely slow. Since whenever you do union, you have to go through all the array, you will end up with O(N) runtime.

The quick find has 3 methods. They are:

    constructor: prepares the set as an array     connected: checks if two nodes are connected or not     union: connects two nodes

Quick Union: Quick union improves greatly in union operation. Instead of going through entire array during union, you attach one node’s root to another’s root.

b. How can maintaining the “weight” of each subtree improve the quick-union algorithm?

During a union operation, the data structure correctly adjusts the size of the root of the merged trees. Therefore, after any union operation, all the tree roots have the correct sizes.

While you are correct that during path compression in the find step that the sizes aren't updated, there is no reason that the data structure would change sizes here. Path compression just reduces the length of the paths from nodes in some tree up to the root of the tree. It doesn't change the number of nodes stored in that tree. Accordingly, the size information at the root of the tree undergoing path compression does not need to change. Although some internal subtrees might lose some children as they are reparented higher up in the tree, this is irrelevant because the union/find structure only needs to maintain size information at the roots of its trees, not at internal nodes.

Overall, this means that the data structure does correctly store size information. There is no adverse impact on runtime, nor is there a need to correct anything.

c. What is path compression and why is it useful?

Generally heuristics by rank and path compression are used to achieve fast disjoint-set data structure operations. Somehow, I find heuristics by weight and path compression more sensible

2. For each of the following connectivity problem data sets, explain whether it describes actual, random, or perverse data.

a. The data is the list 0-1, 1-2, 2-3, 3-4, ..., 99-100.

Data in the above set is perverse.

Because list contains values that are floating point numbers.

So we cannot predict the actual value.

b. The data is generated by rolling a hundred-sided die.

Data in the above set is random.

We get a number in range(1-100)

Because every number in the set has same probability to occur.

c. The data is an encoding of links in a country’s railway system.

Data in the above set is Actual because exact value can be encoded by using some mechanism or algorithm

3. The following refer to O-notation.

a. Suppose f(n) = n2 + 10n + 5. Explain what is meant when we say f(n) is O(n2).

Big O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann–Landau notation (after Edmund Landau and Paul Bachmann),[1][2] or asymptotic notation. In computer science, big O notation is used to classify algorithms[3][4] by how they respond ( e.g., in their processing time or working space requirements) to changes in input size. In analytic number theory, it is used to estimate the "error committed" while replacing the asymptotic size, or asymptotic mean size, of an arithmetical function, by the value, or mean value, it takes at a large finite argument. A famous example is the problem of estimating the remainder term in the prime number theorem.

Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation. The letter O is used because the growth rate of a function is also referred to as order of the function. A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function. Associated with big O notation are several related notations, using the symbols o, ?, ?, and ?, to describe other kinds of bounds on asymptotic growth rates.

b. What is an asymptotic expression?

an asymptotic expansion, asymptotic series or Poincaré expansion (after Henri Poincaré) is a formal series of functions which has the property that truncating the series after a finite number of terms provides an approximation to a given function as the argument of the function tends towards a particular, often infinite, point.

The most common type of asymptotic expansion is a power series in either positive or negative powers. Methods of generating such expansions include the Euler–Maclaurin summation formula and integral transforms such as the Laplace and Mellin transforms. Repeated integration by parts will often lead to an asymptotic expansion.

Since a convergent Taylor series fits the definition of asymptotic expansion as well, the phrase "asymptotic series" usually implies a non-convergent series. Despite non-convergence, the asymptotic expansion is useful when truncated to a finite number of terms. Typically, the best approximation is given when the series is truncated at the smallest term. This way of optimally truncating an asymptotic expansion is known as superasymptotics.[1] The error is then typically of the form where ? is the expansion parameter. The error is thus beyond all orders in the expansion parameter. It is possible to improve on the superasymptotic error, e.g. by employing resummation methods such as Borel resummation to the divergent tail. Such methods are often referred to as hyperasymptotic approximations

4. Solve the recurrence

CN = CN/2 + N, C1 = 0

when N is a power of 2.

C2 = -2C1 / 3 C_n+3 = [ C_n – (n+2)(n+5)*C_n+2 ] / [ 3(n+2)(n+3) ]

For the first independent solution, let C0 = 0. For the second, let C1 = 0. We get y1 = C0 * [ 1 + 1/18 * x^3 – 1/36 * x^4 + 7/540 * x^5 + … ] y2 = C1 * [x – 2/3 * x^2 + 10/27 * x^3 – 17/108 * x^4 + 101/1620 * x^5 + …

5. Consider a sales record book with 1000 pages, one for each customer, in no particular order. Below are algorithms for looking up a customer’s record in the book. For each algorithm, describe the best case, the average case, and the worst case.

a. Start from the first page and work towards the back.

best case: the record to be looked up appears in the very first page of the record book.(eg page 1)

average case: the record to be looked up appears somewhere in the middle of the record book.(eg between 400-600)

worst case: the record to be looked up appears on the last page of the record book.(eg 1000th page)

b. Use dice to generate a number from 1 to 1000, look on that page; repeat as needed.

best case: the record to be looked up is represented by the very first throw of the dice.

average case: the record to be looked up is represented by the dice after a few throws.

worst case: the record to be looked up is never ever represented by the dice or represented after several hundred throws.

image1.png