DEPARTMENT OF

COMPUTER SCIENCE & ENGINEERING

Subject: Design and Analysis of Algorithms

Name: Suryapraksh Subudhi

UID:23BET10117
Submitted to:Ms. Kushwant kaur
Section and Group:901-A
Subject Code: 23CSH-301/23ITH-301 Semester: 5th

Complex Problems for Average Learner’s

1. Code to find the ignored successor in an BinarySearch Trees with complexity Analysis.

Answer:
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
Node(int v){ data=v; left=right=nullptr; }
};

Node* insert(Node* root, int v){

if(!root) return new Node(v);
if(v < root->data) root->left = insert(root->left, v);
else root->right = insert(root->right, v);
return root;
}

Node* inorderSuccessor(Node* root, Node* x){

Node* succ = nullptr;
while(root){
if(x->data < root->data) succ = root, root = root->left;
else root = root->right;
}
return succ;
}

int main(){
Node* root = nullptr;
for(int v : {20,8,22,4,12,10,14}) root = insert(root,v);
Node* x = root->left->right->right;
Node* s = inorderSuccessor(root,x);
cout << (s ? s->data : -1);
}
 DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Time Complexity for the above code:

O(h) → O(log n) for a balanced BST and O(n) for a skewed BST.

2. Given the pointer to the head node of a linked list, change the next pointers of the nodes
so that their order is reversed. The head pointer given may be null meaning that the initial
list is empty.
Example
head references the list 1->2->3->4->NULL
Manipulate the pointers of each node in place and return head, now
referencing the head of the list 3->2->1->NULL .
Function Description
Complete the reverse function.
reverse has the following parameter:
● SinglyLinkedListNode pointer head: a reference to the head of a list
Returns
● SinglyLinkedListNode pointer: a reference to the head of the reversed
list
Input Format
The first line contains an integer t, the number of test cases.
Each test case has the following format:
The first line contains an integer n, the number of elements in the linked list.
Each of the next n lines contains an integer, the data values of the elements
in the linked list.
Constraints

Answer:
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
Node(int x){ data=x; next=nullptr; }
 DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

};

Node* reverse(Node* head){

Node *prev=nullptr, *cur=head, *nxt;
while(cur){ nxt=cur->next; cur->next=prev; prev=cur; cur=nxt; }
return prev;
}

int main(){
Node* head=new Node(1);
head->next=new Node(2);
head->next->next=new Node(3);
head = reverse(head);
for(Node* t=head;t;t=t->next) cout<<t->data<<" ";
}

Time Complexity: O(n)

Space Complexity: O(1)

3. Sort a given set of elements using the Heap sort method and determine the time required
to sort the elements. Repeat the experiment for different values of n, the number of
elements in the list to be sorted and plot a graph of the time taken versus n. The elements
can be read from a file or can be generated using the random number generator.
 DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Answer:
#include <bits/stdc++.h>
using namespace std;
void heapify(vector<int>& a,int n,int i){
int l=2*i+1,r=2*i+2,largest=i;
if(l<n && a[l]>a[largest]) largest=l;
if(r<n && a[r]>a[largest]) largest=r;
if(largest!=i){ swap(a[i],a[largest]); heapify(a,n,largest); }
}
void heapSort(vector<int>& a){
int n=[Link]();
for(int i=n/2-1;i>=0;i--) heapify(a,n,i);
for(int i=n-1;i>0;i--){ swap(a[0],a[i]); heapify(a,i,0); }
}
int main(){
int n; cin>>n;
vector<int> a(n); for(int&i:a)cin>>i;
clock_t s=clock(); heapSort(a); clock_t e=clock();
for(int x:a) cout<<x<<" ";
cout<<"\nTime: "<<(double)(e-s)/CLOCKS_PER_SEC;
}
Overall Time Complexity: O(n log n)
Space Complexity: O(1) (in-place sorting)
 DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

4. Write the postOrder function. It received 1 parameter: a pointer to the root of a binary
tree. It must print the values in the tree's postorder traversal as a single line of space-
separated values.
Input Format
Our test code passes the root node of a binary tree to the postOrder function.
Constraints

Answer:
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left,*right;
Node(int x){ data=x; left=right=nullptr; }
};
void postOrder(Node* root){
if(!root) return;
postOrder(root->left);
postOrder(root->right);
cout<<root->data<<" ";
}
int main(){
Node* root=new Node(1);
root->left=new Node(2);
root->right=new Node(3);
postOrder(root);
}

Time Complexity: O(n)

 DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

5. Code for enqueue, dequeue, Isfull and Isempty operation in queues using templates.

Answer:
#include <bits/stdc++.h>
using namespace std;
template<class T>
class Queue {
int f,r,sz; T* q;
public:
Queue(int n){ sz=n; f=r=-1; q=new T[n]; }
bool isEmpty(){ return f==-1; }
bool isFull(){ return (r+1)%sz==f; }
void enqueue(T x){
if(isFull()) cout<<"Full\n";
else { if(f==-1) f=0; r=(r+1)%sz; q[r]=x; }
}
void dequeue(){
if(isEmpty()) cout<<"Empty\n";
else if(f==r) f=r=-1;
else f=(f+1)%sz;
}
void display(){
if(isEmpty()) return;
for(int i=f;;i=(i+1)%sz){ cout<<q[i]<<" "; if(i==r) break; }
cout<<"\n";
}
};
int main(){
Queue<int> q(3);
[Link](10); [Link](20); [Link](30);
[Link](); [Link](); [Link]();
}

Time Complexity: O(1) per enqueue/dequeue

 DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

