6 Replies - 1366 Views - Last Post: 22 July 2012 - 01:55 PM

#1 Lemur  Icon User is offline

  • Pragmatism over Dogma
  • member icon


Reputation: 1381
  • View blog
  • Posts: 3,510
  • Joined: 28-November 09

Algorithm Math

Posted 21 July 2012 - 11:14 PM

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?

Is This A Good Question/Topic? 0
  • +

Replies To: Algorithm Math

#2 111027  Icon User is offline

  • D.I.C Head

Reputation: 17
  • View blog
  • Posts: 141
  • Joined: 26-December 11

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 D-r Rosen. It is in my opinion "the" book for discrete maths and introduction to algorithms.
Was This Post Helpful? 0
  • +
  • -

#3 peace_fixation  Icon User is offline

  • D.I.C Head

Reputation: 46
  • View blog
  • Posts: 198
  • Joined: 01-November 11

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. :)
Was This Post Helpful? 1
  • +
  • -

#4 111027  Icon User is offline

  • D.I.C Head

Reputation: 17
  • View blog
  • Posts: 141
  • Joined: 26-December 11

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.
Was This Post Helpful? 0
  • +
  • -

#5 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1156
  • View blog
  • Posts: 2,538
  • Joined: 05-May 05

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, depth-first and breadth-first 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 Big-Oh for relatively simplistic algorithms and what Big-Oh describes. It also covers elementary combinatorics, graphs, discrete probability, induction, and recurrences in enough detail that you can tackle many of the non-trivial 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

Was This Post Helpful? 1
  • +
  • -

#6 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10767
  • View blog
  • Posts: 40,093
  • Joined: 27-December 08

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 Big-O 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)
Was This Post Helpful? 0
  • +
  • -

#7 Lemur  Icon User is offline

  • Pragmatism over Dogma
  • member icon


Reputation: 1381
  • View blog
  • Posts: 3,510
  • Joined: 28-November 09

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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1