Algorithms

Course: Diploma Code: 7485 Branch: CS,IT Date: July 2022

Save as PDF

Opens your browser print dialog — select "Save as PDF" to download.

F/2024/7485
Total Pages : 4

Third Semester

Computer Science & Engineering/IT

Scheme OCBC July 2022

ALGORITHMS

Time : Three Hours
Maximum Marks : 70

Note :

  1. Attempt total six questions. Question No. 1 (Objective type) is compulsory. From the remaining questions attempt any five.

    कुल छः प्रश्न हल कीजिए। प्रश्न क्रमांक 1 (वस्तुनिष्ठ प्रकार का) अनिवार्य है। शेष प्रश्नों में से किन्हीं पाँच को हल कीजिए।

  2. In case of any doubt or dispute, the English version question should be treated as final.

    किसी भी प्रकार के संदेह अथवा विवाद की स्थिति में अंग्रेजी भाषा के प्रश्न को अंतिम माना जायेगा।

1.

Choose the correct answer.

सही उत्तर का चयन कीजिए।

2 each

i) What is the best time complexity of bubble sort?

बबल सॉर्ट की बेस्ट टाइम कॉम्पलेक्सिटी क्या है?

(a) 0(n2)

(b) 0(n)

(c) 0(nlogn)

(d) None of the above

ii) Worst case indicates maximum time required for program execution.

प्रोग्राम एक्जीक्यूशन के लिए जरूरी अधिकतम समय निकृष्टतम केस दर्शाता है।

(a) Yes

(b) No

(c) Can be Yes or No

(d) Can not say

iii) A STACK is a ?

एक स्टेक है

(a) FIFO

(b) LIFO

(c) Ordered array

(d) Linear tree

iv) Which compression losses data?

किस कम्प्��ेशन में डाटा लॉस होता है?

(a) Lossy compression

(b) Lossless compression

(c) Both (a) and (b)

(d) None of the above

v) What is the number of edges present in a complete graph having n vertices?

एक कम्पलीट ग्राफ जिसमें n वर्टिसेस है, में उपस्थित एजेस की क्या संख्या होगी?

(a) (n * (n + 1))/2

(b) (n * (n - 1))/2

(c) n

(d) Information given is insufficient

2.

a) What do you understand by data abstraction?

डाटा एब्स्ट्रेक्शन से आप क्या समझते हैं?

2

b) Explain asymptotic and worst case analysis of algorithm.

एल्गोरिथम के एसिम्प्टोटिक और फर्स्ट केस एनालिसिस को समझाइए।

4

c) Explain different types of queues with example.

विभिन्न प्रकार के कय उदाहरण सहित समझाइए।

6
3.

a) Define sorting with example.

सॉर्टिंग को उदाहरण सहित परिभाषित कीजिए।

2

b) Explain the process of Quick Sort.

क्विक सॉर्ट की प्रक्रिया को समझाइए।

4

c) Write an algorithm to perform bubble sort. Also give an example.

बबल सॉर्ट के लिए एक एल्गोरिथम लिखिए। साथ ही उदाहरण भी दीजिए।

6
4.

a) Explain about symbol table.

सिंबल टेबल के बारे में समझाइए।

2

b) What is Hash table? How data is stored in hash table?

हैश ट��बल क्या है? हैश टेबल में डाटा कैसे स्टोर करेंगे?

4

c) Explain the concept of binary search tree with example.

बाइनरी सर्च ट्री के कॉन्सेप्ट को उदाहरण सहित समझाइए।

6
5.

a) What is Graph?

ग्राफ क्या है?

2

b) Define the following term in graph.

ग्राफ में निम्न टर्म को परिभाषित कीजिए।

4
  1. Directed graph
  2. Undirected graph
  3. Directed acyclic graph
  4. Path

c) Explain about minimum spanning tree algorithm.

मिनिमम स्पेनिंग ट्री एल्गोरिथम के बारे में समझाइए।

6
6.

a) Describe about regular expressions.

रेगुलर एक्सप्रेशन के ब��रे में व्याख्या कीजिए।

2

b) What are the applications of data compression?

डाटा कम्प्रेशन की क्या उपयोगितायें हैं?

4

c) Write an algorithm to find substring from a string.

एक स्ट्रिंग से सबस्ट्रिंग प्राप्त करने के लिए एल्गोरिथम लिखिए।

6
7.

a) What is stack?

स्टेक क्या है?

2

b) What are the applications of stack?

स्टेक की क्या उपयोगितायें हैं?

4

c) Sort the following array using insertion sort.

निम्नलिखित ऐरे को इनसर्शन सॉर्ट द्वारा सॉर्ट कीजिए।

6

9, 5, 1, 4, 3.

8.

Write short note on any two of the following:

निम्न में से किसी दो पर संक्षिप्त टिप्पणी लिखिए।

12
  1. Dijkstra's algorithm
  2. Height balance tree
  3. Merge sort
  4. Elementary data compression