DS Assignment Presentation 20242024.pptx

Nssnsnsssjsja

1. DS Assignment Presentation Done By: Team 18 Harish Veeramani (2312019) Sanjeev Narayan(2312038)

2. To implement a function that finds the inorder successor of a specified students name in the BST structure representing the school's student database. Program: #include <iostream> #include <string> using namespace std; struct Node { string key; // Student's name Node* left; Node* right; Node(string val ) : key( val ), left( nullptr ), right( nullptr ) {} };

3. Node* insert(Node* root, string key) { if (root == nullptr ) return new Node(key); if (key < root->key) root->left = insert(root->left, key); else root->right = insert(root->right, key); return root; } Node* findMin (Node* node) { while (node && node->left != nullptr ) node = node->left; return node; } Node* findInorderSuccessor (Node* root, Node* target) { if (!root || !target) return nullptr ;

4. if (target->right) { return findMin (target->right); } Node* successor = nullptr ; Node* current = root; while (current) { if (target->key < current->key) { successor = current; current = current->left; } else if (target->key > current->key) { current = current->right; } else { break; } } return successor; }

5. int main() { Node* root = nullptr ; root = insert(root, "Alice"); root = insert(root, "Bob"); root = insert(root, "Charlie"); root = insert(root, "Diana"); root = insert(root, "Eve"); Node* target = root->left; // Example: "Bob" Node* successor = findInorderSuccessor (root, target); if (successor) cout << " Inorder Successor of " << target->key << " is " << successor->key << endl ; else cout << "No Inorder Successor for " << target->key << endl ; return 0; }

6. Question: Develop a library book management system using an AVL tree to keep track of books.Each book has a unique ISBN, title, and author.Implement the AVL tree operations for the Dictionary ADT to manage book records.Insert multiple book records into the AVL tree and ensure it remains balanced.Search for a book by ISBN and display its details.Update a book's author and ensure the tree remains balanced.Sample Input:Insert : ("978-3-16-148410-0", "Book A", "Author A"), ("978-0-306-40615-7", "Book B","Author B"), ("978-1-4028-9462-6", "Book C", "Author C")Search: "978-0-306-40615-7"Update: (978-0-306-40615-7", "Book B", "Author X*)Sample Output:Inserted : ("978-3-16-148410-0", "Book A", "Author A")Inserted: ("978-0-306-40615-7", "Book B", "Author B")Inserted: "978-1-4028-9462-6"Found: ("978-0-306-40615-7","Book C", "Author C"), "Book B", "Author B')Updated: (978-0-306-40615-7", "Book B", "Author X)

7. Program: #include <iostream> #include <string> using namespace std; struct BookNode { string isbn ; string title; string author; int height; BookNode * left; BookNode * right; BookNode (string i , string t, string a) : isbn ( i ), title(t), author(a), height(1), left( nullptr ), right( nullptr ) {} }; int getHeight ( BookNode * node) { return node ? node->height : 0; }

8. int getBalanceFactor ( BookNode * node) { return node ? getHeight (node->left) - getHeight (node->right) : 0; } void updateHeight ( BookNode * node) { if (node) { node->height = 1 + max( getHeight (node->left), getHeight (node->right)); } } BookNode * rotateRight ( BookNode * y) { BookNode * x = y->left; BookNode * T = x->right; x->right = y; y->left = T; updateHeight (y); updateHeight (x); return x; }

