Page 237 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 5. Write methods to implement queues in a circular array with one unused entry in the array.
That is, we consider that the array is full when the rear is two positions before the front;
when the rear is one position before, it will always indicate an empty queue.
6. Prove that “The binomial tree of order k, B , contains 2 nodes. extbfProof (By induction).
k
k
Let n be the number of nodes in B , a binomial tree of order k.”
k k
7. Write a menu driven demonstration program for manipulating a deque of characters,
similar to the Extended_queue demonstration program.

8. Write the class definition and the method implementations needed to implement a deque
in a linear array.
9. Write the methods needed to implement a deque in a circular array. Consider the class
Deque as derived from the class Queue.
10. Write a method to implement queues, where the implementation does not keep a count of
the entries in the queue but instead uses the special conditions

rear = −1 and front = 0
to indicate an empty queue.

Answers: Self Assessment

1. fores 2. null path length 3. zero 4. right
5. enqueue 6. fi ndMin 7. Sleator and Tarjan

8. binomial tree
11.8 Further Readings

Books Brian W. Kernighan and Dennis M. Ritchie, The C Programming Language, Prentice
Hall, 1988.
Burkhard Monien, Data Structures and Effi cient Algorithms, Thomas Ottmann,
Springer.
Kruse, Data Structure & Program Design, Prentice Hall of India, New Delhi.
Mark Allen Weles, Data Structure & Algorithm Analysis in C, Second Ed., Addison-
Wesley Publishing.
RG Dromey, How to Solve it by Computer, Cambridge University Press.
Shi-Kuo Chang, Data Structures and Algorithms, World Scientifi c.
Shi-kuo Chang, Data Structures and Algorithms, World Scientifi c.
Sorenson and Tremblay, An Introduction to Data Structure with Algorithms.
Thomas H. Cormen, Charles E, Leiserson & Ronald L., Rivest: Introduction to
Algorithms, Prentice-Hall of India Pvt. Limited, New Delhi.
Timothy A. Budd, Classic Data Structures in C++, Addison Wesley.

Online links www.en.wikipedia.org
www.web-source.net
www.webopedia.com

232 LOVELY PROFESSIONAL UNIVERSITY