What do you call your ugrad non-algorithms theory course?

I am in the process of reviewing

                     What can be computed: A Practical Guide to the Theory of Computation
                     by John MacCormick


and I need YOUR help for the first SENTENCE.  I began by saying


                    This is a text book for a course on Formal Language Theory

but then I realized that this is not what we call the course at UMCP. Then I got to thinking: what do other schools call it? I have the following so far:

UMCP: Elementary Theory of Computation

Harvard: Introduction to Theory of Computation

MIT: Automata, Computability, and, Complexity

Clark: Automata Theory

(My spellcheck does not think Automata is a word. Also Computability. Usually I listen to my spellcheckers, but I checked and YES, I spelled them right.)

For some other schools I either hit a place I needed an account, or I just got titles without a description so I could not be sure.

This is where YOU come in!

Please leave comments with your school and the title of the course at your school that covers a reasonable overlap with: Regular Sets, Context Free Sets, Decidable and Undecidble and r.e. sets, P, NP, perhaps other complexity classes, and NP-completeness. Its FINE if your answer is one of the above ones, or one of the other comments--- I plan to later set this up as a pigeonhole principle problem.

I suspect that courses in algorithms are called Algorithms or Introduction to Algorithms.

I suspect that courses in cryptography are called Cryptography  or Intro to Cryptography.


Why does the non-algorithm, non-crypto theory course have more names?

Julia Robinson's 100th birthday

On Dec 8, 1919 Julia Robinson was born, so today is close to her 100th birthday (she passed away at

the age of 65 on July 30, 1985).

So time for some facts about her

1) She got her PhD from Tarski where she proved the undecidability of the theory of the rationals.

2) She is probably best known for her work on Hilbert's tenth problem (which we call H10)

In todays' terminology H10 would be stated as:

Find an algorithm that will, given p in Z[x_1,...,x_n] determine if it has an integer solution.

Hilbert posed it to inspire deep research in Number Theory. There are some cases that are

solvable (the topic of a later blog post) but the general problem is undecidable. This is not what Hilbert was aiming for. I wonder if he would be happy with the resolution.

The Davis-Putnam-Robinson paper showed that the decision problem for exponential diophantine equations was undecidable. It was published in 1961. The paper is here.  Martin Davis predicted that the proof that H10 was undecidable would be by a young Russian mathematician. He was proven correct when Yuri Matiyasevich supplied the missing piece needed to complete the proof.  

