What should a mathfag know about computation and computation complexity theory?
What are the most important concepts to know, apart from the undergrad CS stuff?
>>8073794
Just remember, O(log n) is the best my manno.
>>8073794
>Combinatorics (because it leads onto) combinatorial optimization
>Numerical analysis
>Variational principles
>Algorithmic Graph Theory
>>8073794
>apart from the undergrad CS stuff?
the grad CS stuff
>>8073794
The following concepts are valuable to understand:
>Pseudopolynomial time complexity
>Eliminating recurring term in a recurring equation
>Reductions
>Generating functions
>Z-transforms
Truth to be told, I'm an undergrad and as such have no clue what I am talking about. pic not related
>>8074759
>>Z-transforms
CS majors don't learn shit about z transforms
>>8075163
I attended a class in algorithms with CS majors who knew about Z-transforms. With that said, I don't know how they learned it in school or in spare time. Nevertheless, your statement is completely useless.
>>8074759
>Generating functions
Why is this not undergrad?
>>8073794
If you are a mathematician simply looking to enter the software industry here are the things you need to know:
>Avoid n^3 growth. By this I am implying that you should be able to tell the growth rate of your functions and just not do stupid shit.
>Know the theory behind common data structures and when to use them. This is not a day to day stuff but in the past I've had to use linked lists a fuckton of times and binary trees a few times aswell.
You don't need anything else because if you have a math degree you already know how to think logically and whenever something "complex" arrives at your door, you just need to think calculus and linear algebra to solve it.
t. Professional computational mathematician
>>8073794
It's all ad hoc really.
>>8073794
Covered in the first volume of The Art of Programming.
1.2.10 Analysis of an Algorith
1.2.11 Asymptotic Representations/Euler's summation formula to approx an algorithm
There's a good crash course for simple complexity estimation
>>8076046
Isn't it? We did it in 2nd year. (Canadian university, CS or Math do it in 2nd year)
>>8076059
>linked lists
What language are you using and situation are you in where these are useful in any way?
Vectors blow them out of the water for performance in virtually every case
Are you talking about immutable linked lists?
Don't fall for linked list meme. A number of situations where it can be efficiently used is relatively small and the "not having constant size of elements" is a weak indicator outside the lectures.
>>8076155
Look, if you're still going to troll or act retarded, that's fine.
- Swear
- Ad hominem; Call people names
- Don't provide counter-arguments
- Reject realism and the scientific consensus
That's ok.
Just don't loop.
Looping is cancer.
Personal incredulity and the argument from ignorance are fallacies. You're ignorant.
You imply you have no knowledge of the other kinds, therefore they don't exist.
That is wrong irrational.
:D
>>8076629
no, they don't.
lists support the cut at x / join operations in O(1)
