Data Structures (ASSIGNMENT-1)

2/4 B.Tech (CSE)

Answer the following questions and submit it to your faculty member on or before August 31, 2010. You have to show the execution for the first 8 questions.

1.  Implement an optimized version of quick sort and experiment with combinations of the following:

          Pivot:  First Element, Middle Element, Random Element, Median of three, Median of five.

2.  A sorting algorithm is stable if elements with equal keys are left in the same order as they occur in the input. Which of the following sorting algorithms are stable and why?

a) Bubble Sort               b) Insertion Sort        c) Selection Sort              d) Merge Sort        e) Quick Sort

3.  Implement the merge sort without using recursion. Determine the running time of Merge Sort for

                    a) Sorted Input                     b) Reverse – Ordered Input            c) Random - Input

4. Write a program to reverse a singly linked list in O(n) time using constant extra space.

5. Write a linked list implementation of self-adjusting lists. A self adjusting list is like a regular list, except  that all insertions are performed at the front ,and when an element is accessed by a find ,it is moved  to the front of the list without changing the relative order of the  other items.

6. Given two sorted lists L1 and L2,

          a) Write a procedure to compute union of L1 and L2.

           b) Write a procedure to compute intersection of L1 and L2.

7.           a) Write a program to convert an infix expression  which includes  ‘(‘         ‘)’   ‘+’   ‘-‘   ‘*’                  and ‘/’ to Postfix.

           b) Write a program to convert a postfix expression to infix.

8. Write a routine that reads in two alphabetized files and merges them together forming a third, alphabetized file.

9.  Explain about any 4 Data representation methods and give its applications.

10. Prove that any comparison –based sorting algorithm requires   Ω(nlogn) comparisons on average.