Responses

'Other' Responses
- Don;t know
- It has already been removed from some curricula, but is compulsory for others.
- Not presented every year but solidly part of course
- Not sure. I think some professors don't know why the course is there...
- Was under threat but now solid.

'Other' Responses
- Don't know
- Running as a core for only one year thus far.
- Management does not realise the importance of such courses and would rather phase them out because of their relatively low pass rates.
- It is elective in our Honours year.
- low pass rates
- Students always complain about the theoretical approach and the massive reading time, even when there is practical evaluation and at most 150 pages to read.
- sometimes teacher assigned to the course is not the best suitable. it brings some tension, but usually things run smoothly.
- Traditionally difficult content, but vitally important stuff, of course.
- No more problems than other courses like computer graphics, analysis of algorithms, discrete mathematics, compiler construction, and others where programming is not the only ability required.
- Students find it very difficult and do not see its importance for their professional career.
- The grades are lower than in other courses and there are about 40% students that do not have success. But in our university the student can go to the next semester and only the courses that depend on Theory cannot be attended until the student being approved.
- Low enrolment in Formal Languages course caused it to be offered every two years now.
- There is ongoing discussion on whether the topic should be kept in the computer engineering program.
- The reaction depends a lot on who is teaching the TOC. I suspect it also matters a lot how much they attempt to relate it to problems an average student might meet in a career.
- My personal opinion is that it should comprise of 2 semesters (1 for formal languages, 1 for computability theory), to avoid cramming up too much content into one semester.
- Well, there has been no serious problems lately. But, since this is a last year course, usually a few (3, 4) of the students that fail the course tend to complain or ask for a second chance.
- Many students think that the course is not useful for them, especially students attracted to Information Systems and Software Engineering.

'Other' Responses
- .
- Programming Data Structures course, Modern Operation Systems course
- Compilers
- Artificial Intelligence, Formal Logic
- Principles of Programming Languages
- KRR
- Compilers
- Systems Engineering/Analysis
- Logic
- biomedical informatics
- Formal Program Verification; Formal Specification Languages
- graph theory; analysis of algorithms
- algorithms and data structures
- Algorithms Design and Analysis and also Graphs: Theory and Applications
- Operatym Sistems
- Never taught.
- Logic
- never teach
- Algorithms

Responses
- Weighted automata and transducers, with applications, in a basic course. Tree automata in an extended course.
- Quantum Turing Machine
- Savitch Theorem - PSPACE-completeness
- Parallel complexity classes. PRAM NC P-complete etc

