Skip to content

Latest commit

 

History

History
62 lines (45 loc) · 3.48 KB

Questions.md

File metadata and controls

62 lines (45 loc) · 3.48 KB
Raw

discrete-structures

  1. Write a Program to create a SET A and determine the cardinality of SET for an input array of elements (repetition allowed) and perform the following operations on the SET: a) ismember (a, A): check whether an element belongs to set or not and return value as true/false. b) powerset(A): list all the elements of power set of A. 26

  2. Create a class SET and take two sets as input from user to perform following SET Operations: a) Subset: Check whether one set is a subset of other or not. b) Union and Intersection of two Sets. c) Complement: Assume Universal Set as per the input elements from the user. d) Set Difference and Symmetric Difference between two SETS e) Cartesian Product of Sets.

  3. Create a class RELATION, use Matrix notation to represent a relation. Include functions to check if the relation is Reflexive, Symmetric, Anti-symmetric and Transitive. Write a Program to use this class.

  4. Use the functions defined in Ques 3 to check whether the given relation is: a) Equivalent, or b) Partial Order relation, or c) None

  5. Write a Program to implement Bubble Sort. Find the number of comparisons during each pass and display the intermediate result. Use the observed values to plot a graph to analyse the complexity of algorithm.

  6. Write a Program to implement Insertion Sort. Find the number of comparisons during each pass and display the intermediate result. Use the observed values to plot a graph to analyse the complexity of algorithm.

  7. Write a Program 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)

  8. Write a Program to calculate Permutation and Combination for an input value n and r using recursive formula of nCr and n Pr .

  9. For any number n, write a program to list all the solutions of the equation x1 + x2 + x3 + …+ xn = C, where C is a constant (C<=10) and x1, x2,x3,…,xn are nonnegative integers using brute force strategy.

  10. Write a Program to accept the truth values of variables x and y, and print the truth table of the following logical operations: a) Conjunction f) Exclusive NOR b) Disjunction g) Negation c) Exclusive OR h) NAND d) Conditional i) NOR e) Bi-conditional

  11. Write a Program to store a function (polynomial/exponential), and then evaluate the 27 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)).

  12. Write a Program to represent Graphs using the Adjacency Matrices and check if it is a complete graph.

  13. Write a Program to accept a directed graph G and compute the in-degree and out-degree of each vertex.

  14. Given a graph G, write a Program to find the number of paths of length n between the source and destination entered by the user.

  15. Given an adjacency matrix of a graph, write a program to check whether a given set of vertices {v1,v2,v3.....,vk} forms an Euler path / Euler Circuit (for circuit assume vk=v1).

  16. Given a full m-ary tree with i internal vertices, Write a Program to find the number of leaf nodes.

  17. Given an array of N integers arr[] where each element represents the max length of the jump that can be made forward from that element. Find the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then you cannot move through that element.