meta data for this page
  •  

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision		Previous revision
public:dugc:cs208-toc [2015/07/08 15:34] – created anupreetpublic:dugc:cs208-toc [2020/06/05 02:36] (current) – external edit 127.0.0.1
Line 3: Line 3:
 There are three parts in this proposal.  There are three parts in this proposal. 
  
-a) Syllabus for a new core course titled 'Logic for Program Correctness'+a) Syllabus for a new core course titled 'Logic for Program Correctness'\\
 b) Deletion of some of the related topics from the course CS 208 -   b) Deletion of some of the related topics from the course CS 208 -  
 'Automata Theory and Logic' and renaming that course 'Theory of   'Automata Theory and Logic' and renaming that course 'Theory of  
-Computation'+Computation'\\
 c) Dropping 2 other courses titled "Theory of Computation" - CS 319 and CS   c) Dropping 2 other courses titled "Theory of Computation" - CS 319 and CS  
 331. 331.
  
---------------------------------------------------------+----
  
 As suggested by DUGC, Supratik, Bharat and Om came together to decide the As suggested by DUGC, Supratik, Bharat and Om came together to decide the
Line 26: Line 26:
  
 I  Title of the Course  Logic for Computer Science I  Title of the Course  Logic for Computer Science
-i   Credit Structure     L   T   P  C +i   Credit Structure\\ 
-                         3   0   0  6+ L   T   P  C\\ 
 + 3   0   0  6\\
 ii  Prerequisite, if any - None ii  Prerequisite, if any - None
-Syllabus: 
  
 +Syllabus:
 +<html><pre>
 1 Propositional logic: 1 Propositional logic:
         1.1 Declarative sentences         1.1 Declarative sentences
Line 74: Line 76:
         3.3 Proof calculus for total correctness         3.3 Proof calculus for total correctness
         3.4 Programming by contract         3.4 Programming by contract
 +</pre></html>
  
 Time permitting, other possible applications and tools can be covered. Time permitting, other possible applications and tools can be covered.
Line 80: Line 83:
 Press, 2004. Press, 2004.
  
----------------+---- 
 Once this course is introduced, CS 208 - Automata Theory and Logic can be Once this course is introduced, CS 208 - Automata Theory and Logic can be
 renamed "Theory of Computation" and the following can be dropped from CS renamed "Theory of Computation" and the following can be dropped from CS
Line 92: Line 96:
 material is anyway not being covered in CS 208 due to lack of time. material is anyway not being covered in CS 208 due to lack of time.
  
-The syllabus for revised CS 208 - Thoery of Computation will be:+The syllabus for revised CS 208 - Theory of Computation will be:
  
 Current curriculum:    Current curriculum:   
  
-      I  Title of the Course  Theory of Computation +I  Title of the Course  Theory of Computation\\ 
-i   Credit Structure     L                T + i   Credit Structure\\ 
-P                C + L  T  P  C\\ 
-                             3                0 + 3  0  0  6\\ 
-0                6 + ii  Prerequisite, if any Discrete Structures (CS 207)(for the student) 
-ii  Prerequisite, if any Discrete Structures (CS 207) + 
-        (for the student) +v   Course content\\ 
-v   Course content       Rudiments of formal languages. Finite state +Rudiments of formal languages. Finite state machines(DFA/NFA/epsilon NFAs), regular expressions. Properties of regular languages. My hill-Nerode Theorem. Non-regularity. Push down automata. Properties of context-free languages. Turing machines:Turing hypothesis, Turing computability, Nondeterministic, multi tape and other versions of Turing machines. Church's thesis, recursively enumerable sets and Turing computability. Universal Turing machines. Unsolvability, The halting problem, partial solvability, Turing 
-machines +enumerability, acceptability and decidability, unsolvable problems about Turing Machines. Post`s correspondence problem. 
-                             (DFA/NFA/epsilon NFAs), regular expressions. + 
-Properties of +Texts/References:\\ 
-                             regular languages. My hill-Nerode Theorem. +1. Introduction to Automata Theory, Languages and Computation,\\ 
-Non-regularity. +by John. E. Hopcroft, Rajeev Motwani, J. D. Ullman,\\ 
-                             Push down automata. Properties of context-free +published by Pearson Education Asia, 2006.\\ 
-languages. Turing +2. Elements of the Theory of Computation, by H.R. Lewis and C.H.Papadimitrou,\\ 
-                             machines:Turing hypothesis, Turing +published by Prentice Hall Inc, 1981. 
-computability, + 
-                             Nondeterministic, multi tape and other versions +----
-of Turing +
-                             machines. Church's thesis, recursively +
-enumerable +
-sets and +
-                             Turing computability. Universal Turing +
-machines. +
-Unsolvability, +
-                             The halting problem, partial solvability, +
-Turing +
-enumerability, +
-                             acceptability and decidability, unsolvable +
-problems about Turing +
-                             Machines. Post`s correspondence problem. +
-        Texts/References +
-                             1. Introduction to Automata Theory, Languages +
-and +
-Computation, +
-                                by John. E. Hopcroft, Rajeev Motwani, J. D. +
-Ullman, published +
-                                by Pearson Education Asia, 2006. +
-                             2. Elements of the Theory of Computation, by +
-H.R. +
-Lewis and +
-                                C.H.Papadimitrou, pu  blished by Prentice +
-Hall +
-Inc, 1981. +
-------------------------------------------------------+
  
 Note that there are 2 other courses titled "Theory of Computation" - CS Note that there are 2 other courses titled "Theory of Computation" - CS
-319 and CS 331, which should be dropped. +319 and CS 331, which should be dropped.