1.

Data Structures and Algorithms : Course Based Project: (Team 1 and Team 7 )
a) Define stack. List all applications of stacks
b) Simulate stacks operations push () and pop() using graphics.h
Follow link to understand how it should look like :
https://www.cs.usfca.edu/~galles/visualization/StackArray.html

c) Write a menu driven code that helps you to perform parenthesis matching in a given
string
i) Using stacks … determine time complexity involved
(you have to derive time complexity involved and use “ time.h” related
functions to calculate time )
ii) Without using stacks….determine time complexity
(you have to derive time complexity involved and use “ time.h” related
functions to calculate time )
d) Given an integer N with D digits without any leading zeroes. Find the largest number
which can be obtained by deleting exactly K digits from the number N.
Note: Return the largest number without any leading zeroes.
Input format
 First line contains integer N.
 Second line contains integer K.
Output format
Return the largest number which can be obtained by deleting exactly K digits from the number N.
Constraints
𝑁>01≤𝐷≤1060≤𝐾<𝐷
Sample Input
44312
2
Sample Output
443

2. Data Structures and Algorithms : Course Based Project: (Team 2 and Team 8)
a) Define Queues. List all applications of queues
b) Simulate linear queue operations insert () and delete () using graphics.h
Follow link to understand how it should look like :
https://www.cs.usfca.edu/~galles/visualization/StackArray.html

c) Given an integer k and a queue of integers, The task is to reverse the order of the first k
elements of the queue, leaving the other elements in the same relative order. Write a
program.
d) A positive integer 𝑋 has been stolen. But luckily, 𝑁 hints are available, each described by
two integers 𝑎𝑖 and 𝑑𝑖, meaning that |𝑋−𝑎𝑖|=𝑑𝑖. The hints are numbered 1 through 𝑁.
While some of those hints are helpful, some might be just a lie. Therefore, we are going
to investigate the number 𝑋 under different possible scenarios.
Initially, we neither trust nor distrust any hint. That is, each hint may be either true or false. Then,
in each of the 𝑄 stages, we will either:
 1 id
Entrust the 𝑖𝑑-th hint (1≤𝑖𝑑≤𝑁). That is, from now on, the 𝑖𝑑-th hint must be true, unless
declared otherwise in the future.
  2 id
Distrust the 𝑖𝑑-th hint (1≤𝑖𝑑≤𝑁). That is, from now on, the 𝑖𝑑-th hint must be false, unless
declared otherwise in the future.
 3 id
Neutralize the 𝑖𝑑-th hint (1≤𝑖𝑑≤𝑁). That is, from now on, the 𝑖𝑑-th hint may be either true or
false, unless declared otherwise in the future.
After each stage, you should determine the number of possible positive values 𝑋 and report such
values in an increasing order. If there are infinitely many such values, print −1 instead.
Input
The first line contains two space-separated integers 𝑁 and 𝑄.
The 𝑖-th of the following 𝑁 lines contains two space-separated integers 𝑎𝑖 and 𝑑𝑖, describing the 𝑖-th
hint. It is guaranteed that no two hints are identical. That is, for every two different 𝑖, 𝑗, it
is guaranteed that 𝑎𝑖≠𝑎𝑗 or 𝑑𝑖≠𝑑𝑗.
Then, 𝑄 lines follow, each containing two integers 𝑡 and 𝑖𝑑 — the type of an update and the index of
an affected hint.
Output
After each stage, print the number of possible values of 𝑋 (in case there are infinitely many of them,
print −1). If the number of possible values is finite and non-zero, in the same line, continue to print
those values in an increasing order.
Constraints
1≤𝑁,𝑄≤200000
0≤𝑎𝑖,𝑑𝑖≤109
1≤𝑡≤3 for every stage (update).
1≤𝑖𝑑≤𝑁 for every stage.
In tests worth 74 points in total, 𝑎𝑖,𝑑𝑖≤500000.
Note that the expected output feature for custom input is disabled for this contest.
Sample Input
3 10
30
03
63
11
31
12
32
13
33
11
12
21
13
Sample Output
13
-1
13
-1
239
-1
13
13
0
0
 3. Data Structures and Algorithms : Course Based Project: (Team 3 and Team 9)
a) Define Linked List. List all applications of Linked Lists
b) Simulate single linked list operations insert () and delete () using graphics.h
Follow link to understand how it should look like :
https://www.cs.usfca.edu/~galles/visualization/StackArray.html
c) You are given a linked list that contains 𝑁 integers. You have performed the following
reverse operation on the list:
Select all the subparts of the list that contain only even integers. For example, if the list
is {1,2,8,9,12,16}, then the selected subparts will be {2,8}, {12,16}.
Reverse the selected subpart such as {8,2} and {16,12}.
Now, you are required to retrieve the original list.
Note: You should use the linked list for this problem:

