Algorithms and Data Structures

[raghav singh]

Hi,

Can someone guide me here? I know nothing about algorithms and data structures.Is there any good books where I can start learning it.

Should I also learn advanced mathematics?


Thanks for reading.

[Dipta P Banerjee]

There are lots of books for the same and I am not sure which one is/are the best. This is not the direct answers of your question but I will prefer to go through the online free courses by Coursera. I have personally taken those courses and they are great.

[Winston Gutkowski]

raghav singh wrote:Can someone guide me here? I know nothing about algorithms and data structures.Is there any good books where I can start learning it.

Well, a quick Google got me this list, of which this is the grandaddy of them all (albeit geared more for mathematicians than programmers).

Should I also learn advanced mathematics?

Nah. Or not unless you want to. I've managed for 35 years with my grade 'D' A-Level.

Winston

[raghav singh]

I've managed for 35 years with my grade 'D' A-Level

So that means you got a lifetime of experience.About algorithms, how many are known?Should I learn all of them.Or it is an infinite list.

Or it there something like some base algorithms from which all algorithms are derived from??

[Paweł Baczyński]

raghav singh wrote:Or it there something like some base algorithms from which all algorithms are derived from??

Short answer: no.

Longer answer:
Yes, it is:
1. get the input
2. produce an output

[raghav singh]

Paweł Baczyński wrote:

raghav singh wrote:Or it there something like some base algorithms from which all algorithms are derived from??

Short answer: no.

Longer answer:
Yes, it is:
1. get the input
2. produce an output

Can you elaborate more on what you mean?

[Paweł Baczyński]

No problem.
I think that there is no general universal algorithm.
The only things various algorithms have in common is that they require some data, they process it and return some result.
This could be listed in two steps as I did.
And those two steps can be considered an algorithm itself

[Winston Gutkowski]

raghav singh wrote:About algorithms, how many are known?

Ooooodles.

Should I learn all of them. Or it is an infinite list.

As close to infinite as makes no difference.

Or it there something like some base algorithms from which all algorithms are derived from??

There are certainly a few that are worth knowing about:

For structures, I'd say: heaps, hash tables, trees (particularly binary trees). Also, if you feel so inclined: skiplists.

For algorithms: binary chops; a few sorts (eg, Quicksort, Heapsort, and possibly Merge sort - although it may be best to start out with a simple Bubble sort).

I suspect that'll get you started, and it's purely my opinion. I'm sure others will add to it if they think I've missed out something vital (which I'm sure I have ).

HIH

Winston

[raghav singh]

Paweł Baczyński wrote:No problem.
I think that there is no general universal algorithm.
The only things various algorithms have in common is that they require some data, they process it and return some result.
This could be listed in two steps as I did.
And those two steps can be considered an algorithm itself

OK. I just go an "Aha..moment".

[Campbell Ritchie]

Winston Gutkowski wrote: . . . simple Bubble sort). . .

When I started learning Java there were several reliable ways to wind up Elizabeth who was teaching. Speaking French was one, saying, “bubble sort” was another.

It is worth learning about the complexity of a few of those sort algorithms, and why bubble sort is the least efficient known to modern science.
Then find out when bubble sort might be the best kind of sorting algorithm

[Paweł Baczyński]

Campbell Ritchie wrote:It is worth learning about the complexity of a few of those sort algorithms, and why bubble sort is the least efficient known to modern science.

Not true. The winner in this category is Bogosort.

[raghav singh]

How does one study algorithms and data structures?.I mean what are the approach you guys use to study algorithms and data structures?

[Winston Gutkowski]

raghav singh wrote:How does one study algorithms and data structures?.I mean what are the approach you guys use to study algorithms and data structures?

Well, apart from the ones I mentioned, my approach is "Google as I find a need" (or check my weatherbeaten old copy of TAOCP and curse that I didn't take advanced Maths ).

Winston

[Ulf Dittmer]

Paweł Baczyński wrote:
1. get the input
2. produce an output

This is often written in 3 steps: 1) input, 2) processing, 3) output. Coincidentally, the Feynman Problem Solving Algorithm also has 3 steps: 1) Write down the problem, 2) Think very hard, 3) Write down the answer.

[Winston Gutkowski]

Ulf Dittmer wrote:Coincidentally, the Feynman Problem Solving Algorithm also has 3 steps: 1) Write down the problem, 2) Think very hard, 3) Write down the answer.

Another link to bookmark.

About the only thing I'd add to that is that, for the first two steps (especially the first), observe the 'WhatNotHow' (←click) rule.

Winston

[raghav singh]

