Hey all,
I have started learning Algorithms (in java). I found a course on coursera starting soon: Analysis of Algorithms and I am really interested in doing it as it will probably aid my current Algorithm course in college however my maths is somewhat weak and I am wondering what math concepts I will need to brush up on for this course? It says know calculus but besides that?
Thanks!
Maths requirements for Algorithm Analysis
Page 1 of 18 Replies  1786 Views  Last Post: 18 September 2013  01:06 PM
Replies To: Maths requirements for Algorithm Analysis
#2
Re: Maths requirements for Algorithm Analysis
Posted 23 August 2013  02:47 PM
You won't really need a ton of Calculus. The only Calculus skill you will need is understanding how to evaluate limits. Algorithm Analysis focuses more heavily on the Discrete side. You will want a basic understanding of Number Theory, Set Theory, Graph Theory, Combinatorics, and proofwriting (specifically, proof by induction). The number theory is particularly relevant for solving recurrence relations. If you have taken a differential equations class, the methods for solving recurrences are pretty much the same (as recurrences are discrete differential equations).
#3
Re: Maths requirements for Algorithm Analysis
Posted 23 August 2013  02:48 PM
Ok thanks a lot! I'll focus more on revising discrete mathematics then. Any book suggestions for someone that is relatively average at maths?
This post has been edited by alpha_x: 23 August 2013  02:49 PM
#5
Re: Maths requirements for Algorithm Analysis
Posted 29 August 2013  12:38 PM
I'd also suggest brushing up on Linear Algebra.
So much of Computer Science involves matrices and vectors, you are bound to come across it.
Even a field seemingly unrelated to advanced mathematics, such as game development, makes heavy use of arrays (i.e.  matrices and vectors). It might be a good idea to learn some basic concepts of matrices, how vectors apply to two and threedimensional space, how to compute the norm of a vector, how to multiply a vector by a matrix to get a vector, etc.
So much of Computer Science involves matrices and vectors, you are bound to come across it.
Even a field seemingly unrelated to advanced mathematics, such as game development, makes heavy use of arrays (i.e.  matrices and vectors). It might be a good idea to learn some basic concepts of matrices, how vectors apply to two and threedimensional space, how to compute the norm of a vector, how to multiply a vector by a matrix to get a vector, etc.
#6
Re: Maths requirements for Algorithm Analysis
Posted 29 August 2013  01:14 PM
Quote
field seemingly unrelated to advanced mathematics, such as game development
Really?
#7
Re: Maths requirements for Algorithm Analysis
Posted 31 August 2013  02:14 PM
#8
Re: Maths requirements for Algorithm Analysis
Posted 31 August 2013  02:55 PM
Quote
Even a field seemingly unrelated to advanced mathematics, such as game development, makes heavy use of arrays (i.e.  matrices and vectors). It might be a good idea to learn some basic concepts of matrices, how vectors apply to two and threedimensional space, how to compute the norm of a vector, how to multiply a vector by a matrix to get a vector, etc.
The math behind game development is a lot more intense. Personally, I don't agree with the attitude that a little bit of basic vector math from a high school precalc class is sufficient. In order to do game development, you'll really want an abstract linear algebra class, where vector spaces and linear transformations are covered. You will want a lot of this for topics like Orthogonal projections.
As for linear algebra, it is useful for algorithms (though one can definitely get by and do well without it), just not in the context you are discussing. Vector Spaces can be used to study graphs, which are incredibly useful in CS for topics like planarity, isomorphisms, etc. So at that point, the precalc vector math isn't as important as applying abstract linear algebra concepts.
#9
Re: Maths requirements for Algorithm Analysis
Posted 18 September 2013  01:06 PM
I have found that in algorithm analysis, you should be succiecent in methods of proof, relations, recurrance relations, Big O, Time complexity, and Numberical Analysis.
Page 1 of 1
