patternMinor
Why is discrete mathematics required for data structures?
Viewed 0 times
whydiscreteformathematicsdatastructuresrequired
Problem
Data Structures is the second CS course taught at Columbia University and it lists Discrete Mathematics as a Co-Req.
I have a BSEE and have not taken any discrete mathematics and am having a hard time understanding why I need to take this to do things like create data structures?
Is this just so the university can cram useless info in my head and make more money, or is there a real relation to discrete math and data structures?
I have a BSEE and have not taken any discrete mathematics and am having a hard time understanding why I need to take this to do things like create data structures?
Is this just so the university can cram useless info in my head and make more money, or is there a real relation to discrete math and data structures?
Solution
A course on data structures will not be about "creating data structures". You can expect to analyse data structures, prove various properties of them, and create your own to solve some highly nontrivial problems.
Every single data structure you intend to build must be rigorously defined. Each method on a data structure must be proven rigorously to be correct. The time and space complexity of each method must be rigorously proven to follow a particular asymptotic bound. This all involves some nontrivial discrete mathematics. You'd also need to have a solid handle on probability when randomized inputs and data structures start being used, which you should expect for a decent course on data structures. If you're still unconvinced, look up Cuckoo Hashing and show that the insert time is, on average, $O(1)$, or take a look at a van Emde Boes tree and just attempt to figure out how the hell it works in the first place. You'll quickly realise that there's far more to it than just writing code to build obvious structures.
However, if you go into this course believing it to be beneath you, I can guarantee that you'll get nothing out of it. I would be very surprised indeed if an Ivy League university is "trying to cram useless info into your head and make more money".
Every single data structure you intend to build must be rigorously defined. Each method on a data structure must be proven rigorously to be correct. The time and space complexity of each method must be rigorously proven to follow a particular asymptotic bound. This all involves some nontrivial discrete mathematics. You'd also need to have a solid handle on probability when randomized inputs and data structures start being used, which you should expect for a decent course on data structures. If you're still unconvinced, look up Cuckoo Hashing and show that the insert time is, on average, $O(1)$, or take a look at a van Emde Boes tree and just attempt to figure out how the hell it works in the first place. You'll quickly realise that there's far more to it than just writing code to build obvious structures.
However, if you go into this course believing it to be beneath you, I can guarantee that you'll get nothing out of it. I would be very surprised indeed if an Ivy League university is "trying to cram useless info into your head and make more money".
Context
StackExchange Computer Science Q#14450, answer score: 9
Revisions (0)
No revisions yet.