For the life of me, I cannot figure out what form of mathematics are used to describe algorithms. I've only really had up to College Algebra and never bothered with anything past that (...which is making things difficult to understand.)
I assume it's something to the extent of Set Math, but for some algorithms and more advanced formulas I have no idea where to start to find anything.
Is there any resource to look up symbols or otherwise? I would go through classes, but I would prefer to know which ones to look into.
Algorithms and advanced programming have always been interesting to me, but coming from a SysAdmin/Ops background it's not been entirely necessary. Despite this, I'd like to get to a more advanced level of programming, if for nothing else than personal satisfaction and pet projects.
So put simply, where should one start to learn high level algorithms if they only have College Algebra as the highest actual math class?
Algorithm Math
Page 1 of 16 Replies  1388 Views  Last Post: 22 July 2012  01:55 PM
Replies To: Algorithm Math
#2
Re: Algorithm Math
Posted 22 July 2012  01:28 AM
Have you ever heard of discrete mathematics? That is basically where algorithms are used the most. It deals with a bunch of things you need, as well as algorithms themselves. Look up the book "Discrete mathematics and its applications" by Dr Rosen. It is in my opinion "the" book for discrete maths and introduction to algorithms.
#3
Re: Algorithm Math
Posted 22 July 2012  01:29 AM
You don't need much math to study algorithms, just algebra and basic functions, and it sounds like you have covered these.
Introduction to Algorithms  Thomas Cormen (and co.) is the canonical text that has been recommended to me by many people. It will provide all that you need.
Introduction to Algorithms  Thomas Cormen (and co.) is the canonical text that has been recommended to me by many people. It will provide all that you need.
#4
Re: Algorithm Math
Posted 22 July 2012  01:32 AM
In my experience, that depends on what you intend to do, and how deep you need to go. If you just want to learn common algorithms, you only do need algebra. But if you want to design novel algorithms... it's a bit of a different subject. For an example, I've worked on several algorithms with the cryptography professor at my school, and maths knowledge was imperative. Not only in the development of the algorithms (which were highly mathematical), but also in their proof, verification and analysis.
#5
Re: Algorithm Math
Posted 22 July 2012  10:40 AM
Let me start off by saying that, as mentioned, many analyses only require a knowledge of algebra and trigonometric functions. If you've got that down (and some programming background), you could probably start the simpler algorithms right now: linear and binary search; selection, insert and merge sort; heaps, depthfirst and breadthfirst search, travelling salesman, etc. Ultimately, you'll need good knowledge of discrete mathematics.
Rosen's book is good for beginners; it'll give you a sense of how to do BigOh for relatively simplistic algorithms and what BigOh describes. It also covers elementary combinatorics, graphs, discrete probability, induction, and recurrences in enough detail that you can tackle many of the nontrivial proofs that come up. The book also covers the psudeocode for many of the common algorithms, so that should help greatly.
Once you read through Rosen, you can move onto Introduction to Algorithms. It depends heavily on the five subtopics above for its proofs. You'll also find some calculus, but not much and it's probably OK to skip it anyway. CLRS is the canonical source (it's very thorough and understandable), but there are plenty of other good books on algorithms and analysis that aren't so dry and mathematically intense.
Algorithms by Dasgupta et. al
Algorithm Design
Actually, I've never even read those books, but I've heard they're a little easier to digest.
You'll find that many of analyses take leaps of intuition that have nothing to do with Math. Once those ideas are established and can be formally verified then the Math becomes necessary.
Have you considered taking an online course in algorithms? I'd pick up Rosen's book and enroll in a course.
Rosen's book is good for beginners; it'll give you a sense of how to do BigOh for relatively simplistic algorithms and what BigOh describes. It also covers elementary combinatorics, graphs, discrete probability, induction, and recurrences in enough detail that you can tackle many of the nontrivial proofs that come up. The book also covers the psudeocode for many of the common algorithms, so that should help greatly.
Once you read through Rosen, you can move onto Introduction to Algorithms. It depends heavily on the five subtopics above for its proofs. You'll also find some calculus, but not much and it's probably OK to skip it anyway. CLRS is the canonical source (it's very thorough and understandable), but there are plenty of other good books on algorithms and analysis that aren't so dry and mathematically intense.
Algorithms by Dasgupta et. al
Algorithm Design
Actually, I've never even read those books, but I've heard they're a little easier to digest.
You'll find that many of analyses take leaps of intuition that have nothing to do with Math. Once those ideas are established and can be formally verified then the Math becomes necessary.
Have you considered taking an online course in algorithms? I'd pick up Rosen's book and enroll in a course.
This post has been edited by blackcompe: 22 July 2012  10:47 AM
#6
Re: Algorithm Math
Posted 22 July 2012  12:55 PM
I've never looked at Rosen's book personally, but I've worked with both the Epp and Johnsonbaugh Discrete Math textbooks. Epp is a less technical approach that's good for starting out. Johnsonbaugh isn't as thick as Epp, and is more technical in nature. I think Johnsonbaugh is good for introductory algorithm analysis personally.
If you're at school, you might consider enrolling in a proofs class as well to get a feel for things. I have a couple tutorials you may find helpful:
Introduction to Solving Linear Recurrences (if you've taken a Diff Eqs class, this should look familiar)
Introduction to BigO and Induction Proofs (this one isn't exactly what you would be doing in an Algorithm Analysis class, but it's a good starting point to get into some of the process)
If you're at school, you might consider enrolling in a proofs class as well to get a feel for things. I have a couple tutorials you may find helpful:
Introduction to Solving Linear Recurrences (if you've taken a Diff Eqs class, this should look familiar)
Introduction to BigO and Induction Proofs (this one isn't exactly what you would be doing in an Algorithm Analysis class, but it's a good starting point to get into some of the process)
#7
Re: Algorithm Math
Posted 22 July 2012  01:55 PM
At this point I'm a College Senior. My entire focus to this point has been System Administration. Most of my history in programming has been C# and .NET, but anything I've done professionally has been in Ruby.
I've gotten into metaprogramming and trying to figure out more advanced aspects of languages. At this point syntax and basic concepts really aren't a problem as much as knowing application. My weakness at this point is knowing algorithms and advanced application.
I ended up buying a few books:
Introduction to Algorithms:
http://www.amazon.co...duct/8120340078
The Algorithm Design Manual:
http://www.amazon.co...duct/1848000693
I was reading some articles on how to score a job in Development with Google and the like. Despite been a SysAdmin, I'd much rather be able to pull a jack of all trades and be ready for any potential job.
A majority of the annoyance for me is seeing algorithms written out in what looks to be complete french. I work in commercial wireless, and I keep trying to find new ways to do things. Problem is most are in algorithm notation and I can't tell where in the world to even start. All these interesting ideas like azimuth, game theory, fresnal, and other such things are fascinating, but I can't understand implementation without that knowledge.
I've gotten into metaprogramming and trying to figure out more advanced aspects of languages. At this point syntax and basic concepts really aren't a problem as much as knowing application. My weakness at this point is knowing algorithms and advanced application.
I ended up buying a few books:
Introduction to Algorithms:
http://www.amazon.co...duct/8120340078
The Algorithm Design Manual:
http://www.amazon.co...duct/1848000693
I was reading some articles on how to score a job in Development with Google and the like. Despite been a SysAdmin, I'd much rather be able to pull a jack of all trades and be ready for any potential job.
A majority of the annoyance for me is seeing algorithms written out in what looks to be complete french. I work in commercial wireless, and I keep trying to find new ways to do things. Problem is most are in algorithm notation and I can't tell where in the world to even start. All these interesting ideas like azimuth, game theory, fresnal, and other such things are fascinating, but I can't understand implementation without that knowledge.
Page 1 of 1
