What can a math major do to get into a computer science PhD program? I graduated this past May from UC Berkeley with a degree in applied math. I realized that I am very interested in getting a PhD in computer science. However, my programming experience is mostly self taught and I have only one introductory class in Python on my resume as programming experience. Right now, I'm working at a startup building risk models using machine learning. I do some coding at work, but not a lot. My primary interest is in AI (especially it's applications in video games) and my top schools are Stanford, Berkeley, USC, and Caltech.

I'm willing to spend the next few years building up a resume so that I can get into grad school, but the problem is that I don't know what to do. I can talk to my employers and see if I can get more work that involves programming. I could also work with them to publish our findings in academic papers. I can work on some projects on my own, such as building apps or something. Or I could take extension classes in CS. What would be the best course of action? Should I go for a masters instead? Does anyone who got into a PhD program without studying the subject in college have any stories to share? (Note: I have not yet taken the GRE).

As a bonus question, if you think another school besides the four I listed would be really great for AI, which one and why? And as an extra bonus question, does anyone know if it's harder to get into Berkeley as a grad student if you already went there for undergrad?
"Programming" is only one part of computer science, and arguably, the "easiest" part. The harder parts of computer science are the theoretical parts (e.g. math and machine learning), in which your background is strong.

To address your greatest concern, programming, my own experience is something like this: The easiest part of program is creating commands for things like "formatting." That is more tedious, than anything else. Certainly, Python or other programming experience is helpful in this regard, but is nothing that someone of your intellectual caliber should worry about.

A harder part of computer science is "logic," at least as expressed in flow charts. These include things like true-false "branching," or jump commands such as "goto," or loops and links. This part of computer science is harder than the formatting part, but not overly difficult.

The hardest part (for me at least) is mathematical concepts and equations. Once you've got the equations down, and can express them in "computer" form (using e.g., recursion), you are over the most difficult part. Related to this is machine learning, how the machine bootstraps itself through feedback loops.

So, relax. You have a good background in the hardest part of computer science. Naturally, you want to learn some of the "soft" stuff, e.g. programming, but until you get to the actual courses, what you don't know won't hurt you.

Besides the four California schools that you mentioned, I would consider Carnegie Mellon University in Pittsburgh, Pennsylvania. My father (Dr. Tung Au) retired from there as a professor 24 years ago, (and has a laboratory named after him). That school is known for robotics, artificial intelligence, and computer science. Another school you might consider is his alma mater, Illinois Institute of Technology.