So I guess I will start with TAOCP.

[Ulf Dittmer]

TAOCP is not a good book for beginners - it's more a reference than a tutorial or introduction to be read from start to finish. Wirth's Algorithm and Data Structures is still of interest (and freely available as PDF), and (somewhat newer) Cormen/Leiserson/Rivest's Introduction to Algorithms is not bad.

[raghav singh]

Ulf Dittmer wrote:TAOCP is not a good book for beginners - it's more a reference than a tutorial or introduction to be read from start to finish. Wirth's Algorithm and Data Structures is still of interest (and freely available as PDF), and (somewhat newer) Cormen/Leiserson/Rivest's Introduction to Algorithms is not bad.

Ayaye, I was about to order TAOCP.Just in time my mail pop ups.

I check out the free book first and then later will buy introduction to algorithms

[chris webster]

raghav singh wrote:How does one study algorithms and data structures?.I mean what are the approach you guys use to study algorithms and data structures?

There's still time to join the free online course in Algorithmic Thinking from Coursera, which just started on Monday.

Several JavaRanchers seem to be following the course - https://coderanch.com/t/638573/Bunkhouse-Lounge/Online-Algorithmic-Thinking-Rice-University

[Campbell Ritchie]

Damn! I forgot about b*gg**sort b*gg***ffsort b*g*fsort Bogosort.

[Campbell Ritchie]

The important part of the Feynman algorithm is that it makes you write down the problem. As we all know, that can be half the battle.

[raghav singh]

chris webster wrote:

raghav singh wrote:How does one study algorithms and data structures?.I mean what are the approach you guys use to study algorithms and data structures?

There's still time to join the free online course in Algorithmic Thinking from Coursera, which just started on Monday.

Several JavaRanchers seem to be following the course - https://coderanch.com/t/638573/Bunkhouse-Lounge/Online-Algorithmic-Thinking-Rice-University

I just joined Algorithmic Thinking as suggested by you.Also I might join algorithm part I and part 2 which also seem interesting.It will start on September 5.

[Matthew Brown]

raghav singh wrote:Also I might algorithm join part I and part 2 which also seem interesting.It will start on September 5.

Those are excellent (I haven't done Algorithmic Thinking, so I can't comment). And the examples and assignments are in Java, which is an advantage if that's what you're familiar with.

[raghav singh]

Matthew Brown wrote:

raghav singh wrote:Also I might algorithm join part I and part 2 which also seem interesting.It will start on September 5.

Those are excellent (I haven't done Algorithmic Thinking, so I can't comment). And the examples and assignments are in Java, which is an advantage if that's what you're familiar with.

Yeah, that what I thought.

[fred rosenberger]

I've been a fan of Polya's How to Solve It. It is kind of an algorithm on how to come up with your algorithm.

[Winston Gutkowski]

fred rosenberger wrote:I've been a fan of Polya's How to Solve It. It is kind of an algorithm on how to come up with your algorithm.

Looks interesting. I might try to find a copy.

@raghav: Sorry if I sound like I'm banging on about it, but I reckon the business of "what, not how" is incredibly important - especially for beginners. In fact, I'd say it's possibly the single biggest lesson I've learned in my 35 years; and it's quite difficult to master.

I think we all have a natural tendency, when we're looking at a problem, to leap immediately to a solution - or at least to want to - because we don't like "not knowing". But it's a flawed approach; specifically:

It tends to preclude "new" solutions (or algorithms), because we tend to look for - or use - the familiar ones first.

It's likely to be "targeted", and therefore brittle.

It sometimes (unfortunately) gets you quick results, which makes you think you've "solved it", when in fact you've actually gone down a blind alley.

Learning to describe a problem in English, before you start to solve - and in particular, describing what it's supposed to do rather than how it's supposed to do it - is a really good habit to get into; but it takes some practice.
You'll find the rewards further down the road though. Furthermore, OO languages like Java have all sorts of constructs that allow you to avoid making critical "how" decisions before you're ready.

Know that your problem needs a Widget, but don't know what it's going to look like? Create an interface and bang a few method signatures into it. Know that some class you've written needs a draw() or plot() method, but don't know exactly what it's supposed to do? Create a stub that simply throws an Exception (UnsupportedOperationException is my favourite) until you do.

What you'll find is that it leads to a natural "big picture first" style that allows you to "fill in the blanks" as you get into more and more detail. It also helps you not to be overwhelmed by the scale of the problem, or your lack of knowledge about particular algorithms. Need a sort? Create a sort() method (or class, or interface) and leave it blank until you're ready to tackle it.

My 2¢.

Winston