I often read `H10 was resolved by Davis-Putnam-Robinson and Matiyasevich' or sometimes they put all four names in alphabetical order. I like that--- it really was a joint effort.

3) She was inducted (a proof by induction?) into the National Academy of Sciences in 1975.

4) She was elected to be president of the American Math Society in 1982.  

5) She got a MacAuthor Fellowship prize in 1985 (Often called the MacAuthor Genius award.)

At the time it was worth $60,000.  Its now $625,000.

6) She also did work in Game Theory. Her paper An Iterative Method of Solving a Game, which is
here, is a proof from the book according to Paul Goldberg's comment on this post.

7) The Julia Robinson Math Festival is named in her honor (hmmm- is that a tautology?) Its purpose is to inspire K-12 students to get involved in math. For more on it see here.

8) (ADDED LATER) Commenter David Williamson pointed out that Julia Robinson did work on the transportation problem. See his comment and his pointer to the paper.

(ADDED LATER) When I hear Julia Robinson I think Hilbert's 10th problem.  I suspect many of you do the same. However, looking at items 6 and 8 above, one realizes that she did research in non-logic branches of math as well.

Fields used to be closer together than they are now. Good? Bad?

There was a retired software Eng professor that I had heard two very non-controversial rumors about:

1) He got his PhD in Numerical Analysis

2) He got his PhD in Compiler Optimization.

So I asked him which was true.

The answer: Both! In those days you had to optimize your code to get your NA code to run fast enough.

We cannot imagine that anymore. Or at least I cannot.

Over time the fields of computer science advance more so its hard to be  master of more than one field.  But its not that simple: there has been work recently applying Machine Learning to... well
everything really. Even so, I think the trend is more towards separation. Or perhaps it oscillates.

I am NOT going to be the grumpy old man (Google once thought I was 70, see here) who says things were better in my day when the fields were closer together. But I will ask the question:

1) Are people more specialized new? While I think yes since each field has gotten more complicated and harder to master. There are exceptions: Complexity theory uses much more sophisticated mathematics then when I was a grad student (1980-1985), and of course Quantum Computing has lead to more comp sci majors knowing physics.

2) Is it good for the field that people are specialized? I am supposed to say that it is terrible and that great advances are made when people are interdiscplinary. But there are many more small advances that are made by someone who has a mastery of one (or two) fields.

3) The PhD Process and the Tenure Process encourage specialization. This I think IS bad since there are different modes of research that should all be respected.'

A non-moral dilemma about cheating, but it brings up some points

I often give two versions of an exam and TELL THE STUDENTS I am doing this so that they don't even try to cheat. I've even had two different classes take the midterm at the same time, same room, every other seat, so the person next to you is in a different course. And I TELL THE STUDENTS that I am doing this.  A colleague of mine says I shouldn't TELL THE STUDENTS. Here are our arguments

1) Don't tell: students cheat a lot and this is a way to catch them.

2) Tell:  Dealing with cheating distracts from our mission of teaching so best to be preventative so it does not happen. Less noble- tell them so that you don't have to deal with the cheating issue.

I have heard of the following case at a diff school some years ago and want your take on it:
there was one question on the midterm that was different on the two exams- the prof changed the key number, but they were the same question really. The prof was in a hurry for some reason and FORGOT TO TELL THE STUDENTS. You can probably guess what happened next, but not what happened after that

One of the students exams had the solution to THE OTHER PROBLEM on it. Clearly cheating. When called in the student said:

Since you didn't tell us that they were different exams the cheating claim is unfair!

They DID admit their guilt, but they DID NOT have any contrition.

 Options for what penalty to go for:

1) A 0 on the exam itself

2) An F in the course

3) A notation on the transcript indicating Failed-because-cheated. I don't know what that notation was at the schol the story took place, but at UMCP its XF. (Side Note- not clear if someone outside of UMCP looks at a transcript and sees an XF they'll know what the means. But the F part makes it look bad.)

4) Expulsion from school. (This might not be the profs call- this may depend on if its a first offense.)

The lack of contrition bothers me, though the prof who told me the story said that the student may have said it out of shock- the first thing that came into their mind. I asked the prof how the student was doing in the class and the prof said, CORRECTLY, that that is irrelevant.

SO- what penalty would you go for?

The professor went for XF. The student, at the hearing, once again said


Since you didn't tell us that they were different exams the cheating claim is unfair!

The professor told me that he thinks the student was trying to claim it was entrapment, though he had a hard time expressing this coherently. If the student had been a coherent thinker, he probably wouldn't have needed to cheat.

He got the equivalent of an XF.

But here is my real question: Should we TELL THE STUDENTS that they are different exams (I think yes) or
should we NOT tell them so can catch them?

Limits of using the web for info- self-reference

(I wrote this a while back so when I say `I Googled BLAH' I meant back then. It is prob different now.)

While the web is a wonderful to find things out there are times when it doesn't quite work.

1. An old blog of Scott Aaronson's had as part of its title a Woitian Link. Wanting to find out what a Woitian Link is but not wanting to bother Scott (he's busy enough making comments on Shtetl-Optimized) I went to google and typed in "Woitian Link". The ONLY hits I got back were to Scotts blog. I finally had to email Scott. He told me that it was referring to the blog not even wrong by Peter Woit which often has links that... Well, Scott never told me quite what it was but I'll go there myself and try to figure it out.
   
