Scribd
Upload
190 views3 pages

Data Structures: Searching & Sorting Algorithms

This document provides information about Assignment 3 for the course BCS-301: Data Structure. It includes 16 mandatory questions and 3 supplementary questions related to searching and sorting algorithms. Students are asked to write algorithms and analyze the time complexity of sequential search, binary search, merge sort, quicksort, heap sort, and other sorting and searching techniques. They are also asked questions involving implementing sorting algorithms like merge sort and quicksort in C programming language.

Uploaded by

ashishsrmcem
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
190 views3 pages

Data Structures: Searching & Sorting Algorithms

This document provides information about Assignment 3 for the course BCS-301: Data Structure. It includes 16 mandatory questions and 3 supplementary questions related to searching and sorting algorithms. Students are asked to write algorithms and analyze the time complexity of sequential search, binary search, merge sort, quicksort, heap sort, and other sorting and searching techniques. They are also asked questions involving implementing sorting algorithms like merge sort and quicksort in C programming language.

Uploaded by

ashishsrmcem
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

B.

TECH - CS
Assignment - 3
Semester-I (Odd), Session: 2023-24
BCS-301: Data Structure
Unit-3 Course Outcome: CO3 – Discuss the
Unit-Name: Searching and Sorting computational efficiency of the sorting and
searching algorithms.
Date of Distribution: __/11/2023 Faculty Name: Dr. Ashish Avasthi, Dr.
Arpita Singh and Mr. Abhishek Tiwari

Sr. MANDATORY QUESTIONS BL


1 Write a short note on sequential search and index sequential search. 1
2 Write down algorithm for the linear/sequential search technique. Give its analysis. 2
3 Write down the algorithm of binary search technique. Write down the complexity of 1
algorithm
4 What is difference between sequential (linear) search and binary search technique? 2
5 What do you mean by hashing and collision? Discuss the advantages and 2
disadvantages of hashing over other searching techniques. Discuss types of hash
functions.
6 Write the conditions when collision occurs in hashing. Describe any collision 2
detection algorithm in brief.
7 Describe two way merge sort method. Explain the complexities of merge sort 2
method.
8 What is quick sort ? Sort the given values using quick sort; present all 3
steps/iterations : 38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72
9 Write an algorithm for merge sorting. Using the algorithm sort in ascending order : 3
10, 25, 16, 5, 35, 48, 8
10 How do you calculate the complexity of sorting algorithms ? Also, write a recursive 4
function in ‘C’ to implement the merge sort on given set of integers.
11 Write algorithm for quick sort. Trace your algorithm on the following data to sort the 4
list: 2, 13, 4, 21, 7, 56, 51, 85, 59, 1, 9, 10. How the choice of pivot elements affects
the efficiency of algorithm.
12 Explain radix sort. 1
13 Write short notes on garbage collection. 1
14 Use quick sort algorithm to sort 15, 22, 30, 10, 15, 64, 1, 3, 9, 2. Is it a stable sorting 3
algorithm? Justify.
15 Write a short note on heap sort. 1
16 Write a recursive quick sort algorithm. 1
SUPPLEMENTARY QUESTIONS
1 An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot 4
element is chosen uniformly at random. The probability that the pivot element gets
placed in the worst possible location in the first round of partitioning (rounded off to 2
decimal places) is ______.
2 What is the worst case running times of Insertion sort, Merge sort and Quick sort. 4
3 Consider the following array of elements. 5
〈89,19,50,17,12,15,2,5,7,11,6,9,100〉
What is the minimum number of interchanges needed to convert it into a max-heap?

IQAC/ASU/F/2023-24/2.1 Page 1 of
2

REFERENCES

TEXT BOOKS:
Ref. Authors Book Title Publisher/Press Edition &Year of
[ID] Publication
Computer Concepts and
[T1] [Link] McGraw Hill 5th 2016
Programming in C
[T2] Y.P. Kanetkar Let Us C By BPB Publication 5th 2018
REF ERENCE BOOKS:
Ref. Edition &Year of
Authors Book Title Publisher/Press
[ID] Publication
Computer Fundamentals
[R1] Reema Thareja Oxford Publication 2015
and Programming in C.
Computer Basics and C PHI Learning Pvt.
[R2] [Link] 2015
Programming Limited
ONL INE/DIGITALREFERENCES:
Ref.
Source Name Source Hyperlink
[ID]
C Tutorial
[D1] [Link]
([Link])

Signature of Faculty:______________ Signature of


HOD:_______________
(With Date) (With Date)
IQAC/ASU/F/2023-24/2.1 Page 2 of 2

You might also like