6 Replies - 476 Views - Last Post: 21 March 2019 - 08:32 PM

#1 dgupta111   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 66
  • Joined: 28-August 17

recommend foundation book

Posted 21 March 2019 - 05:45 AM

Hi,

I needed some recommendation about books on algorithms.Most of the problems on programming websites are reformulated as a word problem.For example,if I have to check whether a graph is bipartite,I would check if this doesn's has any odd cycles.This can be easily be reformulated as a word problem.Furthermore,if I have to check whether a graph is eulerian,I would find the degree of each vertex of the graph check whether it is even or I would use fleury's algorithm.There are many other examples.I am looking for a book to strengthen the foundations of algorithms and apply it to prove basic theorems that can be reformulated as a word problem at the next level with a constant learning curve.
are reading separate book on each algorithm in field of maths the only way to achieve this.Or is there any foundation book that can help me .THE Topics are combinatorial game theory,number theory,graph theory .Thanks

Is This A Good Question/Topic? 0
  • +

Replies To: recommend foundation book

#2 andrewsw   User is online

  • never lube your breaks
  • member icon

Reputation: 6807
  • View blog
  • Posts: 28,143
  • Joined: 12-December 12

Re: recommend foundation book

Posted 21 March 2019 - 06:12 AM

Do not use a nonsense title "Need help!" for your question. I have changed it for you.

What has this to do with Project Euler?
Was This Post Helpful? 0
  • +
  • -

#3 dgupta111   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 66
  • Joined: 28-August 17

Re: recommend foundation book

Posted 21 March 2019 - 06:50 AM

Sorry for posting in wrong forum.Its my mistake.I would be grateful if you transfer this discussion to another forum.
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 6992
  • View blog
  • Posts: 23,765
  • Joined: 05-May 12

Re: recommend foundation book

Posted 21 March 2019 - 01:01 PM

I highly recommend The Algorithm Design Manual by Steven S S. Skiena
Was This Post Helpful? 1
  • +
  • -

#5 cfoley   User is offline

  • Cabbage
  • member icon

Reputation: 2391
  • View blog
  • Posts: 5,023
  • Joined: 11-December 07

Re: recommend foundation book

Posted 21 March 2019 - 06:10 PM

A second vote for Skiena!

Once I realised there was a book budget at uni that nobody used, I requested this for the library. It then sat on my desk for about 2 years. I referred to it frequently. Great book for algorithms.
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12634
  • View blog
  • Posts: 45,800
  • Joined: 27-December 08

Re: recommend foundation book

Posted 21 March 2019 - 07:41 PM

Kleinberg and Tardos is excellent. CLRS is another good choice.

From Thomas Cormen (the C in CLRS):
https://www.quora.co...f-so-whats-next

Quote

Yes, Introduction to Algorithms really is an introductory text—on algorithms. It is not, and was never intended to be, an introductory text for computer science. We assume that the reader has some programming experience, including recursion, and knows how to read and write rigorous mathematical proofs. The discrete mathematics facts needed to analyze the algorithms in the book appear in the appendices.

As an algorithms text, it starts with insertion sort, one of the simplest of sorting algorithms. The algorithms and data structures covered in the first few sections are, for the most part, among the most basic. I think of the material in the first six parts of the book (except for the starred sections, which we consider graduate-level material) as part of the canon of computer science.

I understand that some people consider the book to be beyond introductory. We do go deeply into some material, and we pull no punches in the mathematics. From where the material starts, however, the book is most definitely an introduction.


You may also want to check out Rosen for a general introduction to discrete math and proof writing. Doug West is an amazing graph theory text.

For Combinatorial Game Theory, my understanding is that Berlekamp, Conway, and Guy is the standard text. I have heard mixed reviews about it and have not used it personally.
Was This Post Helpful? 0
  • +
  • -

#7 jon.kiparsky   User is online

  • Beginner
  • member icon


Reputation: 11604
  • View blog
  • Posts: 19,728
  • Joined: 19-March 11

Re: recommend foundation book

Posted 21 March 2019 - 08:32 PM

I have mixed feelings on trying to learn algorithms from any book. It seems to me that this is likely to be eventually successful, but you're going to miss a lot of key points and lose a lot of time. A lot of what's important about algorithms and algorithmic thinking is under the surface. There are many good books, and almost any book is good enough for the purpose - if you're in the hands of a good teacher who has prepared a good curriculum, with good assignments, and who does a good job of responding to the students in the class. Without those things, any book is going to be likely to leave you halfway there.

This is because the algorithms themselves are not actually the point. What is important is everything hanging around the algorithms - starting with the understanding of a problem and its representation in a computational context, ie, the choice of data structures and the insights that lead you to efficient representations, and continuing into the questions about how you can make use of the data structures, exploit their properties to reach an effective and efficient solution. You have to be able to think about high-level questions of general problem solving, and how to use apparently unrelated facts to limit search spaces and reduce the required work, and low-level concerns about implementation. You have to develop above all a feel for data structures - what trade-offs do they offer, and what set of compromises will best guide you to an answer? What sort of scaling is implied by a linked list, or by a tree? What sort of problem "smells like" a graph problem?
All of this is stuff that hovers in the zone between academic and execution, and no book or video will ever really get you there quickly. A good class, in person, with smart and engaged students, is really your best bet here.

So, failing that, I suggest you try working through the problems on the rosalind.info "Algorithmic Heights" track. These are reasonably well-crafted problems which play well with CLRS or with the text that they recommend, Dasgupta et al., and they'll at least force you to get out of the passive receptive mode that textbooks naturally inspire.

Quote

For Combinatorial Game Theory, my understanding is that Berlekamp, Conway, and Guy is the standard text. I have heard mixed reviews about it and have not used it personally.


I was first exposed to CGT through a course on coursera by Tom Morley. https://www.coursera...ial-game-theory
Morley comes across as a bit daft, but he exposes the material well, and it was actually quite enjoyable. No text was required, but you'll want to take good notes.

Winning Ways is good follow-up to that course, if you enjoyed it. Once you've soaked up some of the material it'll be good fun. It's certainly not written as a standard math text, it's more conversational and exploratory, but the math is all there.
Also worth a look is DEK's Surreal Numbers, which abuts this material in a nice way. That book is in the form of a novel, and Knuth's text is somewhat cringe-inducing at times, but he gives you plenty of stuff to sit down work on.
I honestly don't know if there's anything else that touches on this material

Quote

Doug West is an amazing graph theory text


For beginners who want to get a good grasp on the logic of graph theory, Trudeau's introduction is a must. He doesn't get incredibly far into the material, but what he covers is covered in depth and his writing is extremely clear. It's worth picking up a copy and working through it particularly if you're not very familiar with mathematical writing. It'll pave the way very nicely for a more standard text that covers the proofs more explicitly and rigorously.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1