2. An old blog of mine was the man who loved algorithms. Part of my blog said that I thought the man would be Knuth but it was not. (It was Thomas Kailath) One of the commenters said that it couldn't be Knuth since he was still alive. This made me want to check the original article to see if Thomas Kailath, is also still alive (he is). I didn't have the issue with me at the time so I typed "the man who loved algorithms" into google. The first page of hits all refered to my posting. Eventually I found one to verify that yes, indeed, he was still alive.
   
3. Donald Knuth VOLUME FOUR was originally published in a series of fascicile's. Whats a fascicle? Here the web was helpful- Wikipedia said it was a book that comes out in short pieces, the pieces of which are called `fascicle'. They gave only one example: Donald Knuth's Volume 4 will be coming out in Fascicle. Still, they DID tell me what I want to know. (Note- this was a while back, they have since removed that comment.) For most things the web is great. But for some more obscure things, better off asking someone who knows stuff.

Do you have experiences where you ask the web for a question and you end up in a circle?

Statistics to Scare

So how do you parse the following paragraph from Monday's NYT Evening Breifing.

A study in JAMA Pediatrics this year found that the average Halloween resulted in four additional pedestrian deaths compared with other nights. For 4- to 8-year-olds, the rate was 10 times as high.

The paragraph  means the percent increase for pedestrian deaths for 4-8 year olds was ten time the percent increase for people as a whole, a number you cannot determine from the information given. Using the fact that roughly 7% of Americans are in the 4-8 year range, that yields a little under three additional deaths for 4-8 year olds and about one for the other age ranges.

The paper unfortunately sits behind a firewall. But I found a press release.

Children in the United States celebrate Halloween by going door-to-door collecting candy. New research suggests the popular October 31 holiday is associated with increased pedestrian traffic fatalities, especially among children. Researchers used data from the National Highway Traffic Safety Administration to compare the number of pedestrian fatalities from 1975 to 2016 that happened on October 31 each year between 5 p.m. and 11:59 p.m. with those that happened during the same hours on a day one week earlier (on October 24) and a day one week later (on November 7). During the 42-year study period, 608 pedestrian fatalities happened on the 42 Halloween evenings, whereas 851 pedestrian fatalities happened on the 84 other evenings used for comparison. The relative risk (an expression of probability) of a pedestrian fatality was higher on Halloween than those other nights. Absolute mortality rates averaged 2.07 and 1.45 pedestrian fatalities per hour on Halloween nights and the other evenings, respectively, which is equivalent to the average Halloween resulting in four additional pedestrian deaths each year. The biggest risk was among children ages 4 to 8. Absolute risk of pedestrian fatality per 100 million Americans was small and declined from 4.9 to 2.5 between the first and final decades of the study interval. 

Doing the math, we see a 43% increase and a more than quintupling the number of pedestrian deaths for the youngsters. That sounds scary indeed. though it only adds up to a handful of deaths.  Moreover the authors didn't take into account the larger number of pedestrians on Halloween, particularly among 4-8 year olds.

A smaller fraction of people die as pedestrians on Halloween today then on a random day when I was a kid. I wonder if that's because there are fewer pedestrians today.

Also from the New York Times, a sociologist has found "no evidence that any child had been seriously injured, let alone killed, by strangers tampering with candy." I feel lied to as a kid.

So the upshot: Tell your kids to take the usual precautions but mostly let them dress up, have fun trick-or-treating and enjoy their candy.

Random non-partisan thoughts on the Prez Election

This post is non-partisan, but in the interest of full disclosure I disclose that I will almost surely be voting for the Democratic Nominee. And I say almost surely because very weird things could happen.I can imagine a republican saying, in 2015 I will almost surely be voting for the Republican Nominee and then later deciding to not vote for Trump.