Input format
 First line: 𝑁
 Next line: 𝑁 space-separated integers that denote elements of the reverse list
Output format
Print the 𝑁 elements of the original list.

Constraints
1≤𝑁≤103
1≤𝐴𝑖≤109
Sample Input
9
2 18 24 3 5 7 9 6 12
Sample Output
24 18 2 3 5 7 9 12 6

d) After getting her PhD, Christie has become a celebrity at her university, and her facebook
profile is full of friend requests. Being the nice girl she is, Christie has accepted all the
requests.
Now Kuldeep is jealous of all the attention she is getting from other guys, so he asks her
to delete some of the guys from her friend list.
To avoid a 'scene', Christie decides to remove some friends from her friend list, since she
knows the popularity of each of the friend she has, she uses the following algorithm to
delete a friend.
Algorithm Delete(Friend):
DeleteFriend=false
for i = 1 to Friend.length-1
if (Friend[i].popularity < Friend[i+1].popularity)
delete i th friend
DeleteFriend=true
break
if(DeleteFriend == false)
delete the last friend
Input:
First line contains T number of test cases. First line of each test case contains N, the
number of friends Christie currently has and K ,the number of friends Christie decides to
delete. Next lines contains popularity of her friends separated by space.
 Output:
For each test case print N-K numbers which represent popularity of Christie friend's after
deleting K friends.
Constraints
1<=T<=1000
1<=N<=100000
0<=K< N
0<=popularity_of_friend<=100
NOTE: Order of friends after deleting exactly K friends should be maintained as given in
input.
Sample Input
3
31
3 100 1
52
19 12 3 4 17
53
23 45 11 77 18
Sample Output
100 1
19 12 17
77 18

4. Data Structures and Algorithms : Course Based Project: (Team 4 and Team 10)
(a) Without dwelling on the structure of the nodes and on the positional relationship
between keys and subtrees (for which an example picture will be sufficient), give an
otherwise complete and concise definition of a B-tree of minimum degree t, listing all the
defining structural properties.
(b) Explain how to insert a new item into a B-tree, showing that the algorithm preserves the
B-tree properties you gave in part (a). Show the same using graphics.h
https://www.cs.usfca.edu/~galles/visualization/BST.html

Then insert the following values, in this order, into an initially empty B-tree whose nodes
hold at most three keys each: C A M B R I D G E X. Produce a frame-by-frame “movie” in
which you redraw the tree whenever it changes in any way.
(c) Define a “bottom node” as any internal node whose children are (keyless) leaves. Prove
that, for any key in any node of a B-tree, either the key is in a bottom node or its successor is.
You may, for simplicity, assume that all keys are distinct.
(d) Explain how to delete a value from a B-tree:
i) Explain the overall strategy, with diagrams , convincing the reader that it covers all possible
cases and preserves the B-tree properties.
(ii) Apply this procedure to the deletion of values M, Q, Y, in that order, from the following B-
tree, producing a frame-by-frame movie as requested for part (b).
As before, each node holds at most three keys. J-------------------------V C-----G M-----Q---T Y AB
DEF HI KL NOP R U X Z
5. Data Structures and Algorithms : Course Based Project: (Team 5 and Team 11)
a) Write why hashing becomes necessary.
b) Using graphics.h show how a closed hashing works

c) A closed hash table is one in which the overflow chains of key–value pairs are held within the
table itself. Carefully describe how the closed hash table mechanism works for both insertion and
lookup.

d) Assume that the initial probe is p0 = Hash1(key) mod B and the secondary probes are pi , i =
1 . . . B − 1. Discuss the relative merits of the following schemes for choosing the secondary
probes. (i) pi = (p0 + i) mod B (ii) pi = (p0 + 13 ∗ i) mod B (iii) pi = (p0 + 13 ∗ i + 17 ∗ i ∗ i) mod B
(iv) pi = (p0 + Hash2(key) ∗ i + 17 ∗ i ∗ i) mod B

You may assume that all the arithmetic is unsigned.

Carefully describe a mechanism for deleting key–value pairs from a closed hash table.

6. Data Structures and Algorithms : Course Based Project: (Team 6 and Team 12)

a) Simulate using graphics.h the following sorting algorithms…use a menu driven approach
for the same . check sample link: https://visualgo.net/en/sorting?slide=1

i) Insertion sort
ii) Selection sort

b) Write a menu driven program to solve above two sorting algorithms using recursion