<style>@page WordSection1{size: 841.95pt 595.

35pt;mso-page-orientation:
landscape;}div.WordSection1 {page: WordSection1;}</style>
<div class="container">
<div class="col-md-12">
<div class="col-md-8">
<div class="col-md-12" align="center" style="font-size:
22px;font-weight: bold;">
<img
src="https://s3.ap-south-1.amazonaws.com/vmedulife-s3/logo/09-02-2024-LOGO-91-
1707459434.png" width="70" height="70" class="college-logo-for-word">
</div>
<div class="col-md-12" align="center" style="font-size:
22px;font-weight: bold;">
<span class="college-name">Sasurie College of
Engineering</span>
</div>
<div class="col-lg-12 col-md-12 col-sm-12 col-xs-12"
style="text-align:center; font-size: 15px;" id="stream-data">Computer Engineering
[2020-21]</div>
</div>
<div class="col-md-4">
</div>
</div>
</div>
<hr style="margin-top: 0.5%;margin-bottom: 0.5%;">
<!-- Div for displaying basic details like exam name, group etc-->
<div class="container">
<div class="row">
<div class="col-lg-12 col-md-12 col-sm-12 col-xs-12"
align="center" style="font-weight:bold;">
<span style="font-size: 15px;" id="exam-title">Sessional I
Examination</span>
</div>
<div class="col-lg-12 col-md-12 col-sm-12 col-xs-12">
<span style="font-size: 15px;font-weight: 600;">Subject :
</span><span style="font-size: 15px;" id="subject-name">[ SY01T ] Data Structure
&amp; Algorithm - I - Theory</span>&nbsp;&nbsp;
<span style="font-size: 15px;font-weight: 600;">Faculty :
</span><span style="font-size: 15px;" id="faculty">Victoria Browny / Manish Y /
Katherine Pierce / Zayn Somerhalder / Neha Saini / Christopher Jones </span>
<span id="batch-module"></span>

