CS Problems §

---

• P vs NP problem.
• K-clique in a graph.
• Boolean satisfiability.
• Travelling Salesman problem.
• Knapsack problem.
• Linear Knapsack Problem.
• Optimise branches and short branches.
• Colour vertices of graph with k colours.
• Halting Problem

Harder Problems §

• Ackermann’s function.
• Does a regular expression cover all regular expressions possible for its alphabet.