4

I've been assigned to explore implementing (along with modifications, so understanding it is a must) this algorithm for the 'Redistricting Problem': https://dl.acm.org/doi/pdf/10.1145/3274895.3274979 .

They have code linked in the paper, in C++ and python. I've never worked with C++ and my python knowledge is also modest.

Moreover, I've taken only a single Algorithms class (at uni) recently, and while I do understand DP and linear programming concepts well enough, I'm still very new to reading papers. Hence, considering how I'm finding this paper a difficult read (compared to several other algorithms-for-redistricting papers), I'm not sure whether the right approach is to continue to slog at it until deadline, or know when to give up (and move on to other work).

Just, generally, when do you decide that you don't understand (the code/math in) a paper well enough to use their techniques (without exactly copying them)?

Samia Zaman
  • 49
  • 2
  • Find general knowledge resources on maps, such as some of the very useful tutorials over at [Red Blob Games](https://www.redblobgames.com/?) who do a very good job of describing Delauney+Voronoi diagrams. Maybe step back from their code and grab a pen and paper and step through what they are doing at a high level. Their code likely mixes this concern with other concerns that are more platform orientated. Finally the new thing in this paper is probably the application to political zones, or the particular membership function, Voronoi diagrams have been well defined since 1908 and seen in 1644. – Kain0_0 Jul 08 '20 at 10:20

2 Answers2

13

Just, generally, when do you decide that you don't understand (the code/math in) a paper well enough to use their techniques (without exactly copying them)?

When progress stops and you run out of ideas to get it going again.

Your assignment is to explore. That is a polite way to say, "bang your head on this wall". No one knows what will give in first, the wall, your head, or the clock.

It may simply be the math in the paper isn't explained well enough to understand. If that's the case you may have to reverse engineer it to gain understanding of it's principles.

If your skills are lacking find someone who has them and ask questions. If you can, see how they feel about the paper.

Above all, keep whoever asked you to do this apprized of how you're feeling. Predicting the future is hard. Saying you feel lost is not.

candied_orange
  • 102,279
  • 24
  • 197
  • 315
3

Your lack of experience in C++ and Python is probably not the biggest barrier. Source code written by academics for academic papers is typically not very easy to read anyway.

You usually don't need to understand an entire algorithm in order to implement parts of it. Pick a small part you understand, and implement it. You will learn from implementing it, and more of the paper will make sense to you, so you can repeat the process. Don't try to make major modifications until you implement it unchanged. Keep in mind that papers build heavily on previous work, so an incremental step might be going back to a cited paper and implementing its algorithm.

The other benefit of implementing small parts is you still have something to deliver, even if you don't get the entire algorithm implemented. You can report on the part you finished and its pros and cons for your application. You might end up doing data munging or tests or utility code that can be reused in other algorithms.

Karl Bielefeldt
  • 146,727
  • 38
  • 279
  • 479