Discrete mathematics introductionSlide.pptx

it is intro to discrete math

1. 2 + 2 + Discreate Math Mini - Project 1 Supervised by Dr. Mohammad Salah Uddin

2. 2 + 2 + 2 + Good Afternoon 2

3. Work Details 3 C Program Undirected Graph Adjacency Matrix C omputational Time F(n) F(n)

4. 2 + 2 + 2 + Good Afternoon 4 Good Morning Good Day Happy Morning

5. 5 Vertices People, Pages, Photo, Comments, Places, Group Edges User Posting a video, Your Greeting to your beloved

6. 2 + Graph Used Facebook Graph API Google Knowledge Graph Flight Network Recommendation Engines. Path Optimization Algorithms. Scientific Computations. 6

7. 2 + Random graph initialize int **graph = (int **)malloc(n * sizeof (int *)); // Dynamic space allocation // for (i=0; i<n; i++) graph[i] = (int *)malloc(n * sizeof (int)); for(i=0; i<n; i++ ) for(j=i+1; j<n; j++ ) graph[i][j] = graph[j][i] = rand()%2; // Random undirected graph initialize // 7

8. 2 + Calculating ToTal Edge & Degree int total_edges = 0; for(i = 0 ; i < n ; i++) for(j = i + 1 ; j < n ; j++ ) if (graph[i][j] == 1) total_edges ++; // Counting edges // int total_degrees = 0; for(i = 0 ; i < n ; i++ ) for(j = 0 ; j < n ; j++ ) if (graph[i][j] == 1) total_degrees ++; // Computing degrees // 8

9. 2 + Verifying the handshaking theorem int flag; if( total_degrees == 2 * total_edges ) // Verifying Handshaking theorem // flag = 1; else flag = 0; if(flag == 1) // Printing The Verification of Handshaking theorem // printf ("\t\ tIt holds Handshaking theorem! \n"); else printf ("\t\ tIt does not holds Handshaking theorem! \n"); 9

10. 2 + Calculation of Time struct timespec start, end; clock_gettime (CLOCK_REALTIME, &start ); // Start time for computation // clock_gettime (CLOCK_REALTIME, &end); // End time for computation // double nanos = (double)( end.tv_nsec - start.tv_nsec ); double ms = nanos/1000000; printf ("\t\ tComputational time = %.2f ms. \n\n\n", ms ); // Showing Computational Time // 10

11. Add a Footer YOUR TITLE GOES HERE Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut gravida eros erat. Proin a tellus sed risus lobortis sagitti 11 2 + O utput Values for 1000, 2000, 3000, 4000, 5000 Vertices

12. Title YOUR TITLE GOES HERE Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut gravida eros erat. Proin a tellus sed risus lobortis sagittis eu quis est. Duis ut aliquam nisi. Suspendisse vehicla mi diam, sit amet lacinia massa sodales ac. Fusce condimentum egestas nunc a YOUR TITLE GOES HERE Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut gravida eros erat. Proin a tellus sed risus lobortis sagittis eu quis est. Duis ut aliquam nisi. Suspendisse vehicula mi diam, sit amet lacinia massa sodales ac. Fusce condimentum egestas nunc a Add a Footer 12

13. TITLE GOES HERE SUBTITLE GOES HERE Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut gravida eros erat. Proin a tellus sed risus lobortis sagittis eu quis est. Duis ut aliquam nisi. Suspendisse vehicula mi diam, sit amet lacinia massa sodales ac. Fusce condimentum egestas nunc a maximus. Quisque et orci purus. Proin dolor mi, ultrices sit amet ipsum placerat, congue mattis turpis. Donec vestibulum eros eget mauris dignissim, ut ultricies dolor viverra. Phasellus efficitur ante nec sem convallis, in ornare est accumsan. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut gravida eros erat. Proin a tellus sed risus lobortis sagittis eu quis est. Add a Footer 13 Equation :- 6x10 6 X 2 + 0.029X - 23.51 f (n) = 6x10 6 n 2 + 0.029n - 23.51 For f(n)= Og (n) f(n) ≤ c.g (n) => 6x10 6 n 2 + 0.029n - 23.51 ≤ 6x10 6 n 2 + 0.029 n 2 - 23.51 n 2 [n ≤ n 2 ,1 ≤ n 2 ] 6x10 6 n 2 + 0.029n - 23.51 ≤ 5.99998x10 6 n 2 f(n) = 6x10 6 n 2 + 0.029n - 23.51  O( n 2 )

