Maths requirements for Algorithm Analysis

Page 1 of 1

8 Replies - 1762 Views - Last Post: 18 September 2013 - 01:06 PM

#1 alpha_x

Reputation: 6
• Posts: 55
• Joined: 03-May 11

Maths requirements for Algorithm Analysis

Posted 23 August 2013 - 02:41 PM

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!

Is This A Good Question/Topic? 0

Replies To: Maths requirements for Algorithm Analysis

#2 macosxnerd101

• Self-Trained Economist

Reputation: 10964
• Posts: 41,006
• Joined: 27-December 08

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 proof-writing (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 alpha_x

Reputation: 6
• Posts: 55
• Joined: 03-May 11

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

#4 macosxnerd101

• Self-Trained Economist

Reputation: 10964
• Posts: 41,006
• Joined: 27-December 08

Re: Maths requirements for Algorithm Analysis

Posted 23 August 2013 - 04:02 PM

As a matter of fact, we do.

#5 DavidB

Reputation: 3
• Posts: 32
• Joined: 20-July 06

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 three-dimensional space, how to compute the norm of a vector, how to multiply a vector by a matrix to get a vector, etc.

#6 Ryano121

• D.I.C Lover

Reputation: 1372
• Posts: 3,012
• Joined: 30-January 11

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 DavidB

Reputation: 3
• Posts: 32
• Joined: 20-July 06

Re: Maths requirements for Algorithm Analysis

Posted 31 August 2013 - 02:14 PM

Ryano121, on 29 August 2013 - 02:14 PM, said:

Really?

Wait .... is this irony? I am not good at picking that up.
If so, could you please wrap it in <irony></irony> tags. Then I'll know for sure if you are being serious . . . or not.

#8 macosxnerd101

• Self-Trained Economist

Reputation: 10964
• Posts: 41,006
• Joined: 27-December 08

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 three-dimensional 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 jjl

• Engineer

Reputation: 1118
• Posts: 4,632
• Joined: 09-June 09

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.