16. Define the following terms:
(a) Degree of a vertex
(b) Loop
(c) Isolated vertex
(d) Adjacent vertices.
17. Define the following terms w.r.t a graph
(a) path (b) circuit (c) simple path
18. Define the following terms w.r.t. of graph
(a) Connected graph
(b) Components of a graph
(c) Walk of a graph
(d) Directed graph.
19. Define the following terms w.r.t. a graph
(a) out degree (b) in degree
20. How will you define the following:
(a) string (b) alphabet in languages.
21. How do you define the length of a string?
22. Define the following in respect of languages.
(a) Empty string
(b) Reverse string
(c) Substring
(d) Concatenation
22. What do you mean by lexicographic ordering of strings?
23. What do you mean by prefix and suffix of a string?
24. Define a language with an example.
25. Define concatenation of strings with an example.
26. Define “kleene star”, with an example.
27. What are the kinds of fundamental proof techniques?
28. Explain the following with an example (in Boolean logic)
(a) Negation
(b) Conjunction
(c) Disjunction
(d) Exclusive-OR
(e) Equality
(f) Implication
29. State and explain the principle of Mathematical Induction with an
example.
30. State and explain Pigeon-hole principle with an example.
31. What do you mean by Grammar?
32. What are the types of Grammars?
Introduction
45