My Past Predictions: Early on in 2007 I predicted it would be Obama vs McCain and that Obama would win. Was I smart or lucky? Early in 2011 I predicted Paul Ryan would be the Rep. Candidate. Early in 2015 and even into 2016 I predicted that Trump would not get the nomination. After he got the nomination I predicted he would not become president. So, in answer to my first question, I was lucky not smart. Having said all of this I predict that the Dem. candidate will be Warren. Note- this is an honest prediction, not one fueled by what I want to see happen. I predict Warren since she seems to be someone who can bridge the so-called establishment and the so-called left (I dislike the terms LEFT and RIGHT since issues and views change over time). Given my past record I would not take me too seriously. Also, since this prediction is not particularly unusual, if I am right this would NOT be impressive (My Obama prediction was impressive, and my Paul Ryan prediction would have been very impressive had I been right.)

Electability: My spell checker doesn't think its a word. Actually it shouldn't be a word. It's a stupid concept. Recall

JFK was unelectable since he was Catholic.

Ronald Reagan was unelectable because he was too conservative.

A draft dodging adulterer named Bill Clinton could not possible beat a sitting president who just won a popular war.

Nobody named Barack Hussein Obama, who is half-black, could possibly get the nomination, never mind the presidency. And Hillary had the nomination locked up in 2008--- she had no any serious challengers.

(An article in The New Republic in 2007 predicted a brokered convention for the Republicans where Fred Thompson, Mitt Romney, and Rudy Guilliani would split the vote, and at the same time a cake walk for Hillary Clinton with
Barak Obama winning Illinois in the primaries but not much else. Recall that 2008 was McCain vs Obama.)

Donald Trump will surely be stopped from getting the nomination because, in the end, The Party Decides.

Republican voters in 2016 will prefer Rubio to Trump since Marco is more electable AND more conservative. Hence, in the space of Rep. Candidates, Rubio dominates Trump. So, by simple game theory, Trump can't get the nomination. The more electable Rubio, in the 2016 primaries, won Minnesota, Wash DC, and Puerto Rico (Puerto Rico has a primary. Really!) One of my friends thought he also won Guam (Guam?) but I could not find evidence of that on the web. Okay, so why did Trump win? Because voters are not game theorists.

ANYWAY, my point is that how can anyone take the notion of electability seriously when unelectable people have gotten elected?

Primaries: Dem primary voters are torn between who they want to be president and who can beat Trump. Since its so hard to tell who can beat who, I would recommend voting for who you like and not say stupid things like

American would never elect a 76 year old socialist whose recently had a heart attack.

or

Trump beat a women in 2016 so we can't nominate a women

or

America is not ready to elect a gay president yet. (America is never ready to do X until after it does X and then the pundits ret-con their opinions.For example, of course America is ready for Gay-Marriage. Duh.)

Who won the debate?
Whoever didn't bother watching it :-). I think the question is stupid and has become who got out a clever sound bite. We need sound policy, not sound bites!

Differentiation and Integration

Recently there was an excellent xkcd about differentiation and integration, see here.

This brings up thoughts on diff and int:

1) For some students Integration is when math gets hard.

Diff (at least on the level of Calc I) is rote memorization. A computer program can EASILY do diff

Integration by humans requires more guesswork and thought, Computers can now do it very well but I think that it was  harder to get to work.

Someone who has worked on programs for both, please comment.

2) When I took Honors Calculus back in 1976 (from Jeff Cheeger at SUNY Stonybrook) he made a comment which really puzzled the class, and myself, but later I understood it:

             Integration is easier than Differentiation

The class thought this was very odd since the problem of, GIVEN a function, find its diff was easier than GIVEN a function, find its int.  And of course I am talking about the kinds of functions one is
given in Calc I and Calc II, so this is not meant to be a formal statement.

What he meant was that integration  has better mathematical properties than differentiation.  For example, differentiating the function f(x)=abs(x) (absolute value of x)  is problematic at 0, where it has no problem with integration anywhere (alas, if only our society was as relaxed about integration as f(x)=abs(x) is).

So I would say that the class and Dr. Cheeger were both right (someone else might say they were both wrong) we were just looking at different notions of easy and hard.

Are there other cases in math where `easy' and `hard' can mean very different things?