14. TITLE GOES HERE SUBTITLE GOES HERE Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut gravida eros erat. Proin a tellus sed risus lobortis sagittis eu quis est. Duis ut aliquam nisi. Suspendisse vehicula mi diam, sit amet lacinia massa sodales ac. Fusce condimentum egestas nunc a maximus. Quisque et orci purus. Proin dolor mi, ultrices sit amet ipsum placerat, congue mattis turpis. Donec vestibulum eros eget mauris dignissim, ut ultricies dolor viverra. Phasellus efficitur ante nec sem convallis, in ornare est accumsan. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut gravida eros erat. Proin a tellus sed risus lobortis sagittis eu quis est. Add a Footer 14 Your text here For assignment, summation, , addition, divition we take contant . Because they are not dependent on n. The for loop will be executed (n – 1) times. For each for loop, two comparisons will be done. One more comparison will be needed to exit the for loop. Therefore, exactly 2(n – 1) + 1 = 2n – 1 comparisons are used. Hence, the worst-case time complexity of the algorithm is 2n – 1  O(n). For each nested loop execution will be n*(2n-1) times. Hence, the worst-case time complexity of the algorithm is 2 n 2 – n  O( n 2 ). B ecause the second loop will execute n time for every first n time loop.

15. TITLE GOES HERE SUBTITLE GOES HERE Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut gravida eros erat. Proin a tellus sed risus lobortis sagittis eu quis est. Duis ut aliquam nisi. Suspendisse vehicula mi diam, sit amet lacinia massa sodales ac. Fusce condimentum egestas nunc a maximus. Quisque et orci purus. Proin dolor mi, ultrices sit amet ipsum placerat, congue mattis turpis. Donec vestibulum eros eget mauris dignissim, ut ultricies dolor viverra. Phasellus efficitur ante nec sem convallis, in ornare est accumsan. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut gravida eros erat. Proin a tellus sed risus lobortis sagittis eu quis est. Add a Footer 15 Your text here int total_edges = 0; for(i = 0 ; i < n ; i++) for(j = i + 1 ; j < n ; j++) if (graph[i][j] == 1) total_edges++; // Counting edges // int total_degrees = 0; for(i = 0 ; i < n ; i++ ) for(j = 0 ; j < n ; j++) if (graph[i][j] == 1) total_degrees++; // Computing degrees // int flag; if(total_degrees == 2 * total_edges) // Verifying Handshaking theorem // flag = 1; else flag = 0; For assignment k 1 For nested loop n(2n-1) For If statement k 2 For Summation and assignment k 3 T otal = k 1 + k n(2n-1) + k 2 + k 3 For assignment k 4 For nested loop n(2n-1) For If statement k k 5 For Summation and assignment k 6 T otal = k 4 + k 7 n(2n-1) + k 5 + k 6 For If statement k 8 T otal = k 8 For total time = k 1 + k n(2n-1) + k 2 + k 4 + k 7 n(2n-1) + k 5 + k 6 + k 8 = k + k ( 2 n 2 – n )  0( n 2 ) [After omitting constant and taking most determine value ]

16. TITLE GOES HERE SUBTITLE GOES HERE Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut gravida eros erat. Proin a tellus sed risus lobortis sagittis eu quis est. Duis ut aliquam nisi. Suspendisse vehicula mi diam, sit amet lacinia massa sodales ac. Fusce condimentum egestas nunc a maximus. Quisque et orci purus. Proin dolor mi, ultrices sit amet ipsum placerat, congue mattis turpis. Donec vestibulum eros eget mauris dignissim, ut ultricies dolor viverra. Phasellus efficitur ante nec sem convallis, in ornare est accumsan. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut gravida eros erat. Proin a tellus sed risus lobortis sagittis eu quis est. Add a Footer 16 Your text here Theoretically we got T(n)  0( n 2 ) for the nested loop. F rom the graph equation we got 5.99998x10 6 n 2 . Which is T(n)  k * n 2  0( n 2 ). Compering this with statistical result verifies the claim .

17. 2 + 2 + THANK YOU 17