Still, it's a worthwhile class to take even if using n tracks on the Turing machine felt a little bit like cheating. And the 3-SAT concept is useful to know in general too, and whilst I was struggling with some of the topics, it did give me a good workout. Well, if it would be easy, it would not be so useful, no? ;-) I definitely would not claim I understand the topic, but I gained an appreciation, and learned where to look in case I ever need it. And I plan to retake the course if it runs again.
I did buy the Introduction to Automata Theory, Languages and Computation for ~£5 second hand, but it's a lot to read and going through it will take some time (a paragraph a day will eventually get it read, it's the Turing Machine method of studying -- it may or may not complete)
As a bonus, Mr. Ullman used a free version of his Foundations of Computer Science book, which is a very nice scenic tour of general CS concepts and a great way of refreshing long forgotten topics and picking up a few new ones.