NP and the like are certainly challenging, but it's unlikely your students will have any success with them. Instead, try improving or inventing heuristic algorithms for such problems.

You could start with the knapsack problem. It is surprising how fast even relatively large knapsack problems can be solved on modern computer if clever programming is applied. Problems withh 1000s or 10 000s of objects are solvable in a fraction of a second on desktop computers. It would be eye-opening for your students to see that discovering that a problem is NP is not the kiss of death.

Scheduling and resource allocation problems are a great place to flex heuristic muscles. There is a huge variety of subtlety here. What is the value of putting a task on the schedule? Is it a simple weight, or is there a strict priority where task n is worth more than all tasks m > n, or is there a trade between the value of the task and the resources the task would consume? Does the task always use the same resources which always cost the same amount or do the resources and their costs vary depending on where or when the task is scheduled? Are the tasks atomic or separable into sub-tasks? And if separable, must all the parts be scheduled or are there varieties of sub-tasks that are sufficient?

Similarly, the traveling salesman problem comes in a huge variety of types. Open- ended vs closed-loop tours, for example. Side costs. Ordering constraints. The list is almost endless.

Projects like this will serve your students well. They will develop confindence in themselves as they set about thinking and solving. Plus it will give them something to brag about and discuss intelligently with job interviewers inquiring about what they've done in school.

Heuristics are the way the world runs. Exact solutions are rare. Ingenuity is precious and rewarded correspondingl, but only if it is discovered and nourished.

Plus, this stuff is a lot of fun. (If it's not fun to a student, then that student has discovered something very personally important, that this is not the kind of work they'll want to be doing in their career. You'll have saved someone a lot of angst.)

Best of luck.

Can  you be more specific, please. What is your purpose?

Is there a k-competitive algorithm for solving the k-server problem in an arbitrary metric space?

In what way do you want the algorithm challenging?  Mathematically to understand?  Difficult to implement?  Or are you talking about challenging computing problems (which is pretty much the opposite of what you're asking, but it is worth putting it out there)?

Hi Daniel, I would be looking for  Mathematically difficult, challenging to program etc.

Hi,

Look at : P versus NP problem which is a major unsolved problem in computer science and mathematics

Dear Dr. Chandrakant , it is more complex to work on finding out all hamiltonian cycles in graphs i think this would be challenging for any one

You could implements algorithms for doing low-dimensional topology like knot theory. That could be very much enlightening and would be also useful.

Find an efficient algorithm for "The transversal hypergraph generation" also called "The dualization of a hypergraph". It is  the problem of generating, given a hypergraph, the set of its minimal transversals, i.e., the hypergraph whose hyperedges are the minimal hitting sets of the given one.

A still valid summary:

Johnson, DS 2005, ‘The NP-completeness column’, ACM Trans. Algorithms, vol. 1, no. 1, pp. 160–176.

NP and the like are certainly challenging, but it's unlikely your students will have any success with them. Instead, try improving or inventing heuristic algorithms for such problems.

You could start with the knapsack problem. It is surprising how fast even relatively large knapsack problems can be solved on modern computer if clever programming is applied. Problems withh 1000s or 10 000s of objects are solvable in a fraction of a second on desktop computers. It would be eye-opening for your students to see that discovering that a problem is NP is not the kiss of death.

Scheduling and resource allocation problems are a great place to flex heuristic muscles. There is a huge variety of subtlety here. What is the value of putting a task on the schedule? Is it a simple weight, or is there a strict priority where task n is worth more than all tasks m > n, or is there a trade between the value of the task and the resources the task would consume? Does the task always use the same resources which always cost the same amount or do the resources and their costs vary depending on where or when the task is scheduled? Are the tasks atomic or separable into sub-tasks? And if separable, must all the parts be scheduled or are there varieties of sub-tasks that are sufficient?

Similarly, the traveling salesman problem comes in a huge variety of types. Open- ended vs closed-loop tours, for example. Side costs. Ordering constraints. The list is almost endless.

Projects like this will serve your students well. They will develop confindence in themselves as they set about thinking and solving. Plus it will give them something to brag about and discuss intelligently with job interviewers inquiring about what they've done in school.

Heuristics are the way the world runs. Exact solutions are rare. Ingenuity is precious and rewarded correspondingl, but only if it is discovered and nourished.

Plus, this stuff is a lot of fun. (If it's not fun to a student, then that student has discovered something very personally important, that this is not the kind of work they'll want to be doing in their career. You'll have saved someone a lot of angst.)

Best of luck.

Hi!

Maybe you should try the online judge that the University of valladolid has. The url is http://uva.onlinejudge.org/ there is one of the largest problem repository of all times. Plus, there is a status bar in every problem, so you can determine the difficulty.

Hope it helps!

http://uva.onlinejudge.org/

Hi,

I am doing research in the area of UAV Path planning algorithms. Based on this topic some have written programs in C, C++.  actually many algorithms are their based on this topic. so could you please help me which algorithm will be mostly fit to do work easily in C, C++.

Try to build a heuristic based approach for group formation among students so that they can score more, interact more among themselves; thereby gaining more knowledge.