Responses
- no
- I believe this is one of the courses that shape the identity of Computer Science. Removing it from CS programmes will deprive CS graduates of an essential thinking tool. Isn't it the core of the science of computing? do we then want to cease to be a science? No lets keep it and find ways and means to teach it in a more digestible way.
- Some of these topics are spread out across different courses.
- My feeling is that it is much easier to motivate automata courses to cs students by including scanning an parsing aspects of compiler construction and also speech and language processing applications. A classical theory of computation course fits perhaps better in pure mathematics departments.
- I am currently a Computer Science PhD student at [Uni1]. I've developed a number of algorithms in the field of Bioinformatics. All of the developed algorithms rely on Computer Theory. Finite automata are used to detect for example so called tandem repeats in DNA. My knowledge of CFGs contributed to the development of an algorithm which will hopefully be able to simulate evolution. I've taught Computer Theory to second and third year students for several years. Unfortunately some of the honours module teaching computability and complexity have been eliminated from [Uni2] curriculum. This was a consequence of a more B.Com oriented person managing our School of Computing. You did not provide an option to select if a person has done some Computer Theory first year, second year, third year and on honours level. Such was my case.
- No more comments. I just want to congrats the initiative!
- There are a course combining Formal Grammars & Compiler Construction for Engeneering, besides the traditional Teory of Computation in Computer Science courses in my university. It runs very well and students loves to see an application of Formal Languages and implement a compiler for a simple language.
- I selected topics that should be in a Theory o Computation course, not in a Formal Languages or Computational Complexity Courses. In my University, these are different courses. Could you please send me the result of your research?
- I think that TOC must be taught troughout the undergraduation time. Since the first year, together with programming topics. But not as an isolated course in a semester. The more important issue about this kind of course is its applicability to other areas of computer science (or even science in general). It is impractical to cover all the topics with practice given the time slot. But is very productive to blend theory with practice. Unfortunately, in my university this is not done. We have 2 isolated courses (one at the 6th semester and another at the 7th semester of the undergrad).
- I work with Quantum Computation and Quantum Communications. Many of the concepts behind this new paradigm are understood more easily if a solid background on theory of computation have been previously acquired. Analysis of algorithms, comparisons, communication complexity and other topics are also examples of that. Even in graduation, I also solved problems of compilators in a very easy way using regular expression, for instance. I also perceived this lack of interest from the students in this course. Aiming at minimizing them in our university, together with the professor of ToC, we wrote a book about Finite Automata, from its most basic definition (DFA) to its Quantum version, specially dedicated to undergraduate students in Computer Science. We tried to show other points of view that were not shown in the already existing book. We receive requests from the whole country asking us what to do to buy the book. We considered this initiative successfull. We face this problem in other course as well. It was in Logic for Computer Science. We balanced the theoretical part with automated proof theorem, program verification, and other software engineering related topics. The feedback was quite positive. However, in a general manner, my feeling is that students are each time less capable to create abstractions and each more time interested in becoming programmers (and alikes). The existing appeal for technology, gadgets, inspire them to become Zuckemberg or the Google's guys. When they face the reality of a mostly theoretical course, they do not make efforts to get engaged as they should be. Sometimes they even understimate the difficult of the course. In my opinion, it is important to make a clear point regarding what technology can give us and the barriers that will eternally be faced if theoretical problems remain unsolved.
- Explaining the topics as important and fundamental concepts of other courses (e.g., applied areas such as bioinformatics) would be useful.
- I think this is the kind of topic that a student may never use in his career. At least not directly, i.e. he can completely ignore it and still be a very good professional. However, if he ever needs some of its concepts (for example, to design/maintain a compiler, or to determine the decidability of a given problem) he will have a really hard time trying to understand everything by himself. So, I think the topic should be maintained because the graduation may be the only opportunity to learn it properly.
- I completed part of the survey, but it keeps on crashing.... In short, we've been offering Formal Languages and Automata, combined with ToC, at [Uni3] Computer Science for many years. The FL part used to be offered in the 3rd year (core module) and the ToC (elective) at Honours level. A re‑arrangement of the curriculum now has FL offered in the Honours as well. The pass rate for these courses is on par with our other courses. Students are generally interested in taking the courses. I have to point out that we have a strong FL research group at Stb, and the idea of formal models is introduced to students from their first year onwards. Moreover, we have many practical applications which we actively integrate into the course (natural language processing, machine translation, cellular automata applications, music generation, and more). So the students don't see the course in isolation, and neither would they feel that the course is not of practical use. I'm happy to answer more specific questions.
- Your survey assumes a single course on this topic. At our university there are 3 relevant courses: a) a REQUIRED second year, undergrad course on Discrete Math for CS. People cover some of the following: regular expressions, FAs, P/NP,... in addition to the basics: logic, functions/relations. b) a REQUIRED course on Algorithms and Complexity, in third year, which includes P,NP, lower bounds for sorting/search, as well as graph algorithms. c) an OPTIONAL fourth course on formal language & automata, which is highly mathematical (and is taken by math majors as much as a few of our undergrads). This is the one I was describing in the survey. Note that failure rates have not been an issue. But enrolment has been one (below 10 the course should be canceled).
- Some of the answers are just "closest possible" - as the TOC content is spread over multiple modules. A compulsory 2nd year one that does regular, context free, etc. An elective 3rd year one that does comutatbility and complexity (Halting theorem, P, NP-hard, PSPACE, etc). Of course, please note these are personal and sometimes merely "first-impression" choices. I don't represent the University, and might answer differently if had a lot more time.
- None
- In my own studies, I had theory of computation not only in one year, but in the first, second, and third year. At the university I am working, obligatory theory courses are taught in the first and the second year.
- We actually have two core courses in Theory of Computation, the first covers Automata related stuff, and the second models of computation and undecidability