19
$\begingroup$

I am a graduate student taking a course in theory of computation and I have serious trouble producing content once I'm asked to. I'm able to follow the textbook (Introduction to the Theory of Computation by Michael Sipser) and lectures; however when asked to prove something or come up with a formal description of a specific TM, I just choke.

What can I do in such situations? I guess my issue is with fully comprehending abstract concepts to the point I can actually use them. Is there a structured way to approaching a new, abstract concept and eventually build intuition?

Improve this question
$\endgroup$
6
  • 6
    $\begingroup$ beats me. this seems like a reasonable question for this site. $\endgroup$
    – Suresh
    Mar 14, 2012 at 4:19
  • 4
    $\begingroup$ I voted to close. The main issue I see is that the question is not actually about computer science; it's about how to learn computer science. The latter does not have an objective answer, because each person will have their own best way. The three votes to close are all assigned to the "too localized" reason, but I think this question is also off topic, since it's not about computer science. $\endgroup$
    – Carl Mummert
    Mar 14, 2012 at 20:40
  • 1
    $\begingroup$ I think this question has merit and its the type of question that I struggle with intensely. I think that getting guidance on these types of issues from a trusted community is something many CS students struggle with. I do understand the objection to the question though. It seems to me that the question is quite apropos to the meta section of this site though. $\endgroup$
    – BrotherJack
    Apr 22, 2012 at 20:36
  • 7
    $\begingroup$ @CarlMummert: Every question about computer science is a question about how to learn computer science. $\endgroup$
    – JeffE
    Apr 23, 2012 at 21:19
  • 2
    $\begingroup$ The question is overly broad in its current form. Focus your question, e.g. ask for resources (e.g. problem books) to help improve your ability to solve question in the course, or if you have a specific example focus on that problem and ask about intuition or methods to approach similar problems. $\endgroup$
    – Kaveh
    May 17, 2012 at 0:32

4 Answers 4

Reset to default
15
$\begingroup$

Abstraction is pretty much bread and butter in computer science but unfortunately it is hard to teach explicitly.

In my opinion, understanding concepts is more important than being able to mechanically calculate or prove stuff. Sure, you need to know your way around some elementary methods, but the meat lies elsewhere.

First of all, you have to grasp the content to some extent. To this end, I have found it useful to ask the following question whenever something is unclear to you:

  • Why are we doing this?
  • What are we going to use this for?
  • What similar things does this relate to?
  • How do other sources explain it?
  • What exactly do I not understand?

After you have answered these questions (or discovered follow-up questions and treated them the same way) and still have problems, go to your teachers (or here). By now you should be able to formulate a focused, precisely formulated question; answering such questions is your teachers' job (and StackExchange's philosophy).

Other than that, it is exercise and experience. Try to reproduce proofs after having read them; take care to not learn them by heart but distill the important ideas from them. After some time, you should be able to reproduce all basic proofs by filling in gaps between the major steps. Even later, you will begin to see patterns in statements and proofs. This is how people look at a statement and say "Oh yeah, sure, use method X with theorem Y and then just use Z to get what you want.". It is pattern recognition fueled by years of training. Be patient.

As for basic exercises, go and find text books with some. Off the top of my head I can refer to Concrete Mathematics by Graham, Knuth, and Patashnik. This book is not only a precious toolbox for computer scientists, it also contains loads of exercises with solutions (!). Remember to attempt to solve them before looking up the answers and to reproduce answers you had to look up.

Another useful book is Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein. Included is a sizeable chapter on mathematical basics. It also contains many exercises; solutions are available via the linked page (Supplemental Content). There is also a video lecture by one of the authors which may go nicely with the book.

For introductore lectures regarding proofs, have a look at Linear Algebra Proofs on Khan Academy. I have not watched them, but hopefully they are both basic and helpful. There are many more proofs on Khan Academy; I just figure that linear algebra proofs might fit computer science best. Do no hesitate to watch others, too.

Improve this answer
$\endgroup$
3
  • 7
    $\begingroup$ I agree that understanding concepts is more important than ability to calculate or prove stuff. But understanding is the result of practice with calculations and proofs, not a substitute for that practice. $\endgroup$
    – JeffE
    Mar 13, 2012 at 23:42
  • $\begingroup$ Thank you for the insight. I'll take your advice dearly and try to improve based on that. $\endgroup$
    – trigoman
    Mar 14, 2012 at 1:39
  • $\begingroup$ For more basic needs, the Book of Proof may be a valuable reference. $\endgroup$
    – Raphael ♦
    Sep 12, 2013 at 8:55
8
$\begingroup$

I sometimes find out that people that don't do well in theory, just have the basics wrong (on the first 1-3 lectures, they thought the material is very easy, so they didn't pay too much attention, but then, at lecture 5-7 things speed up and it's too late to recap).

As @fbernardo said, it might be a good idea to start from the beginning. NOT as far as FLA (there is no use in that when studying TC, IMHO), but definitely open Sipser and start solving the questions one by one, by their order. With the experience you'll get intuition and basic tools that are imperative for more advanced concepts.

If you cannot cope with Sipser's basic questions of the first chapter (not the automata chapters, if you study on TMs), then you might be lacking even more fundamental concepts, such as basic proof methods (induction, etc.) or basic set-theory and discrete math.

Good luck, anyways!

Improve this answer
$\endgroup$
3
$\begingroup$

My only advice would be that you start from the beginning. In my course we use Sipser's book too, it is a good book in my opinion. But we do have a course before TC, named FLA (Formal Languages an Automaton) that gave be a better intuition and background on TC. So, again, everybody learns at different rates, and you have a very good book. Any other specific question you can always find help here. :)

Improve this answer
$\endgroup$
2
$\begingroup$

You ask a general question in your title and then at least two basic/specific points in the question, and I think there are good (separate) answers to each one:

  • how to prove stuff
  • create formal descr of a TMs behavior

Here addressing only the 1st item (which is inherently broad & deserves it)-- its sort of the elephant in the room of STEM (science, technology, engineering, mathematics) education that gets short shrift & is often glossed over to a staggering degree. It might seem as if nobody really knows how to teach how to build proofs. This subj starts out in geometry, trigonometry and calculus classes, but is rarely a strict element of it. most teachers treat it as optional. It seems an entire class dedicated to "how to prove stuff" would be an excellent or even critical addition or change to STEM education.

Here are some refs that I turned up on a quick search for how to prove stuff, & I think there are many other good resources. Nowadays also there are probably many videos on the subject that could be turned up via searches, but I havent seen a nice comprehensive organization of "how to prove stuff" type videos.

A key part of proving is to master the basics of mathematics and use it all as tools or building parts. Eg know what a set is, what a tuple is, what the difference/similarity is, when you would use one but not the other, etc.

Another approach is to treat it like a drill. Do many practice proofs on your own, starting from easy to difficult (wish I knew of more books like this, there dont seem to be many).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Add Pólya's classic "How to solve it". It is also useful (specially for graduates) to look around for mathematical writing, e.g. Knuth et al "Mathematical writing". This is a skill too often taken for granted. $\endgroup$
    – vonbrand
    Mar 19, 2013 at 20:23

Your Answer

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

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