Discrete math

1. How many distinct ways are there to arrange 6 different people around a round table, where arrangements obtainable by rotation are considered the same?

120

2. Six different people are to be seated around a round table. Among the seats, two special seats are equipped with microphones. In how many different ways can the people be seated if: (1) arrangements that differ only by rotation are considered the same; (2) the two special seats must be occupied by any two people?

120

3. Six different people {A,B,C,D,E,F} are to be seated around a round table. There is exactly one special seat where only A can sit. In how many different ways can the people be seated if arrangements that differ only by rotation are considered the same?

120

4. A company has 15 identical laptops to assign to 5 departments. In how many ways can this be done if no department may receive more than 6 laptops?

1451

5. How many ways are there to arrange 5 male students and 4 female students in a row such that no two female students stand next to each other?

43200

6. How many ways are there to choose 5 elements from the set {1,2,…,10} such that at least two selected elements are consecutive?

246

7. How many ways are there to distribute 18 identical candies among 6 children so that no child receives more than 7 candies?

15946

8. How many ways are there to distribute 30 identical cookies among 10 students so that each student receives at least 2 and at most 5 cookies?

44803

9. How many ways are there to divide 25 identical balls among 8 boxes such that each box contains at most 6 balls?

392848

10. How many binary strings of length 5 do not contain two consecutive 1s?

13

11. Each menu for a meal at restaurant ABC consists of 3 dishes: appetizer, main dish and dessert. The restaurant has 5 types of appetizer, 3 types of main dish and 4 types of dessert. How many ways can a person choose the menu?

60

12. How many ways are there to choose a class monitor and a secretary from a class of 20 students? The secretary and the class monitor must be two different students.

380

13. Consider a directed weighted graph with V={1,2,3,4,5} and weight matrix W=[[0,10,3,0,0],[0,0,1,2,0],[0,4,0,8,2],[0,0,0,0,7],[0,0,0,9,0]]. Using Dijkstra's algorithm, find the shortest-path distance from vertex 1 to all remaining vertices. Determine the order of vertices in which the algorithm finds the shortest path from 1.

3524

14. Consider a directed weighted graph with V={1,2,3,4,5} and weight matrix W=[[0,10,3,0,0],[0,0,1,2,0],[0,4,0,8,2],[0,0,0,0,7],[0,0,0,9,0]]. Using Dijkstra's algorithm, find the shortest-path distance from vertex 2 to all remaining vertices. What is the third vertex where the algorithm finds the shortest path from 2?

5

15. Consider the undirected graph G=(V,E) with V={A,B,C,D,E} and E={AB,AC,BC,BD,CD,DE}. Does G have an Euler path?

No

16. Consider the undirected graph G=(V,E) with V={A,B,C,D} and E={AB,BC,CD,DA,AC,BD}. Does G have an Euler cycle?

No

17. Consider the undirected graph G=(V,E) with V={A,B,C,D} and E={AB,BC,CD,DA}. Does G have an Euler cycle?

Yes

18. Let G=K2,3, a complete bipartite graph with bipartition {a,b} and {c,d,e}. Let H have edge set E(H)={{1,3},{1,4},{1,5},{2,3},{2,4},{2,5}}. Which mapping is an isomorphism from G to H?

a->1,b->2,c->3,d->4,e->5

19. Determine which graph is represented by the following weight matrix: rows/columns 1..6; row 1 = [0,14,6,0,0,0], row 2 = [0,0,0,0,0,0], row 3 = [0,0,0,3,3,4], row 4 = [4,0,0,0,0,2], row 5 = [0,9,0,0,0,6], row 6 = [0,0,0,0,0,0].

bottom left

20. An undirected simple graph has 20 vertices. What is the minimum number of edges needed to guarantee that it contains a cycle?

20

21. Consider an undirected graph G=(V,E), where V={1,2,3,4,5,6} and E={(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6)}. Is G a complete graph?

No

