This course covers several fundamental topics in computer science: automata theory, formal languages, computability theory, and complexity theory. The automata theory deals with simplified models of computation that have finite states. These models, together with formal languages, have direct practical applications in areas such as search engines, language processing, and bioinformatics. Computability theory deals with the question of whether or not a problem is solvable on the computer. The famous halting problem is an example problem that is easy to formulate but impossible to solve. The complexity theory classifies problem into easy and hard problems. Many problems, such as general satisfibility (SAT) problems, belong to the NP-complete class which is considered hard to solve.
There is one homework assignment every two weeks. You are required to submit your homework in paper in a stapled unit. All homework in paper will be checked and returned. You can also submit your homework by email, but email submissions will not be returned.