Give three advantages of chaining over open addressing (for hash tables), using

Question

Give three advantages of chaining over open addressing (for hash tables), using generic functions.

• Give one advantage of using postfix rather than infix notation for mathematical expressions.

• Give one advantage of using infix rather than postfix notation for mathematical expressions.

• In a circular array with size N, which element follows the element numbered i?

• Estimate T1/T2 where T1 is the run time of heap sort and T2 is the run time of selection sort, and both sorting methods are applied to 1000 data items. Give your answer as a real number.

• Estimate T1/T2 where T1 is the run time of heap sort and T2 is the run time of selection sort, and both sorting methods are applied to 109 data items. Give your answer as a real number.

Explanation / Answer

A. Hash tables resolve collisions through two mechanisms,

1. separate chaining or open hashing and 2. open addressing or closed hashing.

Though the first method uses lists in hash table to maintain more than one entry having same hash values, the other uses complex ways of skipping n elements on collsion.

Since, while searching, both mechanisms requires looking up for more entries on collision and Seperate chaining may require lesser number of searches to find the match.

B. Advantages of using postfix rather that infix

The compiler scans the expression either from left to right or from right to left.

Consider the below expression: a op1 b op2 c op3 d
If op1 = +, op2 = *, op3 = +

The compiler first scans the expression to evaluate the expression b * c, then again scan the expression to add a to it. The result is then added to d after another scan.

The repeated scanning makes it very in-efficient. It is better to convert the expression to postfix(or prefix) form before evaluation.

Advantages: 1. less overhead of brackets.
2. We can easily evaluate a postfix expression in a single scan from left to right with the help of a stack, unlike evaluating infix expressions.

C. Advantages of Infix expression over postfix.
It is better to understand for us if we use infix expressions.
Suppose if we want to write a simple expression (3×4)+2 in the postfix notation it is 3 4 * 2 +. Postfix notation is easier to implement, but infix notation is easier to understand during debugging a code.

D. The i'th element in the circular array can be given as i = (i + 1) % N where N = the number of indices where % is the remainder operation.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.