22. Given an undirected graph G=(V,E) where V={1,2,3,4,5,6} and E={(1,3),(1,4),(1,5),(1,6),(2,5),(2,6),(3,4),(3,5),(5,6)}. Is the vertex sequence 3,1,2,5,6 a path in G?

No

23. Given an undirected graph G=(V,E) where V={1,2,3,4,5,6} and E={(1,4),(1,6),(2,5),(2,6),(3,4),(3,5),(3,6)}. Is G a bipartite graph?

Yes

24. Undirected simple graph G with vertex set V={1,2,…,10}. For every pair of vertices, there is an edge connecting them. What is the number of simple paths starting from vertex 1, passing through all remaining vertices, and ending at vertex 10?

40320

25. Apply Depth-First-Search algorithm (DFS) starting from vertex B on the given graph. When traversing vertices, consider lexicographical order A, B, C, D, E, F. When the algorithm terminates, what is the path from vertex B to vertex F on the DFS tree?

B --> A --> C --> F

26. A knapsack has capacity 10 units. There are six items, each selected at most once. Item 1: weight 2, value 6; item 2: weight 2, value 3; item 3: weight 6, value 5; item 4: weight 5, value 4; item 5: weight 4, value 6; item 6: weight 3, value 5. Determine the maximum total value without exceeding capacity.

17

27. There are 4 item types with weights 5, 3, 2, 4 and values 10, 5, 3, 6. Choose a nonnegative integer number of each type so that total weight <= 14 and total value is maximized. What is the maximum total value?

26

28. Consider a graph with 5 vertices V={1,2,3,4,5}. Weight matrix W=[[0,2,0,6,0],[2,0,3,8,5],[0,3,0,0,7],[6,8,0,0,9],[0,5,7,9,0]]. Using Prim's algorithm starting from vertex 1, what is the fourth edge of the MST found by the algorithm?

14

29. Consider a graph with 5 vertices V={1,2,3,4,5}. W=[[0,2,0,6,0],[2,0,3,8,5],[0,3,0,0,7],[6,8,0,0,9],[0,5,7,9,0]]. What is the total weight of the Minimum Spanning Tree (MST) of the given graph?

16

30. Consider the flow network with capacities s->a=10, s->b=5, a->b=15, a->t=10, b->t=10. Which of the following pairs of sets (S,T) is the minimum cut of this network?

S={s} and T={a,b,t}

31. Consider the network with capacities s->a=10, s->b=5, a->b=15, a->t=10, b->t=10. The maximum flow value of the network is:

15

32. A delivery person starts from the store (point 1), visits delivery points 2, 3, and 4 exactly once, then returns to the store. Find the minimum total distance for cost matrix: [0 3 2 4; 1 0 5 3; 2 3 0 7; 1 1 3 0].

9

33. Using the same 4-point cost matrix [0 3 2 4; 1 0 5 3; 2 3 0 7; 1 1 3 0], find the route with the minimum total distance.

1-3-2-4-1

34. 1001 samples are assigned to 10 clusters. What is the minimum number of samples in the largest cluster?

101

35. A box contains red, blue, and green balls. What is the minimum number of balls that must be drawn to guarantee that two balls have the same color? This statement is:

4

36. A drawer contains socks of only 3 different colors. What is the minimum number of socks that must be selected to guarantee that at least 5 socks are of the same color?

13

37. Among any 10 integers, there exist two integers whose difference is divisible by 9. This statement is:

Always true

38. What is the minimum number of students required in a class to guarantee that at least 4 students were born in the same month?

37

39. Given an undirected graph G where all edges have the same weight. If we want to find the shortest path between any two vertices of the graph, which algorithm is the most efficient?

Breadth First Search (BFS)

40. Given directed graph G with edges 1->2, 1->3, 2->5, 2->4, 3->4, 3->6, 4->5, 4->6. Which of the following graphs is not a subgraph of G?

middle

41. Given the directed graph G shown in the PDF, which of the following is not the topological order of G?

3 2 4 1 6 5

42. How many vertices does a tree with e edges have?

e+1

43. Which statement(s) below is/are correct?

If G is a tree, then there is only one path between every pair of vertices.