Curriculum Planner
(Department of Computer Science
Kalindi College)
Course : B.Sc.(H) Comp. Sc
Semester : II
Paper : PRACTICALS OF PAPER NO –C IV: Discrete Structures
Name of the Teacher: Dr. Reena Jain
LIST OF PRACTICALS OF PAPER NO –C IV
Topic / Schedule· Write a program containing following set operation functions for a given set A (consider A to be array of integers).
a) unique(A) ; return a set of the unique elements of a given set.
(For example unique( [ 1, 2, 8, 2, 2, 1, 7, 2, 1, 1 ] ) should return 1,2,8,7)
b) ismember (a, A); for checking an element’s membership, with return value as true/false
c) cardinality(A): to determine the cardinality of a set;
d) powerset(A): to list all the elements of power set of A
· Create a class SET and include functions to perform following Set operations on Sets:
Subset, Union, Intersection, Complement, Set Difference, Symmetric Difference and Cartesian Product. WAP which takes sets from user and use this class. / Jan 2016
· Create a class RELATION, use Matrix notation to represent a relation. Include functions to check if a relation is reflexive, Symmetric, Anti-symmetric, Transitive, to generate Reflexive Closure of relation. WAP to use this class.
· WAP that generates all the permutations of a given set of digits, with or without repetition. (For example, if the given set is {1,2}, the permutations are 12 and 21). (One method is given in Liu)
· WAP to take a logical expression from a user and generate its truth table.
If the truth values of propositions x and y are given, write a program to find the truth values of the following statements for the propositions x and y
Conjunction
Disjunction
Exclusive OR
Conditional
Biconditional
· WAP for binary search a) using recursion, b) without recursion.
WAP for Calculating Permutation and Combination (nCr and nPr) using recursion.
· For any number n (say 4 or 5), write a program to list all the solutions of the equation x1 + x2 + x3 + …+ xn = C, where C is a constant, where x1, x2, x3,…, xn are nonnegative integers.
· WAP which checks whether the input expression is a well formed formula or not. /
Feb 2016
· WAP to list steps of solution to Tower of Hanoi using recursion.
· WAP to solve second order linear homogeneous recurrence relation with constant coefficients.
· Write a program for recurrence relation T(n), defined as follows
T(n) = T(n-1) + n, T(0) = 1
T(n) = T(n-1) + n^2, T(0) =1
T(n) = 2*T(n)/2 + n, T(1)=1
Test these programs for different input (say n = 1, 2, 3, …) and plot the output in a Spreadsheet package.
· WAP that takes as input a recurrence relation, and solves the recurrence by implementing cases of Master's Theorem.
· WAP to store a function (polynomial/exponential) in an array, and then evaluate the polynomial. (For example store f(x) = 4n3 + 2n + 9 in an array and for a given value of n, say n = 5, evaluate (i.e. compute the value of) f(5)).
· WAP that proves that proves that the function f(n) = 10n2 + 5n + 100 is O(n2). (To do so store the polynomials f(n) and g(n) = n2 in two arrays and compute the values of n and c for which f(n) <= c.g(n) ).
· WAP that proves that proves that the function f(n) = 2n3 + 4n2 + 20 is Ө(n3). (To do so store the polynomials f(n) and g(n) = n3 in two arrays and compute the values of n and positive constants c1 and c2 for which c1.g(n) <= f(n) <= c2.g(n) ). / Mar 2016
· WAP to represent Graphs using the Adjacency Matrices and check if it is a complete graph.
· Take input as an adjacency matrix for an undirected simple graph, write a program to check whether the graph is a tree or not.
· WAP to find the connected components of an undirected graph.
· WAP to create and store a simple binary tree in an array. Further, display nodes in the tree by using any traversal method.
· WAP to find out whether a spanning tree can be formed out of the graph or not.
· Given WAP to check whether an undirected/ directed graph contains Euler cycle or Euler path.
· Given an adjacency matrix of a graph, write a program to find out if there exists an Euler path / euler circuit or not
· Given an adjacency matrix of a graph, write a program to find out if there exists a Hamilton path / Hamilton circuit or not / April 2016