21
$\begingroup$

I often interact with people who want to ask for an algorithm for a computational problem (or its complexity), but they don't express it in a rigorous way for us (computer scientists) to understand.

Referring them to books like CLRS is not helpful because the examples there usually have a quite straightforward way of stating rigorously, e.g. given the adjacency list of a graph and two vertices in it compute the shortest path between those vertices.

Is there any good book (or some other resource) where a person with minimal knowledge of CS can learn how one should formulate and state computational problems in a rigorous way that is understandable to computer scientists?

Preferably the book should have many examples of how to formulate computational problems rigorously from various domain and real world examples.

Clarification

To make the question more specific, let's assume that they know basic math/CS terminology like sets, functions, graphs, lists, etc. at the level of 1st/2nd year undergraduate CS student (which is the case with people who I have in mind). For example, they have read some introductory textbook like Aho and Ullman (although they might not have understood it completely).

Improve this question
$\endgroup$
12
  • 2
    $\begingroup$ I think this is a good question, but I don't know if there's a good answer. I feel like it's kind of asking for "Is there a way we can teach someone who's not a computer scientist to think like a computer scientist?" And the answer to that is "yes, make them a computer scientist." That said, some software engineering researchers may have done studies on stuff like this. $\endgroup$
    – Joey Eremondi
    Commented Jul 9, 2013 at 0:40
  • 3
    $\begingroup$ Also, I think this is what use cases are for, to a degree. If someone doesn't understand how to properly formulate their problem, the list a number of scenarios of what they'd like a given program to do, and the expected behavior in each case. The programmer then develops a specification from that. That said, I'm a theory person, not an engineer, so if I'm wrong, feel free to correct me. $\endgroup$
    – Joey Eremondi
    Commented Jul 9, 2013 at 0:41
  • $\begingroup$ @jmite, thank you for the comments. You are right that part of Software Engineering is to try to understand what a client wants (I think they call it requirement analysis). But that is usually for large projects. I am not talking about such projects, but simple questions like those we get on this site which are not rigorously stated. I have seen books teaching people how to state a statement in logic with many examples. I am hoping that there is something similar for algorithms and computational problems. $\endgroup$
    – Kaveh
    Commented Jul 9, 2013 at 0:48
  • 1
    $\begingroup$ That said, I am of the opinion it requires a certain way of thinking that is not easily acquired, especially by adults. I have tried to get people to drop the technical stuff and explain the problem as simply as possible in terms of everyday objects. The problem is, they will usually forget some constraint, or they will make it sound like an operation that is O(N) in their actual system is O(1), and so on. So I will end up with something very close to a rigorous definition of the wrong problem. $\endgroup$
    – svinja
    Commented Jul 9, 2013 at 16:35
  • 2
    $\begingroup$ in a way, what is asked for is contradictory, because formulating problems rigorously is exactly one of the key learned skills that separates laymen from specialists/professionals... $\endgroup$
    – vzn
    Commented Jul 11, 2013 at 17:02

3 Answers 3

Reset to default
3
$\begingroup$

a good resource on/for this, fairly well known by academics but not so widely known outside of specialists, is Mathematical Writing by Donald E. Knuth, Tracy L. Larrabee, and Paul M. Roberts. there is a published book, lecture videos, and a set of notes. it is more written from the perspective of people attempting to master mathematical writing eg for creating papers, but all the advice is highly applicable to the case of laymen attempting to formulate problems precisely. mathematical writing while formidable to learn is the scientific approach to rigorously define/formulate—and as the book details, solve, eg via algorithms or proofs—computational/algorithmic problems.

also, the classic Garey & Johnson text, Computers & Intractability does not exactly describe how to formulate problems precisely, but it does give many examples, and diverse theoretical/conceptual/technical "patterns", organized into sections of similar problems, which can be used as "building blocks" to describe computational/algorithmic problems.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks vzn, these are nice resources about writing mathematics but I am not looking for something different. The issue is not writing well in mathematics but resources for people to learn how to formulate computational problems clearly enough so an expert can understand what the person asking the question is looking for and help them. $\endgroup$
    – Kaveh
    Commented Jul 12, 2013 at 5:34
  • $\begingroup$ yw; you say those are two different things, and in words/phrases they are, but & I say they are [to borrow a software engineering phrase] "tightly coupled" $\endgroup$
    – vzn
    Commented Jul 12, 2013 at 15:05
3
$\begingroup$

just ran across this nice/neat, unusual, relatively new/unknown ref on his home page by Emmanuele Viola, prof (T)CS at Northeastern University) apparently unpublished elsewhere. 41pp. it starts out with very basic mathematical concepts eg implication and then ranges all the way into advanced topics like the Erdős–Szekeres theorem and Ramsey theory.

Improve this answer
$\endgroup$
0
$\begingroup$

Buy the book Algorithms and Data Structures from Robert Lafore.

On this book, every algorithm is explained as a story, very much like a poetry. Then, give the person the Lafore version of an algorithm, and later the CLRS version.

Maybe like this, the person will get a feeling on how to translate from intuitive description to rigorous ones.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.