CSE 262: Automata., Computability, and Complexity/title> </head> <body bgcolor=#ffffff> <h2><FONT COLOR=red> CSE 262: Automata., Computability, and Complexity<br> Fall 2008, University of Pennsylvania</font></h2> <hr> <H3><font color=green>Introduction</font></H3> This course offers an introduction to the <i>science </i> behind computing by stuying computation abstractly without worrying about specifics of programming languages and/or computing platforms. In particular, we will study (a) finite automata that capture what can be computed using constant memory, and give the class of regular languages useful for pattern matching languages; (b) context-free grammars that faciliate declarative specifications of language syntax, and the associated operational model of pushdown automata; (c) the universal computational model of <a href="http://en.wikipedia.org/wiki/Alan_Turing"> Turing</a> machines, and the inherent limits of what can be solved on a computer (undecidability), and (d) the notion of computational tractability (which problems can be solved in polynomial-time), and <a href="http://www.claymath.org/millennium/P_vs_NP/">the million-dollar P vs NP question.</a> The course also emphasizes rigorous thinking and mathematical proofs. <hr> <h3><font color=green>Logistics</font></h3> <ul> <li>Class: Tues Thurs 12--1.30, Berger Auditorium, Skirkanich Hall <li>Instructor: <a href="http://www.cis.upenn.edu/~alur/">Rajeev Alur</a> (<a href="mailto:alur@cis.upenn.edu">alur@cis</a>), Office hour: Wed 4-5 (Levine 609) <li>Teaching Assistant: <a href="mailto:selama@seas.upenn.edu"> Sela Mador-Haim</a>, <a href="mailto:sudeepa@seas.upenn.edu">Sudeepa Roy </a> <li>Recitation: Monday 4-5 (DRLB A8) <li>Pre-requisites: CSE 260 </ul> <hr> <H3><font color=green>Textbooks</font></H3> <ul> <li>Required: Introduction to Automata Theory, Languages and Computation, J.E. Hopcroft, R. Motwani, and J.D. Ullman, Addison Wesley, Third edition, 2006. <li> Additional Reference: Introduction to the theory of computation, Michael Sipser, Thomson Course Technology, Second Edition, 2004. </ul> Occasionally, we will cover some topics not discussed in the text, or present a topic in a manner significantly different compared to the text. In such acases, course notes will be distributed in class and posted on this page. <hr> <h3><font color=green>Grading</font></h3> Grades will be based on <ul> <li>Homework Assignments (7) 35% <li> Midterms (2) 30 % <li> Final Exam 35% </ul> <hr> <h3><font color=green>Schedule</font></h3> <ul> <li>Sept 4,9,11,16,18,23,25,30: Finite automata and regular languages <li>Oct 2: Midterm 1 <li>Oct 7,9,16,21,23,28: Pushdown automata and context-free grammars <li>Oct 30: Midterm 2 <li>Nov 4,6,11,13,18,20: Turing machines, computability, and Undecidability <li>Nov 25, Dec 2,4: NP-completeness and complexity theory </ul> <hr> <h3><font color=green>Lecture/Recitation Topics</font></h3> <ul> <li>Sept 4: Course logistics, Discussion of course content, Introduction to automata using examples. You may want to read beginning pages of Chapter 1 as well as Chapter 2 (And perhaps also section 2.4) <li>Sept 8 Recitation topic: Mathematical proofs (Sections 1.2, 1.3, 1.4) <li> Sept 9: Deterministic Finite Automata (Sections 1.5 and 2.2) </ul> <hr> <h3><font color=green>Notes</font></h3> <ul> <li> Recitation: During Monday's recitation, we will mainly focus on solving problems. Many students find the homeworks difficult, and even when they have solved the problem, some find it difficult to write the answer concisely and rigorously. Recitation should help with these challenges. However, attendance for recitation is optional as no new material will be covered. <li>Homework Drop-off and Pick-up: On the day the homework is due, it can be submitted during the lecture, or can be given to Merissa Mele (Levine 311) by 5pm. Graded homeworks and exams will be available with Merissa. <li>Plagiarism Policy: For homeworks, you can use your class notes, the textbook, and the reference book, but not old solutions, friends, other books, or any other material from the web. For violations of this rule, you will be given zero credit for that assignment. Start working on homework problems early, and if you get stuck, contact one of us; we will be happy to help you progress. </ul> <hr> <a href="http://www.cis.upenn.edu/~alur/">Maintained by Rajeev Alur</a> </body> </html>