Discrete Structure BSCS 2nd MID TERM Past paper 2016 UOS
Transcript of the Paper:
Department of Computer Science & IT
University of Sargodha
Spring 2016
Program: BS(CS) 2nd [R+S]
Date: Monday, April 11, 2016
Roll No: BSCSH514
Mid Term Paper
Duration: 90 Min
Total Marks: 30
Objective
- I. Differentiate between Euler and Hamiltonian path. [2]
II. Define Bipartite Graph with example. [2]
III. What is the graph coloring problem? Explain with example. [2]
IV. Find the symmetric difference of {2, 4, 6} and {2, 3, 4}. [2]
V. Let A = {eggs, milk, corn} and B = {cows, goats, hens}
Define a relation R from A to B by (a, b) ∈ R if a is produced by b. [2]
Subjective
- State which rule of inference is used in the argument:
If it rains today, then we will not have a barbecue today. If we do not have a barbecue today, then we will have a barbecue tomorrow. Therefore, if it rains today, then we will have a barbecue tomorrow. [4] - Prove that 2^1 divides 47^n+1 + 52^n-1 whenever n is a positive integer. [4]
- Find S = ∑ from k=50 to 100 of (k)^2 [4]
- Determine a railway network of minimal cost for the cities in the following graph using Kruskal’s and Prim’s algorithm. Do these algorithms generate the same output? Justify. [8]
Link: Graph Theory Overview