
The ________ given by DFS allow us to determine whether the graph contains any cycles. CS502
Order
Time stamps Page 130
BFS traversing
Topological sort
e6ac3d19c36b4817855d57b85e421b68image.png
8.1.5 DFS  Cycles
The time stamps given by DFS allow us to determine a number of things about a graph or digraph.
For example, we can determine whether the graph contains any cycles. We do this with the help of the following two lemmas. 
► Optimal
► Nonoptimal
► Exponential
► Polynomial 
In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs.

Consider that a tourist wants to travel between Karachi and Hunza cities in minimum possible span. The road map available has marked distance between each pair of adjacent cities. The time available to the tourist has limited and he/she require to find the shortest possible route between Karachi and Hunza.
In the given scenario, the possible solution may be adopted from the following set of algorithms.
Bellman ford’s Algorithm Flyod Warshal’s Algorithm Dijkstra's Algorithm Breadthfirstsearch algorithmYou are required to select the possible and most reasonable algorithm for the given scenario. Support you answer with solid reasons.

Assignment No. 03
SEMESTER Fall 2019
CS502 Fundamentals of Algorithms
Total Marks: 20Due Date: 15/01/2020
Instructions
Please read the following instructions carefully before solving & submitting assignment:
It should be clear that your assignment will not get any credit if:
• The assignment is submitted after due date.
• The submitted assignment does not open or file corrupt.
• The assignment is fully or partially copied from (other student or ditto copy from handouts or internet).
• Student ID is not mentioned in the assignment File or name of file is other than student ID.
• The assignment is not submitted in .doc or .docx format.
Uploading instructions
Your submission must include:• Assignment should be in .doc or .docx format.
• Save your assignment with your ID (e.g. bx180200786.doc).
Assignment submission through email is NOT acceptable
Objective
The objective of this assignment is
• To give basic knowledge and understanding of Graphs.
• To develop the understanding between adjacency list and adjacency matrix representations.Note:
Your answer must follow the below given specifications.
• Font style: “Times New Roman”
• Font color: “Black”
• Font size: “12”
• Bold for heading only.
• Font in Italic is not allowed at all.
• No formatting or bullets are allowed to use.
• Your answer should be precise and to the point, avoid irrelevant detail.Lectures Covered: This assignment covers Lecture # 28
Deadline
Your assignment must be uploaded/submitted at or before 15/01/2020.Assignment Statement:
Everywhere we see objects and some sort of interaction between them. If we are needed to model this connection or relationship between them, the graphs is a good way to model it.
A graph G = (V, E) consists of a finite set of vertices V (or nodes) and E, a binary relation on V called edges. E is a set of pairs from V. If a pair is ordered, we have a directed graph. For unordered pair, we have an undirected graph.
There are two ways of representing graphs: using an adjacency matrix and using an adjacency list.Question No 01: (Marks: 10)
Draw an undirected Graph for the following Adjacency list representation as given below,
e5754efcb6bf49758417d71e6c4945d6image.png
Question No 02: (Marks: 10)
Draw a directed graph for the following matrix format representation,
15a35cf7f143437f897d7c03d0cd4980image.png=====================================Ended=======================================
For any query about the assignment, contact at [email protected]
GOOD LUCK

