Types of problems in graph theory.

1. If given pair of graphs is isomorphic?
2. Determine if there is a graph possible for the given degree sequence?
3. Draw a graph with given degree sequence.
4. Find the number of edges if a graph has 4 vertices of degree 3 and an isolated vertex.
5. Find the number of regions in a connected planar graph if no. of edges is e and no. of vertices n.
6. Determine if Ore's theorem can be used on given graph?
7. Determine if Diarc's theorem can be used on given graph?
8. Is the given graph planar?
9. Is the given graph bipartite?
10. Does graph have an Euler circuit?
11. Does graph have an Hamiltonian circuit?
12. Find the chromatic number of given graph?
13. Color the given graph.
14. Construct a 4 regular graphs on 12 vertices?
15. Draw complement of given graph.
16. Draw MSTs of the given graph.
17. Prove that ............ 
18. Define ---------  Regular graph, complete graph etc.

Deterministic and Non-Deterministic Algorithms

 n deterministic algorithm, for a given particular input, the computer will always produce the same output going through the same states but in case of non-deterministic algorithm, for the same input, the compiler may produce different output in different runs. In fact non-deterministic algorithms can’t solve the problem in polynomial time and can’t determine what is the next step. The non-deterministic algorithms can show different behaviors for the same input on different execution and there is a degree of randomness to it.

Source: https://www.geeksforgeeks.org/difference-between-deterministic-and-non-deterministic-algorithms/.

Question types in Theory of Computation

 Define a Regular Expression for given DFA.

Define a DFA for the given Regular Expression.

Give the language for the given Regular Expression.

Give the Regular Expression for the given Language.

Construct a DFA for given language.

Construct a PDA for given language.

Construct a TM for given language.

Give a CFG for the given language.

Give the language generated by the given CFG.

Show that given CFG is ambiguous.