Models of Computations

CSCI 2400 - Spring 2005

Contents

 

 

Announcements

 

Welcome to Models of Computation!

 

Try to get help for the homeworks during office hours and not via email. For questions regarding the assignments email the TAs first. If they cannot answer your question, then they will forward it to the instructor.

 

 

General Course Information

Please note that per request of the Computer Science Department, all office hours (beyond those of the instructor) will be held at Science Center 1W01 (the Bray Room).

  • Prof: Petros Drineas, Lally Hall 317, ext. 8265, drinep at cs dot rpi dot edu, Hours: Wed 10:00 – 11:30.
  • TA: Asif Javed, javeda at rpi dot edu, Hours: TBA.
  • TA: Yushin Cho, choy at rpi dot edu, Hours: Mon 16:30 – 18:00, Thu 16:30 – 18:00.

 

Class hours: Mon, Thu 14:00 - 15:30, at DCC 324.

 

Course textbook: “Introduction to Languages and the Theory of Computation” by John Martin (3rd edition). The book is available at the RPI bookstore.

 

Grading: Homeworks 31%, First Midterm 23%, Second Midterm 23%, Third Midterm 23%. There will be 10 to 12 homeworks; the three midterms will be in class. Students whose course average is above 92% will get an A in this course, students whose course average is between 82% and 92% will get a B in this course, students whose course average is between 72% and 82% will get a C in this course, and students whose course average is between 62% and 72% will get a D in this course. The instructor might lower these bounds depending on the final curve of the grades in the course.

 

Description: The course will have 3 parts, each followed by a midterm testing your understanding of the material. The first part will cover regular languages, non-deterministic finite automata and the pumping lemma for regular languages. The second part will cover pushdown automata, context free languages and grammars, the pumping lemma for context free languages, and Turing machines. The last part will cover decidability and an introduction to complexity theory.

 

Lectures

First Part

Ø       Introduction & Languages (book chapters 1 & 2)

Ø       Mathematical Preliminaries (book chapters 1 & 2)

Ø       Regular Languages and Finite Automata (book chapters 3 & 4)

Ø       Nondeterministic Finite Automata (book chapters 3 & 4)

Ø       Properties of Regular Languages (book chapters 3 & 4)

Ø       Regular Expressions and Elementary Questions for Regular Languages (book chapters 3 & 4)

Ø       Pumping Lemma for Regular Languages (book chapter 5)

Ø       More Pumping Lemma Examples (book chapter 5)

Ø       Context-Free Languages and Context-Free Grammars (book chapter 6)

Ø       Simplifications of Context-Free Grammars & Normal Forms (book chapter 6)

Homeworks

 

Collaboration is not allowed. Homeworks should be solved and written by individuals alone. If anyone is caught cheating, then severe measures will be taken, depending on the gravity of the offense. Such measures include significant lowering of the final grade and reporting the event to the appropriate authorities in the campus.

 

 

No homework extensions will be granted under any circumstances, unless approved by the Dean of Students. Homeworks are generally due on Thursday, by 4pm (sharp), in a box outside the Instructor’s office at Lally 317.

 

 

You can check your grades online at WebCT.

 

Ø       Homework 1 (Due on January XXX, by 4pm at Lally 317) à NOT AVAILABLE YET

 

 

 

Exams

 

Exams are open book and open notes. Laptops are NOT allowed.

 

  • Midterm 1
  • Midterm 2
  • Midterm 3