Resources on proving algorithms correct?

  • Context: Undergrad 
  • Thread starter Thread starter BicycleTree
  • Start date Start date
  • Tags Tags
    Algorithms Resources
Click For Summary

Discussion Overview

The discussion centers around finding resources for formally proving algorithms correct. Participants express a desire for accessible materials that provide a precise treatment of algorithm definitions and proofs, indicating a focus on theoretical understanding rather than informal explanations.

Discussion Character

  • Exploratory, Technical explanation

Main Points Raised

  • One participant requests resources for formal treatments of algorithm correctness, expressing frustration with the informal nature of available information.
  • Another participant suggests "The Art of Computer Programming" by Donald Knuth as a potential resource.
  • A different participant recommends "Introduction to Algorithms" by Cormen, Leiserson, and Rivest, noting its suitability for the original request.
  • The initial requester acknowledges the value of "The Art of Computer Programming" but indicates it may be too comprehensive for their current needs, while expressing that "Introduction to Algorithms" appears to meet their requirements.

Areas of Agreement / Disagreement

Participants generally agree on the value of the suggested resources, but there is no consensus on a single best option, as preferences vary based on individual needs for comprehensiveness.

Contextual Notes

Participants have not defined what constitutes a "formal treatment" or provided specific criteria for evaluating the resources suggested. There is also no discussion of the prerequisites needed to understand the materials mentioned.

Who May Find This Useful

Individuals seeking to understand formal proofs of algorithms, particularly those with some background in algorithms and computer science.

BicycleTree
Messages
519
Reaction score
0
Where can I find resources on proving algorithms correct? I'm looking for a formal treatment (hopefully I have enough background by now to absorb that). I keep seeing these proofs of algorithms and references to proofs of algorithms but everything is informal and I've never even seen a precise definition of "algorithm."

I can't find much on Google or Mathworld. Judging by the online descriptions of courses about algorithmic proof, there must be plenty of information out there, but it's not very accessible. I'd appreciate any suggestions.
 
Mathematics news on Phys.org
"The Art of Computer Programming" by Donald Knuth.
 
There's also Introduction to Algorithms, Cormen Leiserson and Rivest.
 
Thanks. The Art of Computer Programming looks very good, but it's probably more comprehensive than I'm looking for right now. Introduction to Algorithms looks like it's exactly what I seek.
 

Similar threads

Undergrad Is an algorithm for a proof required to halt?
  • · Replies 3 ·
Replies
3
Views
2K
High School Are Inverse Problems More Complex Than Direct Problems in Mathematics?
  • · Replies 13 ·
Replies
13
Views
3K
Undergrad The Universe is No Simulation
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad Proof of the Halting Problem's Unsolvability
  • · Replies 16 ·
Replies
16
Views
4K
Graduate Resources on non-spherical conductor surface charges
  • · Replies 3 ·
Replies
3
Views
1K
Undergrad Gaussian elimination: Proof of correctness
  • · Replies 13 ·
Replies
13
Views
8K
What is the loop invariant for this algorithm?
  • · Replies 16 ·
Replies
16
Views
5K
Schools What are some good science fair project ideas or resources?
  • · Replies 5 ·
Replies
5
Views
5K
Undergrad I need a better "method" for working out proofs and problems
  • · Replies 4 ·
Replies
4
Views
1K
Undergrad Can somebody look over my proof? (Asymptotic notation and algorithms)
  • · Replies 4 ·
Replies
4
Views
2K