Video idea: Is shorter code always faster?

RoyVoetman commented 2 years ago

I am trying to think of a video topic idea and right now I have the following idea: a video called “Is shorter code always faster?” In which we mathematically explore two ways to solve an easy programming assignment (one with 5 lines of code and one with 2 lines of code) and determine which program actually requires the least number of operations that the computer has to perform.

The key idea being that in the analysis of this question you will need probably theory and even generating functions, which is super interesting since, to me, this was totally non obvious when first reading about algorithm analysis.

Would anybody of you be interested in such a video? Any suggestions or feedback is welcome 🙏 thanks. And if you have any collaboration ideas let’s see if we can work something out.

About the author

I am almost done with my bachelors degree in Software Engineering at the Hanze University of Applied Science in Groningen the Netherlands. I also have up to 3 years of experience as a part-time programmer and have a large passion for discrete mathematics. In the SOME2 I particularly want to inspire programmers to see the connections between programming and mathematics, and I want mathematicians to see how their field can be applied to programming. This is because from my experience there are a lot of (self-taught) programmers that want to get into the more mathematical side of programming but don’t know were to start. Predominantly because without a formal computer science education from a university it can be really daunting.

More details

I also made a video for SOME1: https://youtu.be/yDXk3Fi6b_A (a mathematical definition of an algorithm) But now that I reflect back on that video it does not motivate the relevance of the content. I believe that my new idea “is shorter code always faster?” really appeals to a wider audience.

Contact details

Discord: Roy#2133 Or just place a comment on this issue

This post is to be considered CC-BY.)

aargup934 commented 2 years ago

I might be interested. I am a 9th grader who is interested in applied math. I am not an expert in this topic, but hope to learn. I am aware of basic Computer Science such as time complexity and especially like combinatorics.

HSchmale16 commented 2 years ago

This is actually a really good topic. Although I don't know how you would make this apply to a general scenario. I could see using an algorithm like substring matches being a good example to start with. As that's a hard algorithm, and there's been a lot of very cool algorithms for finding them quickly. Especially, since the naive algorithm requires a lot of backtracking.

RattatAndyGo commented 2 years ago

I legit just had an exam all about algorithm efficiency, so I know a bunch about it! Please send me a PM on discord if you still want to collaborate with someone. Cheers! Andy_Go#1068

alan2here commented 2 years ago

It's trivially obvious to programmers that shorter programs are not faster than longer ones, for example some recursive functions become faster and longer when they're rearranged into non-recursive functions containing a loop.

Your video could still be very interesting though, it'll be nice to see a proof of a statement like this.

For if you're interested as this may well be outside of the scope of your video:

I'd say that with code that seems correct (for example it gives the correct outputs when input with test data where you already know the answers), then a shorter program is more likely to be actually correct. It's more likely to give you correct answers with new data, generalise, and give reasonable answers even to challenging or confusing questions.

Information theory says something along the lines (although the time complexity may be unmanageable) that N amount of non-random data can typically be compressed to log(N) in size, so you don't need much disk space just to reconstruct the data.

To actually achieve this, and especially if you'd like to generalise, then I think what you'd end up with is something more like a program that reconstructs the data, or something like a Neural Network, still data either way, but very different to a traditional data file such as a ZIP or PNG file.

leios / SoME_Topics