CS 5201 - QE on Theoretical CS. ********************************************** Following is a rough analysis of the different types of questions asked in CS 5201 in 2005-07. I. Design new solutions ----------------------------------------------------- These questions are most common in the Algorithms area. The algorithms question often contains at least one part exhibiting such a flavor. For example see Nov 2005, Nov 2006 - Algorithms - Part B, or Apr 2007 - Algorithms - Part C, D. Any "domain knowledge" required for these questions is integrated within the question. The TOC area can also contain some questions of this kind (construct an automata/grammar) for example see Apr 2007 TOC question (part C), or say TOC question in Nov 2005, or TOC question in April 2006 (part B). II. Analyze the cost of given solutions ------------------------------------------------------------------------ Such questions may manifest themselves in different ways. In its most common form, the question can involve complexity analysis of a given algorithm/pseudocode (see the Algorithms question in past year to locate such questions). It is also possible to have questions in the programming language area which require you to (implicitly) look into the resources consumed by different programming styles in solving a given problem. For example, the April 2007 question in Programming Languages has this flavor. III. Translation of one style of solution to another ---------------------------------------------------------------------- Not surprisingly, these kind of questions are most common in the Programming Languages area where you think about different programming paradigms. For example see part B (particularly B.3) of the Programming Language question in November 2006 where you have to deal with object-oriented vs functional style of programming. Or you could look at part B of the Prog. Lang question (April 2006) where iterative style of programming is translated to a programming style with extensive use of functions. A general understanding of the programming paradigms and constructs is usually sufficient to answer these questions. It is also possible to have similar style questions in other areas, for example, see part (C) of the Logic question in April 2007. In a rather broad sense, the Logic question in April 2006 could also be considered in this category --- since this question explores the connections between program fragments and their equivalent representation in first-order logic. IV. Formalize an informally stated solution --------------------------------------------------------------- Such questions may appear in any area, but they are probably most common in the Logic area (again this is not surprising). The Logic questions in Nov 2005, Nov 2006 and April 2007 are filled with such examples where you formalize informal statements in propositional or first-order logic. However, other areas may also have such questions. For example, a Programming Language question may informally describe a language feature and tell you to formalize the semantics of such a feature. The Prog. Lang. question in Nov 2005 (see part C) contains such an example. V. Formally reason about properties of various solutions ------------------------------------------------------------------------------------ Here you may be required to formally prove some properties about given solutions. Alternatively, a piece of reasoning may be given to you and you may need to check its correctness. Such questions may be common in the TOC and Logic areas e.g. see Logic question in Nov 2005 (part B), or TOC question in April 2006 (part A), or TOC question in April 2007 (parts A, B). Answering such questions require rigorous mathematical reasoning. VI. Ability to deal with modifications of well-known concepts/solutions ---------------------------------------------------------------------------------------------------------------- In this category, a well-known concept will be slightly morphed and you will have to answer questions about this modified entity. These kind of questions can pretty much arise in any area. The TOC question in April 2006 (part C), the Algorithms question in April 2006 (part E), the Programming Language question in Nov 2005 (part B) are suitable examples of questions in this category.