B.Sc. (Hons.
) Computer Science Semester-II
Practical Examination
Discrete Structures
Time 2.5 Hrs Max. Marks 25
Set – I
1. The Fibonacci strings are a sequence of recursively defined strings. F0 is A, F1 is BC.
Fn+2 is defined as the concatenation of Fn and Fn+1. For example, F2 is ABC. Given a
number n and an index k, return the kth character of the string Fn. [7]
2. There are 2 ice-creams that students like – Vanilla and Butterscotch. Create a class
GROUPS that includes a function to input student roll numbers for students who like
a particular ice-cream flavour. Also, implement functions for the following: [13]
a. Check if a student likes Vanilla or not
b. Check whether all students who like Vanilla also like Butterscotch
c. Find the number of students who like only one of the two ice-creams
d. Display all possible pairs of students such that, in a pair, one student likes
Vanilla and the other likes Butterscotch
B.Sc. (Hons.) Computer Science Semester-II
Practical Examination
Discrete Structures
Time 2.5 Hrs Max. Marks 25
Set – II
1. Due to inactivity, Monu has gained weight. Monu wants to lose weight by running
along the roads of his city connecting various landmarks. Implement functions of a
COUNTRY class for the following:
a. Input the road connections between n landmarks, n ≥ 4 and display using
adjacency matrix
b. Check if two cities are connected by a direct or an indirect path
c. Is it possible for Monu to run on all roads exactly once?
d. To lose weight quicky, Monu wants to run on paths of length n. Given a positive
integer n, calculate the number of paths he can run on. [13]
2. Given a list of n integers, n ≥ 10, find the maximum element in the list using recursion.
[7]
B.Sc. (Hons.) Computer Science Semester-II
Practical Examination
Discrete Structures
Time 2.5 Hrs Max. Marks 25
Set – III
1. Use insertion sort to sort a list of n integers, n ≥ 10. [7]
2. Consider three suitcases A, B, and C and n items of clothing of distinct sizes. Initially,
all clothes are placed in a pile in suitcase A arranged in such an order that the
smallest piece of clothing is at the top, while the largest is at the bottom. You are
required to move the entire pile of clothes to another suitcase C, using B as an
intermediate suitcase, obeying the following rules:
a. Only one piece of clothing can be moved at a time
b. Each move consists of taking the topmost piece of clothing from the pile in
one of the suitcases and placing it on top of the pile on another suitcase.
c. No cloth can be placed on top of a smaller cloth.
Given n, calculate the number of moves to perform the transfer. [13]
B.Sc. (Hons.) Computer Science Semester-II
Practical Examination
Discrete Structures
Time 2.5 Hrs Max. Marks 25
Set – IV
1. Consider a relation R on a set of siblings. Two siblings are in relation R if they eat
dinner together. The relation is represented using relation matrix notation.
Implement functions of a SIBLING class to determine if the relation is: [13]
a. Reflexive
b. Symmetric
c. Transitive
d. Anti-symmetric
2. Each of the n students can be identified by a distinct character. Implement a function
to count and print all ways in which an examiner can call them for a viva-voce. [7]
B.Sc. (Hons.) Computer Science Semester-II
Practical Examination
Discrete Structures
Time 2.5 Hrs Max. Marks 25
Set – V
1. Given an equation, x1 + x2 + … + xn = C, where C is a positive constant and x 1, x2, …, xn
are non-negative integers, find all solutions. [7]
2. A social media platform works by allowing users to follow one another. There is a
link from user A to user B if A follows B. Using the information above, implement the
following functions of the SOCIAL class: [13]
a. Represent the social media platform using adjacency matrix
b. Add new users (do not follow anyone and are not followed by anyone initially)
c. Given names of two users, add/delete their follow links
d. For each user, calculate the number of followers and the number of users
they are following
e. Delete existing users
B.Sc. (Hons.) Computer Science Semester-II
Practical Examination
Discrete Structures
Time 2.5 Hrs Max. Marks 25
Set – Vi
1. Given a sorted list of n integers and a positive integer x, find the location of x in this
list using recursive binary search. For the recurrence relation T(n) of binary search,
write a function that accepts an input K from the user and graphically represent the
values of T(n) where n varies from 0 to K. [13]
2. Consider three bookshelves A, B, and C with some books. Assuming the bookshelves
do not hold multiple copies of the same book, implement the following functions of
the BOOKSHELF class: [7]
a. Find books common to all three bookshelves
b. Find books that are present in bookshelf A or bookshelf B but not in bookshelf
C.
c. A relation R is defined on a bookshelf such that (x, y) ∈ R iff x > y. Show
relation matrices for all three bookshelves.
B.Sc. (Hons.) Computer Science Semester-II
Practical Examination
Discrete Structures
Time 2.5 Hrs Max. Marks 25
Set – VII
1. Consider a playlist of songs. A relation R is defined on this playlist such that (a, b) ∈
R (a and b are any two songs from the playlist) if duration of a is greater than or
equal to duration of b. Create a PLAYLIST class and implement the following
operations: [13]
a. Accept user input for the songs’ duration (in mins) in a playlist
b. Accept two playlists A and B and determine if A is a subset of B
c. Determine if the relation R is partial ordered or not.
2. Consider the following propositions:
P: I like to read
Q: I am unable to concentrate
Given the truth values of propositions P and Q, find the truth values of the
conjunction, disjunction, exclusive OR, conditional statement, and biconditional
statement of these propositions. [7]