</div>
<div class="col-lg-12 col-md-12 col-sm-12 col-xs-12">
<span style="font-size: 15px;font-weight: 600;">Year :
</span><span style="font-size: 15px;" id="year-data">Second Year - Third
Semester</span>&nbsp;&nbsp;
<span><span style="font-size: 15px;font-weight: 600;">Marks
: </span><span style="font-size: 15px;"
id="exam-marks">30</span></span>&nbsp;&nbsp;
<span><span style="font-size: 15px;font-weight:
600;">Date : </span><span style="font-size: 15px;" id="exam-date">1 August,
2020</span></span>&nbsp;&nbsp;
<span><span style="font-size: 15px;font-weight:
600;">Duration : </span><span style="font-size: 15px;" id="exam-duration">60
Minutes</span></span>
</div>
<div class="col-lg-12 col-md-12 col-sm-12 col-xs-12">
</div>
</div>
</div>
<br>
<div class="container">
<div class="row" id="ques-paper-display-container"><table
id="configuredDataListTable" class="table table-hover table-
bordered"><thead><tr><td></td><td>Marks</td><td>Course Outcome</td><td>Blooms
Level</td><td>Performance Indicator</td></tr></thead><tbody id="140189"><tr><td>
<ol></ol></td><td>0.00</td><td></td><td></td><td></td></tr></tbody><tbody
id="140190"><tr><td>
<ol></ol></td><td>0.00</td><td></td><td></td><td></td></tr><tr><td><p>a) &nbsp;If
all the elements in an input array is equal for example {1,1,1,1,1,1}, What would
be the running time of the Insertion Algorithm?</p>
<ol></ol></td><td>2.00</td><td>SY01T.1</td><td>Remember</td><td>1.1.1, 1.1.2,
1.2.1</td></tr><tr><td><p>b) &nbsp;What operation does the Insertion Sort use to
move numbers from the unsorted section to the sorted section of the list?</p>
<ol></ol></td><td>2.00</td><td>SY01T.2</td><td>Apply</td><td>1.3.1,
2.1.3</td></tr><tr><td><p>c) &nbsp;Which sorting algorithm will take least time
when all elements of input array are identical? Consider typical implementations of
sorting algorithms.</p>
<ol></ol></td><td>2.00</td><td>SY01T.3</td><td>Understand</td><td>2.4.1, 2.4.2,
2.4.4</td></tr><tr><td><p>d) &nbsp;Which sorting algorithms has the lowest worst-
case complexity?</p>
<ol></ol></td><td>2.00</td><td>SY01T.1</td><td>Analyze</td><td>4.1.1, 4.1.2,
4.1.3</td></tr><tr><td><p>e) &nbsp;The concatenation of two list can performed in
O(1) time. What will be the variation of linked list can be used?</p>
<ol></ol></td><td>2.00</td><td>SY01T.2</td><td>Evaluate</td><td>4.1.2,
4.1.3</td></tr><tr><td><p>f) &nbsp;What is the space complexity for deleting a
linked list?</p>
<ol></ol></td><td>2.00</td><td>SY01T.3</td><td>Remember</td><td>4.3.3,
4.3.4</td></tr></tbody><tbody id="140191"><tr><td>
<ol></ol></td><td>0.00</td><td></td><td></td><td></td></tr><tr><td><p>a)
&nbsp;which algorithm has a running time that is least dependent on the initial
ordering of the input?</p>
<ol></ol></td><td>3.00</td><td>SY01T.1</td><td>Understand</td><td></td></
tr><tr><td><p>b) &nbsp;What is the best sorting algorithm to use for the elements
in array are more than 1 million in general?</p>
<ol></ol></td><td>3.00</td><td>SY01T.2</td><td>Apply</td><td></td></
tr><tr><td><p>c) &nbsp;What is the worst case time complexity of the Quick
sort?</p>
<ol></ol></td><td>3.00</td><td>SY01T.3</td><td>Analyze</td><td>1.2.1, 1.4.1,
2.1.1, 2.1.2</td></tr><tr><td><p>d) &nbsp;Which one of the following sorting
algorithm is best suited to sort an array of 1 million elements?</p>
<ol></ol></td><td>3.00</td><td>SY01T.1</td><td>Evaluate</td><td>2.3.2, 2.4.1,
2.4.2</td></tr><tr><td><p>e) &nbsp;Convert the following Infix expression to
Postfix form using a stack x y * z (p * q r) * s, Follow usual precedence rule and
assume that the expression is legal.</p>
<ol></ol></td><td>3.00</td><td>SY01T.2</td><td>Remember</td><td>3.3.2, 3.4.1,
3.4.2</td></tr><tr><td><p>f) &nbsp;What is the type of expression in which operator
succeeds its operands is?</p>
<ol></ol></td><td>3.00</td><td>SY01T.3</td><td>Understand</td><td>2.1.1,
2.1.2</td></tr></tbody><tbody id="140192"><tr><td>
<ol></ol></td><td>0.00</td><td></td><td></td><td></td></tr><tr><td><p>a)
&nbsp;Consider the Quick sort algorithm which sorts elements in ascending order
using the first element as pivot. Then which of the input sequence will require
number of comparisons when this algorithm is applied on it?</p>
<ol></ol></td><td>5.00</td><td>SY01T.1</td><td>Apply</td><td>2.2.4</td></
tr><tr><td><p>b) &nbsp;The given array is arr = {2,6,1}. What are the pivots that
are returned as a result of subsequent partitioning?</p>
<ol></ol></td><td>5.00</td><td>SY01T.2</td><td>Analyze</td><td>4.1.3</td></
tr><tr><td><p>c) &nbsp;Here is an infix expression: 4 3*(6*3-12). Suppose that we
are using the usual stack algorithm to convert the expression from infix to postfix
notation. The maximum number of symbols that will appear on the stack AT ONE TIME
during the conversion of this expression?</p>
<ol></ol></td><td>5.00</td><td>SY01T.3</td><td>Evaluate</td><td>1.2.1,
5.2.1</td></tr></tbody><tbody id="1052533"><tr><td>
<ol></ol></td><td>0.00</td><td></td><td></td><td></td></tr><tr><td><p>If the range
of the function <span id="MathJax-Element-1-Frame" class="mjx-chtml"><span
id="MJXc-Node-21327" class="mjx-math"><span id="MJXc-Node-21328" class="mjx-
mrow"><span id="MJXc-Node-21329" class="mjx-mi"><span class="mjx-char MJXc-TeX-
math-I">f</span></span><span id="MJXc-Node-21330" class="mjx-mo"><span class="mjx-
char MJXc-TeX-main-R">(</span></span><span id="MJXc-Node-21331" class="mjx-
mi"><span class="mjx-char MJXc-TeX-math-I">x</span></span><span id="MJXc-Node-
21332" class="mjx-mo"><span class="mjx-char MJXc-TeX-main-R">)</span></span><span
id="MJXc-Node-21333" class="mjx-mo MJXc-space3"><span class="mjx-char MJXc-TeX-
main-R">=</span></span><span id="MJXc-Node-21334" class="mjx-msqrt MJXc-
space3"><span class="mjx-box"><span class="mjx-surd"><span class="mjx-char MJXc-
TeX-size1-R">√</span></span><span id="MJXc-Node-21335" class="mjx-mrow"><span
id="MJXc-Node-21336" class="mjx-msubsup"><span class="mjx-base"><span id="MJXc-
Node-21337" class="mjx-texatom"><span id="MJXc-Node-21338" class="mjx-mrow"><span
id="MJXc-Node-21339" class="mjx-mi"><span class="mjx-char
MJXc-TeX-math-I">t</span></span><span id="MJXc-Node-21340" class="mjx-mi"><span
class="mjx-char MJXc-TeX-math-I">a</span></span><span id="MJXc-Node-21341"
class="mjx-mi"><span class="mjx-char
MJXc-TeX-math-I">n</span></span></span></span></span><span class="mjx-sup"><span
id="MJXc-Node-21342" class="mjx-texatom"><span id="MJXc-Node-21343" class="mjx-
mrow"><span id="MJXc-Node-21344" class="mjx-mo"><span class="mjx-char MJXc-TeX-
main-R">−</span></span><span id="MJXc-Node-21345" class="mjx-mn"><span class="mjx-
char MJXc-TeX-main-R">1</span></span></span></span></span></span><span id="MJXc-
Node-21346" class="mjx-mi"><span class="mjx-char
MJXc-TeX-math-I">x</span></span><span id="MJXc-Node-21347" class="mjx-mo MJXc-
space2"><span class="mjx-char MJXc-TeX-main-R">+</span></span><span id="MJXc-Node-
21348" class="mjx-mn MJXc-space2"><span class="mjx-char
MJXc-TeX-main-R">1</span></span></span></span></span><span id="MJXc-Node-21349"
class="mjx-mo MJXc-space2"><span class="mjx-char
MJXc-TeX-main-R">+</span></span><span id="MJXc-Node-21350" class="mjx-msqrt MJXc-
space2"><span class="mjx-box"><span class="mjx-surd"><span class="mjx-char MJXc-
TeX-size1-R">√</span></span><span id="MJXc-Node-21351" class="mjx-mrow"><span
id="MJXc-Node-21352" class="mjx-mn"><span class="mjx-char
MJXc-TeX-main-R">1</span></span><span id="MJXc-Node-21353" class="mjx-mo MJXc-
space2"><span class="mjx-char MJXc-TeX-main-R">−</span></span><span id="MJXc-Node-
21354" class="mjx-msubsup MJXc-space2"><span class="mjx-base"><span id="MJXc-Node-
21355" class="mjx-texatom"><span id="MJXc-Node-21356" class="mjx-mrow"><span
id="MJXc-Node-21357" class="mjx-mi"><span class="mjx-char
MJXc-TeX-math-I">t</span></span><span id="MJXc-Node-21358" class="mjx-mi"><span
class="mjx-char MJXc-TeX-math-I">a</span></span><span id="MJXc-Node-21359"
class="mjx-mi"><span class="mjx-char
MJXc-TeX-math-I">n</span></span></span></span></span><span class="mjx-sup"><span
id="MJXc-Node-21360" class="mjx-texatom"><span id="MJXc-Node-21361" class="mjx-
mrow"><span id="MJXc-Node-21362" class="mjx-mo"><span class="mjx-char MJXc-TeX-
main-R">−</span></span><span id="MJXc-Node-21363" class="mjx-mn"><span class="mjx-
char MJXc-TeX-main-R">1</span></span></span></span></span></span><span id="MJXc-
Node-21364" class="mjx-mi"><span class="mjx-char
MJXc-TeX-math-I">x</span></span></span></span></span></span></span></
span>&nbsp;is&nbsp;<span id="MathJax-Element-2-Frame" class="mjx-chtml"><span
id="MJXc-Node-21365" class="mjx-math"><span id="MJXc-Node-21366" class="mjx-
mrow"><span id="MJXc-Node-21367" class="mjx-mo"><span class="mjx-char MJXc-TeX-
main-R">[</span></span><span id="MJXc-Node-21368" class="mjx-mi"><span class="mjx-
char MJXc-TeX-math-I">a</span></span><span id="MJXc-Node-21369" class="mjx-
mo"><span class="mjx-char MJXc-TeX-main-R">,</span></span><span id="MJXc-Node-
21370" class="mjx-mi MJXc-space1"><span class="mjx-char
MJXc-TeX-math-I">b</span></span><span id="MJXc-Node-21371" class="mjx-mo"><span
class="mjx-char MJXc-TeX-main-R">]</span></span></span></span></span>&nbsp;then the
value of&nbsp;<span id="MathJax-Element-3-Frame" class="mjx-chtml"><span id="MJXc-
Node-21372" class="mjx-math"><span id="MJXc-Node-21373" class="mjx-mrow"><span
id="MJXc-Node-21374" class="mjx-mrow"><span id="MJXc-Node-21375" class="mjx-
mo"><span class="mjx-char MJXc-TeX-size2-R">(</span></span><span id="MJXc-Node-
21376" class="mjx-msubsup"><span class="mjx-base"><span id="MJXc-Node-21377"
class="mjx-texatom"><span id="MJXc-Node-21378" class="mjx-mrow"><span id="MJXc-
Node-21379" class="mjx-mi"><span class="mjx-char
MJXc-TeX-math-I">a</span></span></span></span></span><span class="mjx-sup"><span
id="MJXc-Node-21380" class="mjx-texatom"><span id="MJXc-Node-21381" class="mjx-
mrow"><span id="MJXc-Node-21382" class="mjx-mn"><span class="mjx-char MJXc-TeX-
main-R">2</span></span></span></span></span></span><span id="MJXc-Node-21383"
class="mjx-mo MJXc-space2"><span class="mjx-char
MJXc-TeX-main-R">+</span></span><span id="MJXc-Node-21384" class="mjx-msubsup MJXc-
space2"><span class="mjx-base"><span id="MJXc-Node-21385" class="mjx-texatom"><span
id="MJXc-Node-21386" class="mjx-mrow"><span id="MJXc-Node-21387" class="mjx-
mi"><span class="mjx-char
MJXc-TeX-math-I">b</span></span></span></span></span><span class="mjx-sup"><span
id="MJXc-Node-21388" class="mjx-texatom"><span id="MJXc-Node-21389" class="mjx-
mrow"><span id="MJXc-Node-21390" class="mjx-mn"><span class="mjx-char MJXc-TeX-
main-R">2</span></span></span></span></span></span><span id="MJXc-Node-21391"
class="mjx-mo"><span class="mjx-char
MJXc-TeX-size2-R">)</span></span></span></span></span></span>&nbsp;is</p> <ol><li
type="a"><div><span>2</span>&nbsp;&nbsp;<br><span><img src="https://s3.ap-south-
1.amazonaws.com/vmedulife-s3/200/question/1361544/ANS-39885-6592443d178e8.png"
width="100" height="100"></span></div></li><li
type="a"><div><span>3</span>&nbsp;&nbsp;<br><span><img src="https://s3.ap-south-
1.amazonaws.com/vmedulife-s3/200/question/1361544/ANS-39885-6592443d2b96b.png"
width="100" height="100"></span></div></li><li
type="a"><div><span>6</span></div></li><li
type="a"><div><span>5</span></div></li></ol></td><td>1.00</td><td></
td><td>Evaluate,Analyze</td><td></td></tr><tr><td><p>Define Angular</p>
<ol></ol></td><td>0.00</td><td></td><td></td><td></td></tr></tbody></table></div>
</div>