Algorithms in C

Question

What is the best place or a link to learn algorithms in C? How do you know when and where to use the implementation of algorithms by just looking into the problems?

Answer 1

Algorithms aren't necessarily tied to a specific language, just to clarify, so any algorithms book will work great as long as you can understand the concept being the data structure/algorithm.

That said, this seems like a good choice: Algorithms in C. I have the C++ equivalent on my shelf.

There is also a book that seems language agnostic (correct me if I'm wrong) called Data Structures & Algorithm's, though I hear it's a bit dated, so you'll miss out on more recent structures.

Don't forget the internet has a plethora of information available to you. However, books are usually better for these sorts of things. This is because internet resources tend to focus on one thing at a time. For example, you need to understand what Big-O notation is before you can understand what it means when we say a List has O(1) [constant time] removal.

A book will cover these things in the correct order, but an internet resource will focus on either Big-O notation or data structures, but often won't easily connect the two.

---

When it comes to using it, you'll mostly make the connection when it comes to what you'll be doing with the data.

For example, you might want a vector (array) if you just need ordered elements, but if you need ordered elements and removal from any place (but can sacrifice random access), then a list would be more appropriate, due to it's constant-time removal.

Answer 2

For a reasonable (though far from perfect) book on implementing commonly used algorithms in C, try Sedgewick's Algorithms in C. Note that as for any technical subject,a paper book is likely to be far superior to any Web resources.

As to how to know when to use a specific algorithm, I'm afraid that is down to experience.

Answer 3

For an algortihms text, Cormen, Leiserson and Rivest's 'Introduction to Algorithms' is a good start. The pseudocode implementations are easy to translate to C. Two web resources with many links to documentation about algorithms and sample implementations are:

• Stony Brook Algorithm Repository

• NIST Directory of Data Structures and Algorithms

Answer 4

Algorithms in C by Sedgewick is a great place to start the investigation. Once you are familiar with what algorithms are available and what the performance characteristics of each are, you'll be able to see where to use each of them.

Answer 5

This is my collection of mostly math-related algorithms:

List of algorithms

FXT (math related)

Numerical Methods

Numerical Recipes in C

Answer 6

How do u know when and where to use the implementation of algorithms by just looking into the problems

It's called "pattern matching", once you've seen and solved lots of problems you start to recognize common things and you can reuse your previous knowledge.

By the way, I would recommend you before a good book just on algorithms before starting with algorithms in C, which are more difficult to implement and more error prone than in higher level language, and once you are very confident with the general procedures you can start to tweak and optimize them in C.

Answer 7

Many good resources have already been named, so I won't repeat them here.

As for how do you know what algorithm to use when?

• You need to have a big enough tool box, which you will obtain by sitting down and slogging through a long list of basic (and them more esoteric) data structures and algorithms. You should try to get all the basics, but really only need a sample from the more specialized ones.

• You need to understand what trade offs are available to you (time, code complexity, memory, single versus multiple passes, in-place versus copy, stable versus unstable sorts, etc. ad nauseum), and how the algorithms you study do on each of these. Again, this is just a case of much studying. Big-O is a place to start, but is not the end all and be all of this.

• You need to get a feel for understanding what are the real limits you face when presented with a problem, and how to express these in terms of the algorithm trade offs mentioned above. This requires a degree of intuition, and is generally learned by practice over time.

• It is worth implementing some things more then one way as you go along, to learn in your gut, what works and what doesn't.

• It is worth reading code written by folks more experienced than yourself, to see how they think.

Good luck.

Answer 8

The Wikipedia List of Algorithms is also very handy reference.
And, if you want to get deeper -- The Art of Computer Programming (wikipedia ref).
Preferably after the Robert Sedgewick book already referred in multiple answers.

Answer 9

I read Pointers on C by Kenneth Reek recently. I thought I was pretty well versed in C, but this book gave me a few epiphanies, despite being aimed at beginners. The code examples are things of beauty (but not the fastest code on a x86-like CPU). It provide good implementations of many of the most common algorithms and data-structures that are in use, with excellent explanations about why they are implemented as they are (and sometimes code or suggestions for alternative implementations).

On the same page as your question: patterns for creating reusable code in C (that is what we all want, isn't it?), C Interfaces and Implementations: Techniques for Creating Reusable Software, by David R. Hanson. It has been a few years since I read it, and I don't have a copy to verify what I recall is correct, but if I remember correctly it deals with how to create good C API:s to data structures and algorithms, as well as giving example implementations of some of the most common algorithms.

Of topic: As I have mostly written throw-away programs in C for private use, this one helped me get rid of some bad coding habits as well as being an excellent C reference: C: A reference Manual. Reminds me that I ought to buy that one.

Answer 10

One needs experience to know which set of algorithms to use for a particular problem. Defining a goal will help. Speed, memory, robustness, solution quality ... are all factors in determining which algorithms to use. We could devise different solutions to the same problem given different set of factors and scenarios.

Answer 11

The Algorithm Design Manual is worth a look.

Answer 12

A easy method to learn algorithms is to use Wiki page, who is dedicated to some "classical" algorithms like search algorithms or for sort. The constructions of algorithms is based on ability to use different data structures, like linked lists or C. So, first try to implement different data structures like simple linked list or binary tree, and after try to use in different algorithms who is related to real life problems.