6. Marc loves cupcakes, but he also likes to stay fit. Each cupcake has a calorie count, and
Marc can walk a distance to expend those calories. If Marc has eaten j cupcakes so far,
after eating a cupcake with c calories he must walk at least 2i *c miles to maintain his
weight.
Example
calorie = [5,10,7]
If he eats the cupcakes in the order shown, the miles he will need to walk are
(20 *5) + (21* 10) +(22*7) = 5+20+28 = 53. This is not the minimum, though,
so we need to test other orders of consumption. In this case, our minimum
miles is calculated as (20 *10) + (21* 7) +(22*5) = 10+14+20 = 44.
Given the individual calorie counts for each of the cupcakes, determine the
minimum number of miles Marc must walk to maintain his weight. Note that
he can eat the cupcakes in any order.
Function Description
Complete the marcsCakewalk function in the editor below.
marcsCakewalk has the following parameter(s):
● int calorie[n]: the calorie counts for each cupcake
Returns
● long: the minimum miles necessary

Input Format
The first line contains an integer n, the number of cupcakes in .
The second line contains n space-separated integers,calorie[i] .
Constraints

Answer:
#include <bits/stdc++.h>
using namespace std;

// Function to calculate minimum miles

long marcsCakewalk(vector<int> calorie) {
sort([Link](), [Link](), greater<int>()); // sort descending
long long miles = 0;

for (int i = 0; i < [Link](); i++) {

miles += (long long)pow(2, i) * calorie[i];
 DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

return miles;
}

int main() {
int n;
cin >> n;

vector<int> calorie(n);
for (int i = 0; i < n; i++) {
cin >> calorie[i];
}

cout << marcsCakewalk(calorie) << endl;

return 0;
}

7. To implement KMP(Knuth-Morris-Pratt)algorithm.

Answer:
#include <bits/stdc++.h>
using namespace std;
vector<int> lpsFunc(string p){
int n=[Link](); vector<int> lps(n); int len=0;
for(int i=1;i<n;){ if(p[i]==p[len]) lps[i++]=++len; else if(len) len=lps[len-1]; else
lps[i++]=0; }
return lps;
}
void KMP(string t,string p){
vector<int> lps=lpsFunc(p); int i=0,j=0;
while(i<[Link]()){
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

if(t[i]==p[j]) i++,j++;
if(j==[Link]()){ cout<<"Found at "<<i-j<<"\n"; j=lps[j-1]; }
else if(i<[Link]() && t[i]!=p[j]) j?j=lps[j-1]:i++;
}
}
int main(){ string t="ababcababc",p="abc"; KMP(t,p); }
8. Priyanka works for an international toy company that ships by container. Her task is to
the determine the lowest cost way to combine her orders for shipping. She has a list of
item weights. The shipping company has a requirement that all items loaded in a
container must weigh less than or equal to 4 units plus the weight of the minimum weight
item. All items meeting that requirement will be shipped in one container.
What is the smallest number of containers that can be contracted to ship the
items based on the given list of weights?
For example, there are items with weights w = [1,2,3,4,5,10,11,12,13] . This
can be broken into two containers:[1,2,3,4,5] and [10,11,12,13] . Each
container will contain items weighing within units of the minimum weight
item.
Function Description
It should return the minimum number of containers required to ship.
toys has the following parameter(s):
● w: an array of integers that represent the weights of each order to ship

Input Format
The first line contains an integer n, the number of orders to ship.
The next line contains space-separated integers, w[1], w[2],…..,w[n] ,
representing the orders in a weight array.
Constraints

Answer:
#include <bits/stdc++.h>
using namespace std;
int toys(vector<int> w){
sort([Link](),[Link]());
int cnt=1,base=w[0];
for(int x:w) if(x>base+4){ cnt++; base=x; }
return cnt;
}
int main(){
int n; cin>>n;
vector<int>w(n); for(int&i:w)cin>>i;
 DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

cout<<toys(w);
}

9. To implement Prim’s algorithm for minimum spanning tree.

Answer:
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
void prims(vector<vector<pii>>&g,int V){
vector<int>key(V,1e9),par(V,-1); vector<bool>in(V,0);
key[0]=0; priority_queue<pii,vector<pii>,greater<pii>>pq;
[Link]({0,0});
while(![Link]()){
int u=[Link]().second; [Link](); if(in[u]) continue; in[u]=1;
for(auto [v,w]:g[u]) if(!in[v] && w<key[v]) key[v]=w,par[v]=u,[Link]({w,v});
}
int sum=0; for(int i=1;i<V;i++) sum+=key[i],cout<<par[i]<<"-"<<i<<"("<<key[i]<<")\n";
cout<<"Total="<<sum;
}
int main(){
int V,E; cin>>V>>E;
vector<vector<pii>> g(V);
while(E--){ int u,v,w; cin>>u>>v>>w; g[u].push_back({v,w}); g[v].push_back({u,w}); }
prims(g,V);
}
10. You are given a pointer to the root of a binary search tree and values to be inserted into
the tree. Insert the values into their appropriate position in the binary search tree and
return the root of the updated binary tree.
Input Format
You are given a function,
Node * insert (Node * root ,int data) {

}
Constraints
• No. of nodes in the tree<= 500
Answer:
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data; Node *left,*right;
Node(int x){ data=x; left=right=nullptr; }
};
Node* insert(Node* r,int v){
if(!r) return new Node(v);
if(v<r->data) r->left=insert(r->left,v);
 DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

else if(v>r->data) r->right=insert(r->right,v);

return r;
}
void inorder(Node* r){ if(!r)return; inorder(r->left); cout<<r->data<<" "; inorder(r->right); }
int main(){
Node* r=nullptr; int n,x; cin>>n;
while(n--){ cin>>x; r=insert(r,x); }
inorder(r);
}