Assignment No. 02
SEMESTER Fall 2019
CS502 Fundamentals of Algorithms
Total Marks: 20Due Date: 27/11/2019
Instructions
Please read the following instructions carefully before solving & submitting assignment:
It should be clear that your assignment will not get any credit if:
• The assignment is submitted after due date.
• The submitted assignment does not open or file corrupt.
• The assignment is full or partially copied from (other student or ditto copy from handouts or internet).
• Student ID is not mentioned in the assignment File or name of file is other than student ID.
• The assignment is not submitted in .doc or .docx format.
Uploading instructions
Your submission must include:• Assignment should be in .doc or .docx format.
• Save your assignment with your ID (e.g. bx180200786.doc).
Assignment submission through email is NOT acceptable
Objective
The objective of this assignment is
• To give basic knowledge and understanding of Algorithms.
• To be able to design sorting algorithms.
• To be able to understand and calculate the complexity of algorithms.Note:
Your answer must follow the below given specifications.
• Font style: “Times New Roman”
• Font color: “Black”
• Font size: “12”
• Bold for heading only.
• Font in Italic is not allowed at all.
• No formatting or bullets are allowed to use.
• Your answer should be precise and to the point, avoid irrelevant detail.Lectures Covered: This assignment covers Lecture # 09  14
Deadline
Your assignment must be uploaded/submitted at or before 27/11/2019.Assignment diagram:
0e4a496cd9364a99ac0c2e198ae8fc43image.png
Consider the given diagram having an unsorted array and its sorting procedure through dry run. You are required to answer the following questions.Question No 01: (Marks: 5)
You are required to determine (write down the name) the algorithm being used while sorting the above given array.Question No 02: (Marks: 7)
You are required to design (write) the algorithm (Only Pseudo code) determined in Question 1.Question No 03: (Marks: 😎
You are required to calculate (Step by Step) the worst case time complexity T(n) of the algorithm designed in Question No. 02.=====================================Ended=======================================
For any query about the assignment, contact at [email protected]
GOOD LUCK


Assignment No. 01 SEMESTER Fall 2019
CS502 Fundamentals of Algorithms
Total Marks: 20Due Date: 13/11/2019
Instructions
Please read the following instructions carefully before solving & submitting assignment:
It should be clear that your assignment will not get any credit if:
• The assignment is submitted after due date.
• The submitted assignment does not open or file corrupt.
• The assignment is full or partially copied from (other student or ditto copy from handouts or internet).
• Student ID is not mentioned in the assignment File or name of file is other than student ID.
• The assignment is not submitted in .doc or .docx format.
Uploading instructions
Your submission must include:• Assignment should be in .doc or .docx format.
• Save your assignment with your ID (e.g. bx180200786.doc).
Assignment submission through email is NOT acceptable
Objective
The objective of this assignment is
• To give basic knowledge and understanding of Algorithms.
• To be able to design simple algorithms.
• To be able to understand and calculate the complexity of algorithms.Note:
Your answer must follow the below given specifications.
• Font style: “Times New Roman”
• Font color: “Black”
• Font size: “12”
• Bold for heading only.
• Font in Italic is not allowed at all.
• No formatting or bullets are allowed to use.
• Your answer should be precise and to the point, avoid irrelevant detail.Lectures Covered: This assignment covers Lecture # 01  06
Deadline
Your assignment must be uploaded/submitted at or before 13/11/2019.Assignment Statement:
In mathematics Prime is a number which can be only divisible by 1 and itself. Examples of prime numbers are, 1 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 etc. When these numbers get large, then it is very difficult to manually identify them as to be prime or not prime. For example the numbers like, 443 and 44371 cannot easily identify as Prime.
There may be many algorithms which can be written for the identification of a number to be prime or not prime.Question No 01: (Marks: 10)
You are required to design (write) a simple algorithm (Only Pseudo code) which can identify a number to be Prime or Not Prime.Question No 02: (Marks: 10)
You are required to calculate (Step by Step) the worst case time complexity T(n) of the algorithm designed in Question No. 01.=====================================Ended=======================================
For any query about the assignment, contact at [email protected]
GOOD LUCK

CS502 Midterm Solved Papers Mid and Final

Please share your current paper

Current CS502 Paper MidFall2019
Cs502 Divide and conquer (3) Catalan number(5) Chain matrix multiple cation (5) Bubble sort(5) Property of algorithms (3) McQ from handout CS502 Today's Mid Term Paper MCQ's Mostly from pastpers 2 qs marks 3 and 3 qs marks 5 1.Sorting and write its types..5 marks 2. Counting sort numbers are given.. 5 marks 3.Any Program.. i don't know this qs..5 marks 4. Edit Transcript.. 3 marks 5. Upper bound and lower bound

CS502 Fundamentals of Algorithms Solved MCQS From Midterm Papers
Question No: 1 ( Marks: 1 )  Please choose one Due to left complete nature of binary tree, the heap can be stored in
► Arrays (Page 40)
► Structures
► Link Lis
►Stack
Question No: 1 ( Marks: 1 )  Please choose one What type of instructions Random Access Machine (RAM) can execute?
►Algebraic and logic
►Geometric and arithmetic
►Arithmetic and logic (Page 10)
►Parallel and recursive
Question No: 1 ( Marks: 1 )  Please choose one For Chain Matrix Multiplication we can not use divide and conquer approach because,
►We do not know the optimum k (Page 86)
►We use divide and conquer for sorting only
►We can easily perform it in linear time
►Size of data is not given
Question No: 1 ( Marks: 1 )  Please choose one What is the total time to heapify?
► Ο(log n) (Page 43)
► Ο(n log n)
► Ο(n2 log n)
► Ο(log2 n)
1
Question No: 1 ( Marks: 1 )  Please choose one word Algorithm comes from the name of the muslim author ____________
►Abu Ja’far Mohammad ibn Musa alKhowarizmi.
Question No: 1 ( Marks: 1 )  Please choose one alKhwarizmi’s work was written in a book titled _______________
►al Kitab almukhatasar fi hisab aljabr wa’lmuqabalah
MIDTERM EXAMINATION Spring 2010 CS502 Fundamentals of Algorithms
Question No: 1 ( Marks: 1 )  Please choose one Random access machine or RAM is a/an
► Machine build by AlKhwarizmi
► Mechanical machine
► Electronics machine
► Mathematical model (Page 10)
Question No: 2 ( Marks: 1 )  Please choose one _______________ is a graphical representation of an algorithm
► Σnotation► Θ
notation► Flowchart Click here for detail
► Asymptotic notation
Question No: 3 ( Marks: 1 )  Please choose one A RAM is an idealized machine with ______________ randomaccess memory.
► 256MB
► 512MB
► an infinitely large (Page 10)
► 100GB
2
Question No: 4 ( Marks: 1 )  Please choose one What type of instructions Random Access Machine (RAM) can execute? Choose best answer
► Algebraic and logic
► Geometric and arithmetic
► Arithmetic and logic (Rep)
► Parallel and recursive
Question No: 5 ( Marks: 1 )  Please choose one What will be the total number of max comparisons if we run bruteforce maxima algorithm with n elements?
► n2n► ► n2n(Page 14)
►
n 8Question No: 6 ( Marks: 1 )  Please choose one What is the solution to the recurrence T(n) = T(n/2)+n .
► O(logn)
► O(n) (Page 37)
► O(nlogn)
► O(n2)
Question No: 7 ( Marks: 1 )  Please choose one Consider the following code:
For(j=1; j<n;j++)
For(k=1; k<15;k++)
For(l=5; l<n; l++) {
Do_something_constant(); } What is the order of execution for this code.
► O(n)
► O(n3)
► O(n2 log n)
► O(n2)
Question No: 8 ( Marks: 1 )  Please choose one What is the total time to heapify?
► Ο(log n) rep
► Ο(n log n)
► Ο(n2 log n)
► Ο(log2 n)
3
Question No: 9 ( Marks: 1 )  Please choose one Consider the following Algorithm: Factorial (n){
if (n=1)
return 1 else
return (n * Factorial(n1)) {
Recurrence for the following algorithm is:
► T(n) = T(n1) +1
► T(n) = nT(n1) +1
► T(n)= T(n1) +n
► T(n)=T(n(n1)) +1
Question No: 10 ( Marks: 1 )  Please choose one
When we call heapify then at each level the comparison performed takes time
► It will take Θ (1) (Page 43)
► Time will vary according to the nature of input data
► It can not be predicted
► It will take Θ (log n)
Question No: 11 ( Marks: 1 )  Please choose one In Quick sort, we don’t have the control over the sizes of recursive calls
► True (Page 40)
► False
► Less information to decide
► Either true or false
Question No: 12 ( Marks: 1 )  Please choose one Is it possible to sort without making comparisons?
► Yes (Page 57)
► No
Question No: 13 ( Marks: 1 )  Please choose one If there are Θ (n2) entries in edit distance matrix then the total running time is
► Θ (1)
► Θ (n2) Click here for detail
► Θ (n)
► Θ (n log n)
4
Question No: 14 ( Marks: 1 )  Please choose one For Chain Matrix Multiplication we can not use divide and conquer approach because,
► We do not know the optimum k (Page 86)
► We use divide and conquer for sorting only
► We can easily perform it in linear time
► Size of data is not given
Question No: 15 ( Marks: 1 )  Please choose one The Knapsack problem belongs to the domain of _______________ problems.
► Optimization (Page 91)
► NP Complete
► Linear Solution
► Sorting
Question No: 16 ( Marks: 1 )  Please choose one Suppose we have three items as shown in the following table, and suppose the capacity of the knapsack is 50 i.e. W = 50.
Item Value Weight 1 60 10 2 100 20 3 120 30 The optimal solution is to pick
► Items 1 and 2
► Items 1 and 3
► Items 2 and 3 (correct)
► None of these
5
MIDTERM EXAMINATION Spring 2010 CS502 Fundamentals of Algorithms
Question No: 1 ( Marks: 1 )  Please choose one For the Sieve Technique we take time
► T(nk) (Page 34)
►T(n / 3)
►n^2
►n/3
Question No: 1 ( Marks: 1 )  Please choose one Sieve Technique applies to problems where we are interested in finding a single item from a larger set of _____________ Select correct option:
►n items (Page 34)
►phases
►pointers
►constant
Question No: 1 ( Marks: 1 )  Please choose one ______________ graphical representation of algorithm.
►asymptotic
►Flowchart (rep)
Question No: 1 ( Marks: 1 )  Please choose one who invented the quick sort
►C.A.R. Hoare Click here for detail
Question No: 1 ( Marks: 1 )  Please choose one main elements to a divideandconquer
►Divide, conquer, combine (Page 27)
Question No: 1 ( Marks: 1 )  Please choose one Mergesort is a stable algorithm but not an inplace algorithm.
►True (Page 54)
►false
6
Question No: 1 ( Marks: 1 )  Please choose one Counting sort the numbers to be sorted are in the range 1 to k where k is small.
►True (Page 57)
►False
MIDTERM EXAMINATION Spring 2007 CS502 Fundamentals of Algorithms
Question No: 1 ( Marks: 1 )  Please choose one Total time for heapify is:
►Ο (log2 n)
►Ο (n log n)
►Ο (n2 log n)
►Ο (log n) Rep
Question No: 1 ( Marks: 1 )  Please choose one If an algorithm has a complexity of log 2 n + nlog 2 n + n. we could say that it has complexity
►O(n)
►O( n log2 n)
►O(3)
►O( log2 ( log2 n ))
►O ( log2 n)
Question No: 1 ( Marks: 1 )  Please choose one In RAM model instructions are executed
►One after another (Page 10)
►Parallel
►Concurrent
►Random
7
Question No: 1 ( Marks: 1 )  Please choose one In selection algorithm, because we eliminate a constant fraction of the array with each phase, we get the
►Convergent geometric series (Page 37)
►Divergent geometric series
►None of these
Question No: 1 ( Marks: 1 )  Please choose one Due to leftcomplete nature of binary tree, heaps can be stored in
►Link list
►Structure
►Array (Page 40)
►None of above
CS609 System Programming Midterm Quizzes (Quiz No.1 & 2)
Quiz No.1 (04 – MAY  2013)
Question No: 1 ( Marks: 1 )  Please choose one The time assumed for each basic operation to execute on RAM model of computation is
Infinite Continuous Constant (Page 10) Variable
Question No: 1 ( Marks: 1 )  Please choose one If the indices passed to merge sort algorithm are not equal, the algorithm may return immediately.
True False (Page 28)
Question No: 1 ( Marks: 1 )  Please choose one Bruteforce algorithm uses no intelligence in pruning out decisions.
True (Page 18) False
8
Question No: 1 ( Marks: 1 )  Please choose one In analysis, the Upper Bound means the function grows asymptotically no faster than its largest term.
True (Page 24) False
Question No: 1 ( Marks: 1 )  Please choose one For small values of n, any algorithm is fast enough. Running time does become an issue when n gets large.
True (Page 14) Fast
Question No: 1 ( Marks: 1 )  Please choose one The array to be sorted is not passed as argument to the merge sort algorithm.
True False
Question No: 1 ( Marks: 1 )  Please choose one In simple bruteforce algorithm, we give no thought to efficiency.
True (Page 11) False
Question No: 1 ( Marks: 1 )  Please choose one The ancient Roman politicians understood an important principle of good algorithm design that is plansweep algorithm.
True False (Page 27) [Divide and Conquer]
Question No: 1 ( Marks: 1 )  Please choose one In 2dspace a point is said to be if it is not dominated by any other point in that space.
Member Minimal Maximal (Page 11) Joint
Question No: 1 ( Marks: 1 )  Please choose one An algorithm is a mathematical entity that is dependent on a specific programming language.
True False (Page 7)
9
Question No: 1 ( Marks: 1 )  Please choose one The running time of an algorithm would not depend upon the optimization by the compiler but that of an implementation of the algorithm would depend on it.
True (Page 13) False
Question No: 1 ( Marks: 1 )  Please choose one F (n) and g (n) are asymptotically equivalent. This means that they have essentially the same __________ for large n.
Results Variables Size Growth rates (Page 23)
Question No: 1 ( Marks: 1 )  Please choose one 8n2 + 2n  3 will eventually exceed c2*(n) no matter how large we make c2.
True (Page 25) False
Question No: 1 ( Marks: 1 )  Please choose one If we associate (x, y) integers pair to cars where x is the speed of the car and y is the negation of the price. High y value for a car means a ________ car.
Fast Slow Expensive Cheap (Page 11)
Question No: 1 ( Marks: 1 )  Please choose one The function f(n)= n(logn+1)/2 is asymptotically equivalent to n log n. Here Upper Bound means the function f(n) grows asymptotically ____________ faster than n log n.
More Quiet Not (Page 24) At least
Question No: 1 ( Marks: 1 )  Please choose one After sorting in merge sort algorithm, merging process is invoked. Select correct option:
True (Page 28) False
10
Question No: 1 (Marks: 1)  Please choose one Asymptotic growth rate of the function is taken over_ case running time. Select correct option:
Best Average Worst (Page 14) Normal
Question No: 1 (Marks: 1)  Please choose one In analysis of f (n) =n (n/5) +n10 log n, f (n) is asymptotically equivalent to ________.
n 2n n+1 n2 (Page 23)
Question No: 1 (Marks: 1 )  Please choose one Algorithm is concerned with…issues.
Macro Micro Both Macro & Micro (Page Normal
Question No: 1 (Marks: 1)  Please choose one We cannot make any significant improvement in the running time which is better than that of bruteforce algorithm.
True False (Page 18)
Question No: 1 ( Marks: 1 )  Please choose one In addition to passing in the array itself to Merge Sort algorithm, we will pass in _________other arguments which are indices.
Two (Page 28) Three Four Five
Question No: 1 ( Marks: 1 )  Please choose one Consider the following Algorithm: Fun(n){ if (n=1) return 1 else return (n * Fun(n1)) } Recurrence for the above algorithm is:
11
nT(n1)+1 2T(n1)+1 T(n1)+cn T(n1)+1
Question No: 1 ( Marks: 1 )  Please choose one In analysis, the Lower Bound means the function grows asymptotically at least as fast as its largest term.
True (Page 24) False
Question No: 1 ( Marks: 1 )  Please choose one Efficient algorithm requires less computational…
Memory Running Time Memory and Running Time (Page 9) Energy
Question No: 1 ( Marks: 1 )  Please choose one The Onotation is used to state only the asymptotic ________bounds.
Two Lower Upper (Page 25) Both lower & upper
Question No: 1 ( Marks: 1 )  Please choose one For the worstcase running time analysis, the nested loop structure containing one “for” and one “while” loop, might be expressed as a pair of _________nested summations.
1 2 (Page 16) 3 4 Question No: 1 ( Marks: 1 )  Please choose one Before sweeping a vertical line in plane sweep approach, in start sorting of the points is done in increasing order of their _______coordinates.
X (Page 18) Y Z X & Y
12
Question No: 1 ( Marks: 1 )  Please choose one Bruteforce algorithm for 2DMaxima is operated by comparing ________ pairs of points.
Two Some Most All (Page 18)
Question No: 1 ( Marks: 1 )  Please choose one The function f(n)=n(logn+1)/2 is asymptotically equivalent to nlog n. Here Lower Bound means function f(n) grows asymptotically at ____________ as fast as nlog n.
Normal Least (Page 23) Most All
Question No: 1 ( Marks: 1 )  Please choose one The definition of Thetanotation relies on proving ___________asymptotic bound.
One Lower Upper Both lower & upper (Page 25) rep
Question No: 1 ( Marks: 1 )  Please choose one In plane sweep approach, a vertical line is swept across the 2dplane and ______structure is used for holding the maximal points lying to the left of the sweep line.
Array Queue Stack (Page 18) Tree
Question No: 1 ( Marks: 1 )  Please choose one Algorithm analysts know for sure about efficient solutions for NPcomplete problems. Select correct option:
True False (Page 9)
13
Quiz No.1 (2012)
Question No: 1 of 10 ( Marks: 1 )  Please choose one The number of nodes in a complete binary tree of height h is
2^(h+1) – 1 (Page 40) 2 * (h+1) – 1 2 * (h+1) ((h+1) ^ 2) – 1
Question No: 1 of 10 ( Marks: 1 )  Please choose one The analysis of Selection algorithm shows the total running time is indeed in n,
arithmetic geometric linear (Page 37) orthogonal
Question No: 1 of 10 ( Marks: 1 )  Please choose one A (an) _________ is a leftcomplete binary tree that conforms to the heap order
heap (Page 40) binary tree binary search tree array
Question No: 1 of 10 ( Marks: 1 )  Please choose one Analysis of Selection algorithm ends up with,
T(n) (Page 37) T(1 / 1 + n) T(n / 2) T((n / 2) + n)
Question No: 1 of 10 ( Marks: 1 )  Please choose one For the sieve technique we solve the problem,
recursively (Page 34) mathematically precisely accurately
14
Question No: 1 of 10 ( Marks: 1 )  Please choose one A heap is a leftcomplete binary tree that conforms to the ___________
increasing order only decreasing order only heap order (Page 40) (log n) order
Question No: 1 of 10 ( Marks: 1 )  Please choose one In which order we can sort?
increasing order only decreasing order only increasing order or decreasing order (Page 39) both at the same time
Question No: 1 of 10 ( Marks: 1 )  Please choose one Divideandconquer as breaking the problem into a small number of
pivot Sieve smaller sub problems (Page 34) Selection
Question No: 1 of 10 ( Marks: 1 )  Please choose one For the heap sort we store the tree nodes in
levelorder traversal (Page 40) inorder traversal preorder traversal postorder traversal
Question No: 1 of 10 ( Marks: 1 )  Please choose one The sieve technique works in ___________ as follows
Phases (Page 34) numbers integers routines
15
CS502  Fundamentals of Algorithms Quiz No.1 12112012
Question No: 1 of 10 ( Marks: 1 )  Please choose one We do sorting to,
keep elements in random positions keep the algorithm run in linear order keep the algorithm run in (log n) order keep elements in increasing or decreasing order
Question No: 1 of 10 ( Marks: 1 )  Please choose one Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary tree,
leftcomplete (Page 40) rightcomplete tree nodes tree leaves
Question No: 1 of 10 ( Marks: 1 )  Please choose one Sieve Technique can be applied to selection problem?
True (Page 35) False
Question No: 1 of 10 ( Marks: 1 )  Please choose one In Sieve Technique we do not know which item is of interest
True (Page 34) False
Question No: 1 of 10 ( Marks: 1 )  Please choose one In the analysis of Selection algorithm, we eliminate a constant fraction of the array with each phase; we get the convergent _______________ series in the analysis,
linear arithmetic geometric (Page 37) exponent
16
Question No: 1 of 10 ( Marks: 1 )  Please choose one For the heap sort, access to nodes involves simple _______________ operations.
arithmetic (Page 41) binary algebraic logarithmic
Question No: 1 of 10 ( Marks: 1 )  Please choose one Slow sorting algorithms run in,
T(n^2) (Page 39) T(n) T( log n)
Question No: 1 of 10 ( Marks: 1 )  Please choose one In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as,
T(n) T(n / 2) log n (Page 37) n / 2 + n / 4
Question No: 1 of 10 ( Marks: 1 )  Please choose one The sieve technique is a special case, where the number of sub problems is just 5 many 1 (Page 34) few Question No: 1 of 10 (Marks: 1)  Please choose one How many elements do we eliminate in each time for the Analysis of Selection algorithm?
(n / 2)+n elements (n / 2) elements (Page 37) n / 4 elements 2 n elements
Question No: 1 of 10 ( Marks: 1 )  Please choose one One of the clever aspects of heaps is that they can be stored in arrays without using any . pointers (Page 40) constants variables functions
17
Question No: 1 of 10 ( Marks: 1 )  Please choose one How much time merge sort takes for an array of numbers?
T(n^2) T(n) T( log n) T(n log n) (Page 40)
Question No: 1 of 10 ( Marks: 1 )  Please choose one The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,
divideandconquer (Page 34) decrease and conquer greedy nature 2dimension Maxima
Question No: 1 of 10 ( Marks: 1 )  Please choose one In Sieve Technique we do not know which item is of interest
True (Page 34) rep False
Question No: 1 of 10 ( Marks: 1 )  Please choose one Theta asymptotic notation for T (n) :
Set of functions described by: c1g(n)Set of functions described by c1g(n)>=f(n) for c1 s Theta for T(n)is actually upper and worst case comp (Not sure) Set of functions described by: c1g(n)
Question No: 1 of 10 ( Marks: 1 )  Please choose one Memoization is?
To store previous results for future use To avoid this unnecessary repetitions by writing down the results of recursive calls and looking them up again if we need them later (page 74) To make the process accurate None of the above
Question No: 1 of 10 ( Marks: 1 )  Please choose one Which sorting algorithm is faster O (n log n) Page 26 O n^2 O (n+k) O n^3
18
Question No: 1 of 10 ( Marks: 1 )  Please choose one Quick sort is
Stable & in place Not stable but in place (Page 54) Stable but not in place Some time stable & some times in place
Question No: 1 of 10 ( Marks: 1 )  Please choose one One example of in place but not stable algorithm is
Merger Sort Quick Sort (Page 54) Continuation Sort Bubble Sort
Question No: 1 of 10 ( Marks: 1 )  Please choose one Cont sort is suitable to sort the elements in range 1 to k K is Large K is not known K may be small or large K is small (Page 57)
Question No: 1 of 10 ( Marks: 1 )  Please choose one In place stable sorting algorithm.
If duplicate elements remain in the same relative position after sorting (Page 54) One array is used More than one arrays are required Duplicating elements not handled
Question No: 1 of 10 ( Marks: 1 )  Please choose one Which may be a stable sort? Merger Insertion (Page 54)
Both above None of the above
Question No: 1 of 10 ( Marks: 1 )  Please choose one An in place sorting algorithm is one that uses ___ arrays for storage
Two dimensional arrays More than one array No Additional Array (Page 54) None of the above
19
Question No: 1 of 10 ( Marks: 1 )  Please choose one Sieve Technique applies to problems where we are interested in finding a single item from a larger set of _____________
n items (Page 34) phases pointers constant
Question No: 1 of 10 ( Marks: 1 )  Please choose one Sorting is one of the few problems where provable ________ bonds exits on how fast we can sort,
upper lower (Page 39) average log n
Question No: 1 of 10 ( Marks: 1 )  Please choose one Counting sort has time complexity:
O(n) (Page 58) O(n+k) O(k) O(nlogn)
Question No: 1 of 10 ( Marks: 1 )  Please choose one The running time of quick sort depends heavily on the selection of
No of inputs Arrangement of elements in array Size o elements Pivot elements (Page 49)
Question No: 1 of 10 ( Marks: 1 )  Please choose one Which may be stable sort:
Bubble sort Insertion sort Both of above (Page 54)
20
Question No: 1 of 10 ( Marks: 1 )  Please choose one One Example of in place but not stable sort is
Quick (Page 54) Heap Merge Bubble
Question No: 1 of 10 ( Marks: 1 )  Please choose one In Quick Sort Constants hidden in T(n log n) are
Large Medium Small Click here for detail Not Known
Question No: 1 of 10 ( Marks: 1 )  Please choose one Quick sort is based on divide and conquer paradigm; we divide the problem on base of pivot element and:
There is explicit combine process as well to conquer the solution. No work is needed to combine the subarrays, the array is already sorted Merging the sub arrays None of above. (Page 51) Ref:  random choices for the pivot element and each choice have an equal probability of 1/n of occurring. So we can modify the above recurrence to compute an average rather than a max
21
CS501  Quiz No.2 (Spring 2013)
Question No: 1 of 10 ( Marks: 1 )  Please choose one A point p in 2dimensional space is usually given by its integer coordinate(s)
p.x only p.y only p.x & p.z p.x & p.y (Page 10)
Question No: 1 of 10 ( Marks: 1 )  Please choose one In ____________ we have to find rank of an element from given input.
Merge sort algorithm Selection problem (Page 34) Brute force technique Plane Sweep algorithm
Question No: 1 of 10 ( Marks: 1 )  Please choose one In Heap Sort algorithm, if heap property is violated _________
We call Build heap procedure We call Heapify procedure We ignore Heap property can never be violated
Question No: 1 of 10 ( Marks: 1 )  Please choose one Upper bound requires that there exist positive constants c2 and n0 such that f(n) ____ c2n for all n <= n0(ye question ghalat lag raha hai mujhae
Less than Equal to or Less than (Page 25) Equal or Greater than Greater than
Question No: 1 of 10 ( Marks: 1 )  Please choose one A RAM is an idealized algorithm with takes an infinitely large randomaccess memory.
True False (Page 10)
22
Question No: 1 of 10 ( Marks: 1 )  Please choose one _________ is one of the few problems, where provable lower bounds exist on how fast we can sort.
Searching Sorting (Page ) Both Searching & Sorting Graphing
Question No: 1 of 10 ( Marks: 1 )  Please choose one
Floor and ceiling are ____________ to calculate while analyzing algorithms.
Very easy Usually considered difficult (Page 31)
Question No: 1 of 10 ( Marks: 1 )  Please choose one In Heap Sort algorithm, the maximum levels an element can move upward is _________
Theta (log n) (Page 43) Order (log n) Omega (log n)
O (1) i.e. Constant time
Question No: 1 of 10 ( Marks: 1 )  Please choose one A point p in 2dimensional space is usually given by its integer coordinate(s)
p.x only p.y only p.x & p.z
p.x & p.y (Page 17)
Question No: 1 of 10 ( Marks: 1 )  Please choose one In Heap Sort algorithm, the total running time for Heapify procedure is ____________
Theta (log n) (Page 43) Order (log n)
Omega (log n) O (1) i.e. Constant time
Question No: 1 of 10 ( Marks: 1 )  Please choose one Algorithm is a mathematical entity, which is independent of a specific machine and operating system.
True False (Page 7)
23
Question No: 1 of 10 ( Marks: 1 )  Please choose one While Sorting, the ordered domain means for any two input elements x and y _________ satisfies only.
x < y x > y x = y All of the above (Page 39)
Question No: 1 of 10 ( Marks: 1 )  Please choose one Quick sort is best from the perspective of Locality of reference.
True (Page 9) False
Question No: 1 of 10 ( Marks: 1 )  Please choose one Sorting can be in _________
Increasing order only Decreasing order only Both Increasing and Decreasing order (Page 39) Random order
Question No: 1 of 10 ( Marks: 1 )  Please choose one In Heap Sort algorithm, we build _______ for ascending sort.
Max heap (Page 41) Min heap
Question No: 1 of 10 ( Marks: 1 )  Please choose one In Sieve Technique, we know the item of interest.
True False (Page 34)
Question No: 1 of 10 ( Marks: 1 )  Please choose one While solving Selection problem, in Sieve technique we partition input data __________
In increasing order In decreasing order According to Pivot (Page 35) Randomly
24
Question No: 1 of 10 ( Marks: 1 )  Please choose one In pseudo code, the level of details depends on intended audience of the algorithm.
True (Page 12) False
Question No: 1 of 10 ( Marks: 1 )  Please choose one The sieve technique works where we have to find _________ item(s) from a large input.
Single (Page 34) Two Three Similar
Question No: 1 of 10 ( Marks: 1 )  Please choose one If the indices passed to merge sort algorithm are ________,then this means that there is only one element to sort.
Small Large Equal (Page 28) Not Equal
25 