9. BookNode * rotateLeft ( BookNode * x) { BookNode * y = x->right; BookNode * T = y->left; y->left = x; x->right = T; updateHeight (x); updateHeight (y); return y; } BookNode * balanceNode ( BookNode * node) { int balance = getBalanceFactor (node); if (balance > 1) { if ( getBalanceFactor (node->left) < 0) { node->left = rotateLeft (node->left); } return rotateRight (node); }

10. if (balance < -1) { if ( getBalanceFactor (node->right) > 0) { node->right = rotateRight (node->right); } return rotateLeft (node); } return node; } BookNode * insert( BookNode * root, string isbn , string title, string author) { if (!root) return new BookNode ( isbn , title, author); if ( isbn < root-> isbn ) root->left = insert(root->left, isbn , title, author); else if ( isbn > root-> isbn ) root->right = insert(root->right, isbn , title, author);

11. else return root; updateHeight (root); return balanceNode (root); } BookNode * search( BookNode * root, string isbn ) { if (!root || root-> isbn == isbn ) return root; if ( isbn < root-> isbn ) return search(root->left, isbn ); return search(root->right, isbn ); } BookNode * update( BookNode * root, string isbn , string newAuthor ) { BookNode * target = search(root, isbn ); if (target) { target->author = newAuthor ; } return root; // Tree remains balanced }

12. void inorder ( BookNode * root) { if (root) { inorder (root->left); cout << "(" << root-> isbn << ", " << root->title << ", " << root->author << ")" << endl ; inorder (root->right); } } int main() { BookNode * root = nullptr ; root = insert(root, "978-3-16-148410-0", "Book A", "Author A"); cout << "Inserted: (978-3-16-148410-0, Book A, Author A)" << endl ; root = insert(root, "978-0-306-40615-7", "Book B", "Author B"); cout << "Inserted: (978-0-306-40615-7, Book B, Author B)" << endl ; root = insert(root, "978-1-4028-9462-6", "Book C", "Author C"); cout << "Inserted: (978-1-4028-9462-6, Book C, Author C)" << endl ;

13. string searchISBN = "978-0-306-40615-7"; BookNode * found = search(root, searchISBN ); if (found) { cout << "Found: (" << found-> isbn << ", " << found->title << ", " << found->author << ")" << endl ; } else { cout << "Book not found with ISBN: " << searchISBN << endl ; } string updateISBN = "978-0-306-40615-7"; root = update(root, updateISBN , "Author X"); cout << "Updated: (" << updateISBN << ", Book B, Author X)" << endl ; cout << "Books in AVL Tree:" << endl ; inorder (root); return 0; }

14. Question: Given a graph G = (V,E) with n vertices and m edges, and a subset T of I vertices calledterminals , the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of k edges (non-terminal vertices), whose removal from G separates each terminal from all the others

15. #include <iostream> #include <vector> #include <queue> #include <limits> #include <set> #include <map> using namespace std; struct Edge {     int to, capacity, flow, rev; }; class Graph { private:     int V;     vector<vector<Edge>> adj ; public:     Graph(int vertices) : V(vertices), adj (vertices) {}

16. void addEdge (int u, int v, int capacity) {       Edge a{v, capacity, 0, (int) adj [v].size()};         Edge b{u, 0, 0, (int) adj [u].size()};         adj [u]. push_back (a);         adj [v]. push_back (b);     }     bool bfs (int s, int t, vector<int>& parent) {         vector<bool> visited(V, false);         queue<int> q;         q.push (s);         visited[s] = true;         while (! q.empty ()) {             int u = q.front ();             q.pop ();

17.         for (int i = 0; i < adj[u].size(); i++) {                 Edge& e = adj [u][ i ];                 if (!visited[e.to] && e.capacity > e.flow ) {                     parent[e.to] = u;                     visited[e.to] = true;                     if (e.to == t) return true;                     q.push (e.to);                 }             }         }         return false;     }  int fordFulkerson (int s, int t) {         vector<int> parent(V);         int maxFlow = 0;

18.         while (bfs(s, t, parent)) {             int pathFlow = numeric_limits <int>::max();             for (int v = t; v != s; v = parent[v]) {                 int u = parent[v];                 for (Edge& e : adj[u]) {                     if (e.to == v && e.capacity > e.flow) {                         pathFlow = min(pathFlow, e.capacity - e.flow);                         break;                     }                 }             }      for (int v = t; v != s; v = parent[v]) {                 int u = parent[v];                 for (Edge& e : adj[u]) {                     if (e.to == v) {                         e.flow += pathFlow;                         adj[v][e.rev].flow -= pathFlow;                         break;                     }                 }             }

19.       maxFlow += pathFlow ;         }         return maxFlow ;     } set<int> getReachable (int s) {         vector<bool> visited(V, false);         set<int> reachable;         queue<int> q;         q.push (s);         visited[s] = true; while (! q.empty ()) {             int u = q.front ();             q.pop ();             reachable.insert (u); for (Edge& e : adj[u]) {                 if (!visited[e.to] && e.capacity > e.flow ) {                     visited[e.to] = true;                     q.push (e.to);                 }             }         }

20.  return reachable;     } }; void multiTerminalCut (int n, const vector<pair<int, int>>& edges, const vector<int>& terminals) {     Graph graph(n);     map<pair<int, int>, int> edgeMap ; for (auto& edge : edges) {         int u = edge.first , v = edge.second ;         graph.addEdge (u, v, 1);  // Capacity of 1 for unit edge weights         edgeMap [{u, v}] = edgeMap [{v, u}] = 1;  // Track edges for cuts     } set<int> removedEdges ;     for ( size_t i = 0; i < terminals.size (); ++ i ) {         for ( size_t j = i + 1; j < terminals.size (); ++j) {             int source = terminals[ i ];             int sink = terminals[j]; Graph tempGraph = graph;              int cutValue = tempGraph.fordFulkerson (source, sink);             set<int> reachable = tempGraph.getReachable (source);  for (int u = 0; u < n; ++u) {                 for (Edge& e : graph.adj [u])

21.   {                     if ( reachable.count (u) && ! reachable.count (e.to)) {                         removedEdges.insert ( edgeMap [{u, e.to}]);                     }                 }             }         }     }     cout << "Edges to remove for multiterminal cut:" << endl ;     for (int edge : removedEdges ) {         cout << edge << " ";     }     cout << endl ; }int main() {     int n = 6;     vector<pair<int, int>> edges = {         {0, 1}, {1, 2}, {1, 3}, {2, 4}, {3, 4}, {4, 5}     };     vector<int> terminals = {0, 2, 5};     multiTerminalCut (n, edges, terminals);     return 0; }

22. Thank You