Drop some interesting algorithm problems

[u/Homaderuvas]

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 .

[u/Humble-Captain3418]

Can you elaborate this problem a little further? Especially what "grammatical computational model" means. I should be fine reading literature on the matter, too.

[u/Magdaki → u/Humble-Captain3418]

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.

[u/AbleActuary5795 → u/Magdaki]

I assume the interesting part is identifying the minimal grammar that contains exactly all (or some error-free subset) of the outputs of the original system. Does the non-determinism come into play where some particular rules only occur with a given frequency? 

W.r.t. errors, for any sufficiently large sample of system outputs of size n, you could construct G* as your initial minimal grammar. You can then identify the rules that are only used for k<<n items in the sampled output, eliminate those rules and construct the refined G**. Repeat until no rules are removed.

[u/Magdaki → u/AbleActuary5795]

With errors you can always infer a non-deterministic system. So my goal is to infer the underlying deterministic system.