On My New Theory of Computation Series

The fall 2012 semester is approaching. It’s not as fast as those winter waves in Waimea Bay, but close enough. (Yes, the above photo I took is of the same beach — click for a larger view.)

Here are all the courses I’m taking:

  1. Applied Abstract Algebra
  2. Computer Graphics
  3. Probability
  4. Theory of Computation

All are lectures, with Computer Graphics being the only course that includes a lab component. Classes 1 and 3 satisfy my math major requirements, while 2 and 4 are for computer science. For the first semester ever, I won’t have at least one class that doesn’t fall outside of my two majors. So on the one hand, this means I’ll maximize my dedication in these classes, and will probably get high marks (famous last words).

But unfortunately, it means I won’t have as many options if I get a little burned out of computer science and math. I tend to spend long hours studying for exams and working on homework, so I’m going to try and do something that will hopefully alleviate some of the workload. This is purely an experiment, and one that I plan to continue if it brings solid results this semester.

The Plan

I’m going to make a series of blog posts on my Theory of Computation class (henceforth, CS 361). For reference, here’s the course description from the Williams Course Catalog that delineates the fun stuff coming up for me:

This course introduces a formal framework for investigating both the computability and complexity of problems. We study several models of computation including finite automata, regular languages, context-free grammars, and Turing machines. These models provide a mathematical basis for the study of computability theory–the examination of what problems can be solved and what problems cannot be solved–and the study of complexity theory–the examination of how efficiently problems can be solved. Topics include the halting problem and the P versus NP problem.

After every few classes, I hope to record on Seita’s Place what I learned and any relevant information going above and beyond the classroom discussion. By the time I take the midterm and final, I’ll have a nice repository of information online to help do quick review. I will strive to start these entries as soon as possible in draft form, and will add information to them a few hours after each CS 361 class.

There will be a consistent format for each of the posts. Each entry will be titled “CS Theory Part X: Y” where X is some natural number, and Y is a phrase that relates with the material I’ve learned and will cover in the blog entry. I want this to be like a personal Wikipedia that makes heavy use of rigorous proofs and outside sources.

The Benefits

So why do I want to do this? The most important benefit will be that it deepens my knowledge of theoretical computer science in a way that avoids long study hours and memorization session. Again, as I plan to update these entries soon after my classes end, I will minimize the amount of material I forget due to time. Furthermore, by writing these entries in my own words, I force myself to understand the material well, a prerequisite for explaining a subject in depth. (There’s a whole host of information online that backs up the previous claim.) Since I don’t want to write a book on theory, I have to pick the right spots to focus on, which requires me to be able to effectively judge the importance of all the concepts hurled at me in the class. Also, using the Internet over paper to express these posts makes it easier to link together concepts in a web, as explained by Scott Young’s holistic learning method.

But this begs the question: why this class, and not one of the other three?

My long-term goal is to pursue a Ph.D in computer science. As part of the process, I’ll be taking the computer science GRE and Ph.D qualifying exams. As you may expect by the course description, the material in CS 361 is most closely related with what’s going to be on the test than the material in the other three classes. Taken from the Educational Testing Service Website, we see that 40 percent of the material is theory!

III. THEORY AND MATHEMATICAL BACKGROUND — 40%

A. Algorithms and complexity

Exact and asymptotic analysis of specific algorithms
Algorithmic design techniques (e.g., greedy, dynamic programming, divide and conquer)
Upper and lower bounds on the complexity of specific problems
Computational complexity, including NP-completeness

B. Automata and language theory

Models of computation (finite automata, Turing machines)
Formal languages and grammars (regular and context-free)
Decidability

C. Discrete structures

Mathematical logic
Elementary combinatorics and graph theory
Discrete probability, recurrence relations and number theory

I suspect the amount of theory material on Ph.D qualifying exams is similar. These vary among institutions, so there’s no standard.

Computer graphics, while no doubt an interesting subject, isn’t as important in terms of the subject test material.

IV. OTHER TOPICS — 5%

Example areas include numerical analysis, artificial intelligence, computer graphics, cryptography, security and social issues.

It would also be more difficult for me to post graphics-related concepts online, as I’m certain that would involve an excessive number of figures and photos. I do have a limit on how many images I can upload here, and I’m not really keen on doing a whole lot of copying from my graphics class’ webpage; I prefer to have the images here be created by myself.

I also chose CS 361 over my two math classes. If I’m planning to pursue doctoral studies in computer science, it makes sense to focus on CS 361 more than the math classes. I was seriously considering doing some Probability review here, but the possibly vast number of diagrams and figures I’d have to include (as in graphics) is a deterrent.

Finally, another benefit of writing the series will be to increase my attention to Seita’s Place. I hope to boost my writing churn rate and my research into deafness and deaf culture. Even though it’s relatively minor, this blog has become more important to me over the past year, and I want to make sure it flourishes.

I’ll keep you posted.

About these ads

About Daniel Seita

A student.
This entry was posted in Computer Science and tagged , , , , , . Bookmark the permalink.

3 Responses to On My New Theory of Computation Series

  1. Yongyi Chen says:

    Cool! Remember the theoretical computer science presentation from the summer academy? Perhaps you can revisit it after you learn about “theory of computation” :D

  2. Pingback: CS Theory Part 1: Finite Automata « Seita's Place

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s