Guest User

Untitled

a guest
Aug 5th, 2024
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 25.42 KB | None | 0 0
  1. 1. Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given connected undirected graph using Kruskal's algorithm
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17.  
  18.  
  19.  
  20.  
  21.  
  22.  
  23.  
  24.  
  25.  
  26.  
  27.  
  28.  
  29.  
  30.  
  31. Program:
  32. #include<stdio.h>
  33. #define INF 999
  34. #define MAX 100
  35. int p[MAX],c[MAX][MAX],t[MAX][2];
  36.  
  37. {
  38. while(p[v]) v=p[v]; return v;
  39. }
  40. void union1(int i,int j)
  41. {
  42. p[j]=i;
  43. }
  44. void kruskal(int n)
  45. {
  46. int i,j,k,u,v,min,res1,res2,sum=0;
  47. for(k=1;k<n;k++)
  48. {
  49. min=INF;
  50. for(i=1;i<n-1;i++)
  51. {
  52. for(j=1;j<=n;j++)
  53. {
  54. if(i==j)continue;
  55. if(c[i][j]<min)
  56. {
  57. if(i==j)continue;
  58. if(c[i][j]<min)
  59. {
  60. u=find(i); v=find(j);
  61. if(u!=v)
  62. {
  63. res1=i; res2=j;
  64. min=c[i][j];
  65. }
  66. }
  67. }
  68. }
  69. union1(res1,find(res2)); t[k][1]=res1; t[k][2]=res2;
  70. sum=sum+min;
  71. }
  72. printf("\nCost of spanning tree is=%d",sum);
  73. printf("\nEdgesof spanning tree are:\n"); for(i=1;i<n;i++)
  74. printf("%d -> %d\n",t[i][1],t[i][2]);
  75. }
  76. int main()
  77. {
  78. int i,j,n;
  79. printf("\nEnter the n value:"); scanf("%d",&n);
  80. for(i=1;i<=n;i++)
  81. p[i]=0;
  82. printf(“Enter the graph data:\n”);
  83. for(i=1;i<=n;i++)
  84. p[i]=0;
  85. for(i=1;i<=n;i++)
  86. for(j=1;j<=n;j++)
  87. scanf("%d",&c[i][j]);
  88. kruskal(n);
  89. return 0;
  90. }
  91.  
  92.  
  93.  
  94. Output:
  95.  
  96. Enter the n value:5
  97. Enter the graph data:
  98. 0 10 15 9 999
  99. 10 0 999 17 15
  100. 15 999 0 20 999
  101. 9 17 20 0 18
  102. 999 15 999 18 0
  103. Cost of spanning tree is=49
  104. Edges of spanning tree are:
  105. 1 -> 4
  106. 1 -> 2
  107. 1 -> 3
  108. 2 -> 5
  109.  
  110. 2. Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given connected undirected graph using Prim's algorithm.
  111.  
  112. Program:
  113. #include<stdio.h>
  114. // #include<conio.h>
  115. #define INF 999
  116. int prim(int c[10][10],int n,int s)
  117. {
  118. int v[10],i,j,sum=0,ver[10],d[10],min,u;
  119. for(i=1;i<=n;i++)
  120. {
  121. ver[i]=s;
  122. d[i]=c[s][i]; v[i]=0;
  123. }
  124. v[s]=1;
  125. for(i=1;i<=n-1;i++)
  126. {
  127. min=INF;
  128. for(j=1;j<=n;j++)
  129. if(v[j]==0 && d[j]<min)
  130. {
  131. min=d[j];
  132. u=j;
  133. }
  134. v[u]=1; sum=sum+d[u];
  135. printf("\n%d -> %d sum=%d",ver[u],u,sum);
  136. for(j=1;j<=n;j++)
  137. if(v[j]==0 && c[u][j]<d[j])
  138. {
  139. d[j]=c[u][j];
  140. ver[j]=u;
  141. }
  142. }
  143. return sum;
  144. }
  145. void main()
  146. {
  147. int c[10][10],i,j,res,s,n;
  148. clrscr();
  149. printf("\nEnter n value:");
  150. scanf("%d",&n);
  151. printf("\nEnter the graph data:\n");
  152. for(i=1;i<=n;i++)
  153. for(j=1;j<=n;j++)
  154. scanf("%d",&c[i][j]); printf("\nEnter the souce node:");
  155. scanf("%d",&s);
  156. res=prim(c,n,s);
  157. printf("\nCost=%d",res); getch();
  158. }
  159.  
  160. Output:
  161. Enter n value:3
  162. Enter the graph data:
  163. 0 10 1
  164. 10 0 6
  165. Enter the souce node:1
  166. 1 -> 3 sum=1
  167. 3 -> 2 sum=7
  168. Cost=7
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188. 3. a. Design and implement C/C++ Program to solve All-Pairs Shortest Paths problem using Floyd's algorithm.
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.  
  203.  
  204.  
  205.  
  206.  
  207.  
  208.  
  209.  
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217.  
  218.  
  219.  
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226.  
  227.  
  228. Program A:
  229. #include<stdio.h>
  230. #include<conio.h>
  231. #define INF 999
  232. int min(int a,int b)
  233. {
  234. return(a<b)?a:b;
  235. }
  236. void floyd(int p[][10],int n)
  237. {
  238. int i,j,k;
  239. for(k=1;k<=n;k++)
  240. for(i=1;i<=n;i++)
  241. for(j=1;j<=n;j++)
  242. p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
  243. }
  244. void main()
  245. {
  246. int a[10][10],n,i,j;
  247. clrscr();
  248. printf("\nEnter the n value:");
  249. scanf("%d",&n);
  250. printf("\nEnter the graph data:\n"); for(i=1;i<=n;i++)
  251. p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
  252. }
  253. void main()
  254. {
  255. int a[10][10],n,i,j;
  256. clrscr();
  257. printf("\nEnter the n value:");
  258. scanf("%d",&n);
  259. printf("\nEnter the graph data:\n"); for(i=1;i<=n;i++)
  260. for(j=1;j<=n;j++)
  261. scanf("%d",&a[i][j]);
  262. floyd(a,n);
  263. printf("\nShortest path matrix\n");
  264. for(i=1;i<=n;i++)
  265. {
  266. for(j=1;j<=n;j++)
  267. printf("%d ",a[i][j]); printf("\n");
  268. }
  269. getch();
  270. }
  271.  
  272.  
  273.  
  274.  
  275.  
  276.  
  277.  
  278.  
  279.  
  280.  
  281.  
  282.  
  283.  
  284.  
  285.  
  286.  
  287.  
  288. Output:
  289. Enter the n value:4
  290. Enter the graph data:
  291. 0 999 3 999
  292. 2 0 999 999
  293. 999 7 0 1
  294. Shortest path matrix
  295. 0 10 3 4
  296. 2 0 5 6
  297. 7 7 0 1
  298. 6 16 9 0
  299.  
  300. . b. Design and implement C/C++ Program to find the transitive closure using Warshal's algorithm.
  301.  
  302.  
  303.  
  304.  
  305. Program B:
  306. printf("\nResultant path matrix\n");
  307. for(i=1;i<=n;i++)
  308. {
  309. for(j=1;j<=n;j++)
  310. printf("%d ",a[i][j]);
  311. printf("\n");#include<stdio.h>
  312. void warsh(int p[][10],int n)
  313. {
  314. int i,j,k;
  315. for(k=1;k<=n;k++)
  316. for(i=1;i<=n;i++)
  317. for(j=1;j<=n;j++)
  318. p[i][j]=p[i][j] || p[i][k] && p[k][j];
  319. }
  320. int main()
  321. {
  322. int a[10][10],n,i,j;
  323. printf("\nEnter the n value:");
  324. scanf("%d",&n);
  325. printf("\nEnter the graph data:\n");
  326. for(i=1;i<=n;i++)
  327. for(j=1;j<=n;j++)
  328. scanf("%d",&a[i][j]);
  329. warsh(a,n);
  330.  
  331. }
  332. return 0;
  333. }
  334.  
  335. Output:
  336. Enter the n value:4
  337. Enter the graph data:
  338. 0 1 0 0
  339. 0 0 0 1
  340. 1 0 0 0
  341. 2 0 1 0
  342. Resultant path matrix
  343. 1 1 1 1
  344. 1 0 0 0
  345. 2 1 1 1
  346.  
  347.  
  348.  
  349.  
  350.  
  351.  
  352.  
  353.  
  354.  
  355.  
  356.  
  357.  
  358.  
  359.  
  360.  
  361.  
  362.  
  363.  
  364.  
  365.  
  366.  
  367.  
  368.  
  369.  
  370. 4. Design and implement C/C++ Program to find shortest paths from a given vertex in a weighted connected graph to other vertices using Dijkstra's algorithm.
  371.  
  372.  
  373.  
  374.  
  375.  
  376.  
  377.  
  378.  
  379.  
  380.  
  381.  
  382.  
  383.  
  384.  
  385.  
  386.  
  387.  
  388.  
  389.  
  390.  
  391.  
  392.  
  393.  
  394.  
  395.  
  396.  
  397.  
  398.  
  399.  
  400.  
  401.  
  402.  
  403. Program:
  404. #include<stdio.h>
  405. #define INF 999
  406. void dijkstra(int c[10][10],int n,int s,int d[10])
  407. int v[10],min,u,i,j;
  408. for(i=1;i<=n;i++)
  409. {
  410. d[i]=c[s][i]; v[i]=0;
  411. }
  412. v[s]=1;
  413. for(i=1;i<=n;i++)
  414. {
  415. min=INF;
  416. for(j=1;j<=n;j++)
  417. if(v[j]==0 && d[j]<min)
  418. {
  419. min=d[j];
  420. u=j; }
  421. v[u]=1;
  422. for(j=1;j<=n;j++)
  423. if(v[j]==0 && (d[u]+c[u][j])<d[j])
  424. d[j]=d[u]+c[u][j];
  425. }
  426. }
  427. int main()
  428. {
  429. int c[10][10],d[10],i,j,s,sum,n;
  430. printf("\nEnter n value:");
  431. scanf("%d",&n);
  432. printf("\nEnter the graph data:\n");
  433. for(i=1;i<=n;i++)
  434. for(j=1;j<=n;j++)
  435. scanf("%d",&c[i][j]);
  436. printf("\nEnter the souce node:"); scanf("%d",&s);
  437. dijkstra(c,n,s,d);
  438. for(i=1;i<=n;i++)
  439. printf("\nShortest distance from %d to %d is %d",s,i,d[i]); return 0;
  440. }  
  441. Output:
  442. Enter n value:6
  443. Enter the graph data:
  444. 0 15 10 999 45 999
  445. 999 0 15 999 20 999
  446. 20 999 0 20 999 999
  447. 999 10 999 0 35 999
  448. 999 999 999 30 0 999
  449. 999 999 999 4 999 0
  450. Enter the souce node:2
  451. Shortest distance from 2 to 1 is 35
  452. Shortest distance from 2 to 2 is 0
  453. Shortest distance from 2 to 3 is 15
  454. Shortest distance from 2 to 4 is 35
  455. Shortest distance from 2 to 5 is 20
  456. Shortest distance from 2 to 6 is 999
  457.  
  458.  
  459.  
  460. 5. Design and implement C/C++ Program to obtain the Topological ordering of vertices in a given digraph.
  461.  
  462.  
  463.  
  464.  
  465.  
  466.  
  467.  
  468.  
  469.  
  470.  
  471.  
  472.  
  473.  
  474.  
  475.  
  476.  
  477.  
  478.  
  479.  
  480.  
  481.  
  482.  
  483.  
  484.  
  485.  
  486.  
  487.  
  488.  
  489.  
  490.  
  491.  
  492.  
  493.  
  494.  
  495.  
  496.  
  497.  
  498.  
  499.  
  500. PROGRAM:
  501. #include<stdio.h> #include<conio.h> int temp[10],k=0;
  502. void sort(int a[][10],int id[],int n)
  503. {
  504. int i,j;
  505. for(i=1;i<=n;i++)
  506. {
  507. if(id[i]==0)
  508. {
  509. id[i]=-1;
  510. temp[++k]=i;
  511. for(j=1;j<=n;j++)
  512. {
  513. if(a[i][j]==1 && id[j]!=-1)
  514. id[j]--;
  515. }
  516. i=0;
  517. }
  518. }
  519. void main()
  520. {
  521. int a[10][10],id[10],n,i,j;
  522. // clrscr();
  523. printf("\nEnter the n value:");
  524. scanf("%d",&n); for(i=1;i<=n;i++)
  525. id[i]=0;
  526. printf("\nEnter the graph data:\n");
  527. for(i=1;i<=n;i++) for(j=1;j<=n;j++)
  528. {
  529. scanf("%d",&a[i][j]); if(a[i][j]==1) id[j]++;
  530. }
  531. sort(a,id,n); if(k!=n)
  532. printf("\nTopological ordering not possible"); else
  533. {
  534. printf("\nTopological ordering is:"); for(i=1;i<=k;i++)
  535. printf("%d ",temp[i]);
  536. }
  537. // getch();
  538. }  
  539. Output:
  540. Enter the n value:6
  541. Enter the graph data:
  542. 001100
  543. 000110
  544. 000101
  545. 000001
  546. 000001
  547. 000000
  548. Topological ordering is:1 2 3 4 5 6
  549.  
  550.  
  551.  
  552.  
  553.  
  554.  
  555.  
  556.  
  557.  
  558.  
  559.  
  560.  
  561.  
  562.  
  563.  
  564.  
  565.  
  566.  
  567.  
  568.  
  569.  
  570.  
  571.  
  572.  
  573.  
  574.  
  575. 6. Design and implement C/C++ Program to solve 0/1 Knapsack problem using Dynamic Programming method.
  576.  
  577.  
  578.  
  579.  
  580.  
  581.  
  582.  
  583.  
  584.  
  585.  
  586.  
  587.  
  588.  
  589.  
  590.  
  591. PROGRAM:
  592. #include<stdio.h>
  593. int w[10],p[10],n;
  594.  
  595. int max(int a,int b)
  596. {
  597. return a>b?a:b;
  598. }
  599. int knap(int i,int m)
  600. {
  601. if(i==n) return w[i]>m?0:p[i];
  602. if(w[i]>m) return knap(i+1,m);
  603. return max(knap(i+1,m),knap(i+1,m-w[i])+p[i]);
  604. }
  605. int main()
  606. {
  607. int m,i,max_profit;
  608. printf("\nEnter the no. of objects:");
  609. scanf("%d",&n);
  610. printf("\nEnter the knapsack capacity:");
  611. scanf("%d",&m);
  612. printf("\nEnter profit followed by weight:\n");
  613. for(i=1;i<=n;i++)
  614. scanf("%d %d",&p[i],&w[i]);
  615. max_profit=knap(1,m);
  616. printf("\nMax profit=%d",max_profit); return 0;
  617. }
  618.  
  619.  
  620. Output:
  621. Enter the no. of objects:4
  622. Enter the knapsack capacity:6 Enter profit followed by weight:
  623. 78 2
  624. 45 3
  625. 92 4
  626. 71 5
  627. Max profit = 170
  628.  
  629.  
  630.  
  631.  
  632.  
  633.  
  634.  
  635.  
  636.  
  637.  
  638.  
  639.  
  640.  
  641.  
  642.  
  643.  
  644.  
  645.  
  646.  
  647.  
  648.  
  649.  
  650.  
  651. 7. Design and implement C/C++ Program to solve discrete Knapsack and continuous Knapsack problems using greedy approximation method.
  652.  
  653.  
  654.  
  655.  
  656. PROGRAM:
  657. #include <stdio.h>
  658. #define MAX 50
  659. int p[MAX], w[MAX], x[MAX]; double maxprofit; int n, m, i;
  660. void greedyKnapsack(int n, int w[], int p[], int m) { double ratio[MAX];
  661. // Calculate the ratio of profit to weight for each item
  662. for (i = 0; i < n; i++)
  663. {
  664. ratio[i] = (double)p[i] / w[i];
  665. }
  666. // Sort items based on the ratio in non-increasing order
  667. for (i = 0; i < n - 1; i++)
  668. {
  669. for (int j = i + 1; j < n; j++)
  670. {
  671. if (ratio[i] < ratio[j])
  672. {
  673. double temp = ratio[i];
  674. ratio[i] = ratio[j];
  675. ratio[j] = temp;
  676. int temp2 = w[i];
  677. w[i] = w[j];
  678. w[j] = temp2;
  679. temp2 = p[i];
  680. p[i] = p[j];
  681. p[j] = temp2;
  682. }
  683. }
  684. }
  685. int currentWeight = 0;
  686. maxprofit = 0.0;
  687. // Fill the knapsack with items
  688. for (i = 0; i < n; i++)
  689. {
  690. if (currentWeight + w[i] <= m)
  691. {
  692. x[i] = 1; // Item i is selected
  693. currentWeight += w[i];
  694. maxprofit += p[i];
  695. }
  696. else {
  697. // Fractional part of item i is selected
  698. x[i] = (m - currentWeight) / (double)w[i];
  699. maxprofit += x[i] * p[i];
  700. break;
  701. }
  702. }
  703. printf("Optimal solution for greedy method: %.1f\n", maxprofit);
  704. printf("Solution vector for greedy method: ");
  705. for (i = 0; i < n; i++)
  706. printf("%d\t", x[i]);
  707. }
  708. int main()
  709. {
  710. printf("Enter the number of objects: ");
  711. scanf("%d", &n);
  712. printf("Enter the objects' weights: ");
  713. for (i = 0; i < n; i++)
  714. scanf("%d", &w[i]);
  715. printf("Enter the objects' profits: ");
  716. for (i = 0; i < n; i++)
  717. scanf("%d", &p[i]);
  718. printf("Enter the maximum capacity: ");
  719. scanf("%d", &m);
  720. greedyKnapsack(n, w, p, m);
  721.  
  722. return 0;
  723. }
  724.  
  725.  
  726. Output:
  727. Enter the number of objects: 4
  728. Enter the objects' weights: 56 78 98 76
  729. Enter the objects' profits: 34 56 78 45
  730. Enter the maximum capacity: 100
  731. Solution vector for greedy method: 1 0 0 0
  732.  
  733. 8. Design and implement C/C++ Program to find a subset of a given set S = {sl , s2,.....,sn} of n positive integers whose sum is equal to a given positive integer d.
  734.  
  735.  
  736.  
  737.  
  738. Program:
  739. #include<stdio.h>
  740. // #include<conio.h> #define MAX 10 int s[MAX],x[MAX],d;
  741. void sumofsub(int p,int k,int r)
  742. {
  743. int i;
  744. x[k]=1;
  745. if((p+s[k])==d)
  746. {
  747. for(i=1;i<=k;i++)
  748. if(x[i]==1)
  749. printf("%d ",s[i]);
  750. printf("\n");
  751. }
  752. else
  753. if(p+s[k]+s[k+1]<=d)
  754. sumofsub(p+s[k],k+1,r-s[k]);
  755. if((p+r-s[k]>=d) && (p+s[k+1]<=d))
  756. {
  757. x[k]=0;
  758. sumofsub(p,k+1,r-s[k]);
  759. }
  760. }
  761. int main()
  762. {
  763. int i,n,sum=0;
  764. printf("\nEnter the n value:");
  765. scanf("%d",&n);
  766. printf("\nEnter the set in increasing order:");
  767. for(i=1;i<=n;i++)
  768. scanf("%d",&s[i]);
  769. printf("\nEnter the max subset value:"); scanf("%d",&d);
  770. for(i=1;i<=n;i++)
  771. sum=sum+s[i];
  772.  
  773. if(sum<d || s[1]>d)
  774. printf("\nNo subset possible");
  775. else
  776. sumofsub(0,1,sum); return 0;
  777. }
  778.  
  779.  
  780.  
  781.  
  782.  
  783.  
  784.  
  785.  
  786.  
  787.  
  788.  
  789.  
  790.  
  791.  
  792.  
  793.  
  794.  
  795.  
  796.  
  797.  
  798.  
  799.  
  800.  
  801.  
  802.  
  803.  
  804.  
  805.  
  806.  
  807.  
  808.  
  809. Output:
  810. Enter the n value:9
  811. Enter the set in increasing order:1 2 3 4 5 6 7 8 9
  812. Enter the max subset value:9
  813. 1 2 6
  814. 1 3 5
  815. 1 8
  816. 2 3 4
  817. 2 7
  818. 3 6
  819. 4 5 9
  820.  
  821.  
  822.  
  823.  
  824.  
  825.  
  826.  
  827.  
  828.  
  829.  
  830.  
  831.  
  832.  
  833.  
  834.  
  835. 9. Design and implement C/C++ Program to sort a given set of n integer elements using Selection Sort method and compute its time complexity. Run the program for varied values of n> 5000 and record the time taken to sort. 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.
  836.  
  837.  
  838. Program:
  839. #include<stdio.h>
  840. #include<conio.h>
  841. #include<time.h> #include<dos.h> void selsort(int a[],int n)
  842. {
  843. int i,j,small,pos,temp;
  844. for(j=0;j<n-1;j++)
  845. {
  846. small=a[j];
  847. pos=j;
  848. for(i=j+1;i<n;i++)
  849. {
  850. if(a[i]<small)
  851. {
  852. small=a[i]; pos=i;
  853. }
  854. }
  855. temp=a[j]; a[j]=small;
  856. a[pos]=temp;
  857. }
  858. }
  859. void main()
  860. {
  861. int a[10],i,n;
  862. clock_t start,end; float dura;
  863. clrscr();
  864. printf("\nEnter the n value:");
  865. scanf("%d",&n);
  866. printf("\nEnter the array:");
  867. scanf("%d",&a[i]);
  868. for(i=0;i<n;i++)
  869. start=clock();
  870. selsort(a,n);
  871. delay(100);
  872. end=clock();
  873. dura=(end-start)/CLK_TCK; printf("\nTime taken is:%f",dura); printf("\nSorted array is:"); for(i=0;i<n;i++)
  874. printf("%d ",a[i]); getch();
  875. }
  876.  
  877.  
  878.  
  879.  
  880.  
  881.  
  882.  
  883.  
  884.  
  885.  
  886.  
  887.  
  888.  
  889.  
  890.  
  891.  
  892.  
  893.  
  894.  
  895.  
  896.  
  897. Output:
  898. Enter the n value:5
  899. Enter the array:10 2 3 15 12
  900. Time taken is:0.109890
  901. Sorted array is:2 3 10 12 15
  902.  
  903. Graph Plotting code:
  904. import matplotlib.pyplot as plt
  905. # data collected
  906. n_values = [6000, 7000, 8000, 9000, 10000]
  907. time_taken = [0.031000, 0.034000, 0.047000, 0.052000, 0.077000] # replace with actual times recorded
  908. plt.plot(n_values, time_taken, marker='o')
  909. plt.title('Selection Sort Time Complexity')
  910. plt.xlabel('Number of Elements (n)')
  911. plt.ylabel('Time taken (seconds)')
  912. plt.grid(True)
  913. plt.show()
  914.  
  915.  
  916.  
  917.  
  918.  
  919.  
  920. 10. Design and implement C/C++ Program to sort a given set of n integer elements using Quick Sort method and compute its time complexity. Run the program for varied values of n> 5000 and record the time taken to sort. 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.
  921.  
  922.  
  923.  
  924.  
  925.  
  926.  
  927.  
  928.  
  929.  
  930.  
  931.  
  932.  
  933.  
  934.  
  935.  
  936.  
  937.  
  938.  
  939.  
  940.  
  941.  
  942.  
  943.  
  944. #include <stdio.h>
  945. #include <stdlib.h>
  946. #include <time.h>
  947. // Function to swap two elements
  948. void swap(int* a, int* b)
  949. {
  950. int t = *a;
  951. *a = *b;
  952. *b = t;
  953. }
  954. // Partition function for Quick Sort
  955. int partition(int arr[], int low, int high)
  956. {
  957. int pivot = arr[high]; // Pivot element
  958. int i = (low - 1); // Index of smaller element
  959.  
  960. for (int j = low; j <= high - 1; j++)
  961. {
  962. if (arr[j] < pivot)
  963. {
  964. i++; // Increment index of smaller element
  965. swap(&arr[i], &arr[j]);
  966. }
  967. }
  968. swap(&arr[i + 1], &arr[high]);
  969. return (i + 1);
  970. }
  971. // Quick Sort function
  972. void quickSort(int arr[], int low, int high)
  973. {
  974. if (low < high)
  975. {
  976. int pi = partition(arr, low, high);
  977. // Recursively sort elements before and after partition
  978. quickSort(arr, low, pi - 1);
  979. quickSort(arr, pi + 1, high);
  980. }
  981. }
  982. // Function to generate random numbers
  983. void generateRandomNumbers(int arr[], int n)
  984. {
  985. for (int i = 0; i < n; i++)
  986. {
  987. arr[i] = rand() % 100000; // Generate random numbers between 0 and 99999
  988. }
  989. }
  990. int main()
  991. {
  992. int n;
  993. printf("Enter number of elements: ");
  994. scanf("%d", &n); // Read the number of elements from the user
  995. if (n <= 5000)
  996. {
  997. printf("Please enter a value greater than 5000\n");
  998. return 1; // Exit if the number of elements is not greater than 5000
  999. }
  1000. // Allocate memory for the array
  1001. int *arr = (int *)malloc(n * sizeof(int));
  1002. if (arr == NULL)
  1003. {
  1004. printf("Memory allocation failed\n");
  1005. return 1; // Exit if memory allocation fails
  1006. }
  1007. // Generate random numbers and store them in the array
  1008. generateRandomNumbers(arr, n);
  1009. // Measure the time taken to sort the array
  1010. clock_t start = clock();
  1011. quickSort(arr, 0, n - 1);
  1012. clock_t end = clock();
  1013. // Calculate and print the time taken to sort the array
  1014. double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
  1015. printf("Time taken to sort %d elements: %f seconds\n", n, time_taken);
  1016. // Free the allocated memory
  1017. free(arr);
  1018. return 0;
  1019. }
  1020.  
  1021.  
  1022.  
  1023. Output:
  1024. Enter number of elements: 10000
  1025. Time taken to sort 10000 elements: 0.0000 seconds
  1026.  
  1027. ********************************************************************
  1028.  
  1029.  
  1030. Enter number of elements: 20000
  1031. Time taken to sort 20000 elements: 0.015000 seconds
  1032.  
  1033. ********************************************************************
  1034.  
  1035.  
  1036. Enter number of elements: 30000
  1037. Time taken to sort 30000 elements: 0.011000 seconds
  1038.  
  1039. ********************************************************************
  1040.  
  1041.  
  1042. Enter number of elements: 35000
  1043.  
  1044.  
  1045.  
  1046.  
  1047.  
  1048.  
  1049.  
  1050.  
  1051.  
  1052.  
  1053.  
  1054.  
  1055.  
  1056.  
  1057.  
  1058. Graph plotting code:
  1059. import matplotlib.pyplot as plt
  1060. # Example data collected
  1061. n_values = [10000, 20000, 30000, 35000, 50000]
  1062. time_taken = [0.0000, 0.015000, 0.011000, 0.003000, 0.015000] # replace with actual times recorded
  1063. plt.plot(n_values, time_taken, marker='o')
  1064. plt.title('Quick Sort Time Complexity')
  1065. plt.xlabel('Number of Elements (n)')
  1066. plt.ylabel('Time taken (seconds)')
  1067. plt.grid(True)
  1068. plt.show()
  1069.  
  1070.  
  1071.  
  1072.  
  1073.  
  1074.  
  1075.  
  1076.  
  1077.  
  1078. 11. Design and implement C/C++ Program to sort a given set of n integer elements using Merge Sort method and compute its time complexity. Run the program for varied values of n> 5000, and record the time taken to sort. 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.
  1079.  
  1080.  
  1081.  
  1082.  
  1083.  
  1084.  
  1085.  
  1086.  
  1087.  
  1088.  
  1089.  
  1090.  
  1091.  
  1092.  
  1093.  
  1094.  
  1095.  
  1096.  
  1097.  
  1098.  
  1099.  
  1100.  
  1101.  
  1102.  
  1103. PROGRAM:
  1104.  
  1105. #include <stdio.h>
  1106. #include <stdlib.h>
  1107. #include <time.h>
  1108. // Function to merge two sorted arrays
  1109. void merge(int arr[], int left, int mid, int right)
  1110. {
  1111. int i, j, k;
  1112. int n1 = mid - left + 1;
  1113. int n2 = right - mid;
  1114. int *L = (int *)malloc(n1 * sizeof(int));
  1115. int *R = (int *)malloc(n2 * sizeof(int));
  1116. for (i = 0; i < n1; i++)
  1117. L[i] = arr[left + i];
  1118. for (j = 0; j < n2; j++)
  1119. R[j] = arr[mid + 1 + j];
  1120. i = 0;
  1121. j = 0;
  1122. k = left;
  1123. while (i < n1 && j < n2)
  1124. {
  1125. if (L[i] <= R[j])
  1126. {
  1127. arr[k] = L[i];
  1128. i++;
  1129. }
  1130. else
  1131. {
  1132. arr[k] = R[j];
  1133. j++;
  1134. }
  1135. k++;
  1136. }
  1137. while (i < n1)
  1138. {
  1139. arr[k] = L[i];
  1140. i++;
  1141. k++;
  1142. }
  1143. while (j < n2)
  1144. {
  1145. arr[k] = R[j];
  1146. while (j < n2)
  1147. {
  1148. arr[k] = R[j];
  1149. j++;
  1150. k++;
  1151. }
  1152. free(L);
  1153. free(R);
  1154. }
  1155. // Function to implement Merge Sort
  1156. void mergeSort(int arr[], int left, int right)
  1157. {
  1158. if (left < right)
  1159. {
  1160. int mid = left + (right - left) / 2;
  1161. mergeSort(arr, left, mid);
  1162. mergeSort(arr, mid + 1, right);
  1163. merge(arr, left, mid, right);
  1164. }
  1165. }
  1166. // Function to generate random integers
  1167. void generateRandomArray(int arr[], int n)
  1168. {
  1169. for (int i = 0; i < n; i++)
  1170. arr[i] = rand() % 100000; // Generate random integers between 0 and 99999
  1171. }
  1172. int main()
  1173. {
  1174. int n;
  1175. printf("Enter the number of elements: ");
  1176. scanf("%d", &n);
  1177.  
  1178. if (n <= 5000)
  1179. {
  1180. printf("Please enter a value greater than 5000\n");
  1181. return 1; // Exit if the number of elements is not greater than 5000
  1182. }
  1183. int *arr = (int *)malloc(n * sizeof(int));
  1184. if (arr == NULL)
  1185. {
  1186. printf("Memory allocation failed\n");
  1187. return 1; // Exit if memory allocation fails
  1188. }
  1189. generateRandomArray(arr, n);
  1190. // Repeat the sorting process multiple times to increase duration for timing
  1191. clock_t start = clock();
  1192. for (int i = 0; i < 1000; i++)
  1193. for (int i = 0; i < 1000; i++)
  1194. {
  1195. mergeSort(arr, 0, n - 1);
  1196. }
  1197. clock_t end = clock();
  1198. // Calculate the time taken for one iteration
  1199. double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC / 1000.0;
  1200. printf("Time taken to sort %d elements: %f seconds\n", n, time_taken);
  1201. free(arr);
  1202. return 0;
  1203. }
  1204.  
  1205.  
  1206.  
  1207.  
  1208.  
  1209.  
  1210.  
  1211.  
  1212.  
  1213.  
  1214.  
  1215. Output:
  1216. Enter number of elements: 6000
  1217. Time taken to sort 6000 elements: 0.000709 seconds
  1218.  
  1219. ********************************************************************
  1220.  
  1221. Enter number of elements: 7000
  1222. Time taken to sort 7000 elements: 0.000752 seconds
  1223.  
  1224. ********************************************************************
  1225. Enter number of elements: 8000
  1226. Time taken to sort 8000 elements: 0.000916 seconds
  1227.  
  1228. ********************************************************************
  1229. ********************************************************************
  1230.  
  1231. Enter number of elements: 9000
  1232. Time taken to sort 9000 elements: 0.001493 seconds
  1233.  
  1234. ********************************************************************
  1235.  
  1236. Enter number of elements: 10000
  1237. Time taken to sort 10000 elements: 0.001589 seconds
  1238.  
  1239. ********************************************************************
  1240.  
  1241. Enter number of elements: 11000
  1242. Time taken to sort 11000 elements: 0.002562 seconds
  1243.  
  1244. ********************************************************************
  1245.  
  1246. Enter number of elements: 12000
  1247. Time taken to sort 12000 elements: 0.001944 seconds
  1248.  
  1249. ********************************************************************
  1250.  
  1251. Enter number of elements: 13000
  1252. Time taken to sort 13000 elements: 0.002961 seconds
  1253.  
  1254. ********************************************************************
  1255.  
  1256. Enter number of elements: 15000
  1257. Time taken to sort 15000 elements: 0.003563 seconds
  1258.  
  1259.  
  1260.  
  1261.  
  1262.  
  1263.  
  1264. Graph plotting code:
  1265. import matplotlib.pyplot as plt
  1266. # data collected (replace with actual data)
  1267. n_values = [6000, 7000, 8000, 9000, 10000, 11000, 12000, 13000, 15000]
  1268. time_taken = [0.000709, 0.000752, 0.000916, 0.001493, 0.001589, 0.002562, 0.001944, 0.002961, 0.003563] # Replace with actual times recorded
  1269. plt.plot(n_values, time_taken, marker='o')
  1270. plt.title('Merge Sort Time Complexity')
  1271. plt.xlabel('Number of Elements (n)')
  1272. plt.ylabel('Time taken (seconds)')
  1273. plt.grid(True)
  1274. plt.show()
  1275.  
  1276.  
  1277.  
  1278.  
  1279.  
  1280.  
  1281.  
  1282.  
  1283. 12 Design and implement C/C++ Program for N Queen's problem using Backtracking.
  1284.  
  1285.  
  1286.  
  1287.  
  1288.  
  1289.  
  1290.  
  1291.  
  1292.  
  1293.  
  1294.  
  1295. Program:
  1296.  
  1297. #include<stdio.h>
  1298. #include<conio.h>
  1299. #include<stdlib.h>
  1300. #define MAX 50
  1301. int can_place(int c[],int r)
  1302. {
  1303. int i;
  1304. for(i=0;i<r;i++)
  1305. if(c[i]==c[r] || (abs(c[i]-c[r])==abs(i-r)))
  1306. return 0; return 1;
  1307. }
  1308. void display(int c[],int n)
  1309. {
  1310. int i,j;
  1311. char cb[10][10];
  1312. for(i=0;i<n;i++)
  1313. for(j=0;j<n;j++)
  1314. cb[i][j]='-';
  1315. for(i=0;i<n;i++)
  1316. cb[i][c[i]]='Q'; for(i=0;i<n;i++)
  1317. for(j=0;j<n;j++)
  1318. cb[i][j]='-'; for(i=0;i<n;i++)
  1319. cb[i][c[i]]='Q';
  1320. for(i=0;i<n;i++)
  1321. {
  1322. for(j=0;j<n;j++)
  1323. printf("%c",cb[i][j]); printf("\n");
  1324. }
  1325. }
  1326. void n_queens(int n)
  1327. {
  1328. int r;
  1329. int c[MAX];
  1330. c[0]=-1; r=0;
  1331. while(r>=0)
  1332. {
  1333. c[r]++;
  1334. while(c[r]<n && !can_place(c,r))
  1335. c[r]++; if(c[r]<n)
  1336. { if(r==n-1) { display(c,n); printf("\n\n");
  1337. }
  1338. else
  1339. {
  1340. r++;
  1341. c[r]=-1;
  1342. }
  1343. }
  1344. else r--;
  1345. }
  1346. }
  1347. void main()
  1348. {
  1349. int n;
  1350. clrscr();
  1351. printf("\nEnter the no. of queens:"); scanf("%d",&n);
  1352. n_queens(n);
  1353. getch();
  1354. }
  1355.  
  1356.  
  1357. Output:
  1358. Enter the no of queens :4
  1359. -Q—
  1360. ---Q
  1361. Q---
  1362. --Q-
  1363.  
  1364. --Q-
  1365. Q---
  1366. ---Q
  1367. -Q--
  1368.  
  1369.  
Advertisement
Add Comment
Please, Sign In to add comment