DISCRETE MATHEMATICS

GROUP PROJECT

The Objective

You will have the opportunity to improve your skills in team work through preparing an essay.

Each group will consist of two students. A topic will be picked from the following list. You can come up with you own topic as long as it is approved by the instructor. Note that each topic can be selected by at most 2 groups.

The essay will be at most 7 pages and will have the following parts: 1) Introduction and Description 2) Detailed Explanation 3) Examples 4) Applications (if applicable) 5) References

1) Recursive Algorithms

2) Relational Databases

3) RSA public key Crypto System

4) Heaps

5) Euler and Hamiltonian Paths

6) Graph Connectivity

7) Planar Graphs

8) Spanning Trees

9) Graph Coloring

10) Finite State Automata

11) Non-deterministic Finite State Automata

12) Relationship between Languages and Automata

13) Max-flow Min-cut Theorem

14) NP-Completeness

15) Generalized Permutations and Combinations

16) Turing Machines

17) Karnaugh Maps

18) Shortest Path Algorithms in Graphs

19) Sorting Algorithms

20) Gödel's Completeness Theorem