r/computerscience • u/Homaderuvas • 15h ago
Help Drop some interesting algorithm problems
Hi guys please kindly share some interesting algorithm problems in the comment section. I did solve many algorithm problems on platforms like codeforces, atcoder, luogu and code chef etc.. looking for some unique ones that are quite challenging and interesting at the same time but kindly don't share open problems .
4
Upvotes
4
u/Magdaki Professor. Grammars. Inference & Optimization algorithms. 14h ago edited 14h ago
Suppose you have some process that produces data, i.e. a generative process. You've replaced the data with a sequence of symbols in a problem specific representational way. The question is: is some underlying grammar that describes the developmental sequence and if so what is it?
For example:
ABA
ABABBBABA
ABABBBABABBBBBBBBBABABBBABA
The grammar (in this case an L-system) that describes this developmental sequence is A -> ABA and B -> BBB.
For deterministic cases, there's already good algorithms for inferring this, although they could be improved (I have a paper being written right now on just such an improvement). The really challenging case is when there are errors in the strings, missing strings, or non-determinism.
E.g.
ABA
ABBABBBABA
ABABBBBABABBBBBBBAABABBBAA
This is much harder. My RAs and I are currently working on this type of problem. We recently also cracked the non-visual problem too (same paper as above). That's a bit hard to describe so don't worry about it.
This is my core research area.
Even trying to reproduce my work on this without looking it up would be good algorithms practice.
By the way, the solution need not be an L-system. Recently (well ok a few years ago), my research group branched out into other types of grammatical inference. So feel free to pick something else too. The core of it is given some data produced by (or believed to be produced by) some type of grammar, infer the grammar.