CSCI 2400 Models of Computation
Spring 2004
|
Contents |
· Grading
· Projects
· Exams
· Quizes
· WebCT
Exam 3 sample test and practice solutions are posted.
final_pract. Solutions:
final_pract_sol.
Submission for Project 3 can be done using
Submission Page
Homework 12 is posted.
Project 3 is posted. - On Tuesday, there will be helper programs to help you finish project 3.
ReadMe and s6.l and s6.y are helper programs to help you finish the project.
Please check your homework, quiz and exam grades in webct - If there are questions, please contact moorthy asap.
Sample Exam 2 is posted below. Exam 2 is on March 29th Monday in class.
Home Work 9 is posted.
Submission for Project 2 can be done using
Submission Page
Two sample programs to help with project 2 are posted. They can be
compiled by /usr/ccs/bin/lex s4.l;
/usr/ccs/bin/yacc -d s4.y ;
gcc y.tab.c -ly -ll -o myparser
- s4.l - Lex Program
- s5.l - Lex Program
- To run yacc in CS machines use /usr/ccs/bin/yacc
Submission for Project 1 can be done using Submission Page
Febrary 18: There is a practice midterm exam posted below. Your graded homeworks are in a box outside my office (Lally 305). There is an example program to have you started in project 1 posted in the projects section.
Feb 17: Your home work and Quiz grades are posted in WebCT. Please check..
Project 2 is posted. Homework 7 is posted
Homework 8 is posted
Location & Time: DCC 318, Monday & Thursday 2:00-3:50pm
Book: "An Introduction to
Formal Languages and Automata", Peter Linz,Third Edition, ISBN:
0-7637-1422-4.
|
Instructor & TAs |
Name |
Email |
Phone |
Office |
Office Hours |
|
Instructor |
x6911 |
Lally 305 |
Wednesday 2:00-4:00pm |
||
|
TA 1 |
Jing Xi |
x8465 |
Bray room, Science Center |
Tuesday 4-6:00 pm and Thursday 7-9:00 pm |
|
|
TA 2 |
Yu-Shin Cho |
x6397 |
Bray room, |
Monday 4-6:00 pm |
Thanks to Prof. Costas Busch who has prepared these excellent slides.
|
Day |
Topic |
Chapter |
Slides |
Assignment Post |
Assignment Due |
|
Monday January 12 |
Introduction |
-- |
|
|
|
|
Thursday January 15 |
Mathematical Preliminaries & Languages |
1 |
|
|
|
|
Thursday |
Finite Automata |
2.1 |
Homework 1 |
|
|
|
Monday |
Nondeterministic Finite Automata |
2.2 - 2.3 |
Quiz 1 |
|
|
|
Thursday |
Properties of Regular Languages Regular Expressions |
4.1 3.1 - 3.2 |
Homework 2 |
Homework 1 |
|
|
Monday |
Regular Grammars |
3.3 |
Quiz 2 |
|
|
|
Thursday |
Elementary Questions for Reg. Lang. Pumping Lemma for Regular Languages |
4.2 4.3 |
Homework 3 |
Homework 2 |
|
|
Monday |
Pumping Lemma Examples |
4.3 |
Quiz 3 Project 1 |
|
|
|
Thursday |
Context-Free Languages |
5 |
Homework 4 |
Homework 3 |
|
|
Tuesday |
Simplifications of Context-Free Grammars & Normal Forms |
6 |
Quiz 4 |
|
|
|
Thursday Febrary 19 |
Pushdown Automata |
7.1 |
Homework 5 |
Homework 4 |
|
|
Monday |
Exam 1 (Regular Languages) |
|
|
|
|
|
Thursday February 26 |
Pushdown Automata and Context-Free Lang. |
7.2 |
Homework 6 |
Homework 5 |
|
|
Monday March 1 |
Deterministic Pushdown Automata Yacc |
7.3 |
Quiz 5 Project2 |
Project 1 |
|
|
Thursday March 4 |
Pumping Lemma for Context-Free Languages |
8.1 |
Homework 7 |
Homework 6 |
|
|
Monday March 15 |
Pumping Lemma Examples |
8.1 |
Quiz 6 |
|
|
|
Thursday March 18 |
Turing Machines |
9.1-9.2 |
Homework 8 |
Homework 7 |
|
|
Monday |
Turing Thesis Variations of Turing Machines |
9.1 10.1-10.3 |
Quiz 7 |
|
|
|
Thursday |
Universal Turing Machines |
10.4 - 10.5 |
Homework 9 |
Homework 8 |
|
|
Monday |
Exam 2 (Context-Free Languages) |
|
|
|
|
|
Thursday |
Recursive and Recursively Enumerable Languages |
11.1 |
Homework 10 Project 3 |
Homework 9 |
|
|
Monday |
Chomsky's Hierarchy |
11.2-11.4 |
Quiz 8 |
Project 2 |
|
|
Thursday |
Decidability |
12.1-12.2 |
Homework 11 |
|
|
|
Monday April 12 |
The Post-Correspondence Problem |
12.3 - 12.4 |
Quiz 9 |
|
|
|
Thursday April 15 |
Time Complexity |
14 |
Homework 12 |
|
|
|
Monday April 19 |
NP-completeness |
14 (continuted) |
|
|
|
|
Thursday
|
Review Class |
|
|
Quiz 10 |
Homework 12 Project 3 |
|
Thursday Monday April 26 |
Exam 3 (Turing Machines) |
|
|
|
|
Collaboration is not allowed. Any collaboration will be
considered cheating. The only allowed collaboration is for the projects between
the same team members. If anyone is cought cheating then appropriate severe
measures will be taken.
Questions Regarding Assignments and Grading
For any questions regarding homeworks, projects, exams, and quizes, you should post a message on the discussion tool of webCT, and then a TA will answer. Actually, any student in the class can answer questions of the webCT, as long as no homework or project solutions are revealed. Don't send direct emails to the TAs or instructor, unless you have personal reasons to do so. You can meet with the instructor or the TAs during office hours, which are posted above. For homework or quiz questions you should talk to the appropriate TA who is handling the rerspective homework.
Grading of Assignments
- Homeworks (40%)
There will be a homework each week. Each homework will consist from two
questions. All homeworks should be returned at the
beginning of the class on the due date. No late homeworks are accepted.
- Computer Proje~cts (15%)
There will be 3 computer projects. First project counts 5% of your grade. You
will have almost a month for each project. For the projects you can work with
teams of up to 2 people, and this is the only allowed collaboration in the
class. No late projects are accepted.
- Exams (45 %)
There will be three exams. Each counts for 15% of your grade. The exams will be
given in class and will be open book.
- Quizes (Extra Credit: 5%)
There will be 10 in class quizes. Each quiz is 10 minutes long and counts for
0.5 extra credit point (out of 100). Quizes are open book. Quizes help to compensate
for bad grades and are good practice for the exams.
Homeworks should be handed-in in the class, at the end of the class on the due
day.
For questions about homeworks contact the appropriate TA. Solutions can be found on webct.
|
Homework |
Grader |
|
Jing Xi (TA 1) |
|
|
Yu-Shin Cho |
|
|
Jing Xi |
|
|
Yu-shin Cho |
|
|
Jing Xi |
|
|
Yu-Shin Cho |
|
|
Jing Xi |
|
|
Yu-Shin Cho |
|
|
Jing Xi |
|
|
Yu-Shin Cho |
|
|
Jing Xi |
|
|
Yu-Shin Cho |
Project
1 - Lex
- Due
day: Monday, March 1 (at midnight)- submission one per group.
- Assignment handout: project1.pdf.
- Test files: test1, test2, test3, test4, test5.
- Lex manual: lex.pdf, lex.ps.
- Here are the lex programs presented in class: example1.l, example2.l.
- Here is an example program for the first project. Project 1 Help
- A
simple unix script file for compiling your lex programs: lex-script.
Run "lex-script filename", where filename.l is your lex program and filename will be the resulting executable.
(Remember to change the permission of the script file to executable before you use it.) - Submission for Project 1 can be done using Submission Page
Project 2 – Yacc
Interpreter
Two sample programs to help with project 2 are posted. They can be
compiled by /usr/ccs/bin/lex s4.l;
/usr/ccs/bin/yacc -d s4.y ;
gcc y.tab.c -ly -ll -o myparser
- s4.l - Lex Program
- s5.l - Lex Program
- To run yacc in CS machines use /usr/ccs/bin/yacc
- Due
day: Monday, April 5th midnight.
You should submit your lex and yacc programs using the usual submission procedure.. - Assignment handout: project2.pdf,
- Test files: test1, test2, test3, test4, test5.
- Yacc manual: yacc.pdf, yacc.ps.
- Here
are the yacc (and their associated lex) example programs presented in
class:
expr1.l, expr1.y parser for programs that print the result of one expression
expr2.l, expr2.y parser for programs that print the result of consecutive expressions, seperated with ';'
expr3.l, expr3.y parser for programs that implement the print statement for expressions and strings
the ".l" are lex files and the ".y" are the respective yacc files. - A simple unix script
file for compiling your yacc programs: yacc-script.
Run "yacc-script filename", where filename.l and filename.y is your lex and yacc program and filename will be the resulting executable.
(Remember to change the permission of the script file to executable before you use it.) - Submission for Project 2 can be done using Submission Page
Project 3 – Yacc Compiler
- Due
day: Thursday April 22 (no penalty for Friday April 23 submission)
-
ReadMe and s6.l and s6.y are helper programs to help you finish the project.
- Assignment handout: project3.pdf,
- Test files: test1, test2, test3, test4, test5.
- Here is the sample snail program from the handout: sample.snail
Run "yacc-script filename", where filename.l and filename.y is your lex and yacc program and filename will be the resulting executable.
(Remember to change the permission of the script file to executable before you use it.)
Midterm 1 (Regular Languages)
- Examination day: Monday, February 23, in class, duration 1.30 hours.
- Open book examination (you may also use your notes and a laptop without wireless communication).
- Midterm reading material: Chapters 1-4 of book (everything from these chapters that we covered in class).
- Practice Exam: midterm1_pract. Solutions: midterm1_pract_sol.
Midterm 2 (Context-Free
Languages)
- Examination day: Monday, March 29, in class, 1.45 hours.
- Open book examination (you may also use your notes and a laptop without wireless communication).
- Midterm reading material: Chapters 5-8 of book, and respective slides.
- Practice Exam: midterm2_pract. Solutions: midterm2_pract_sol.
Final Exam (Turing Machines)
- Examination day: Monday, April 26, in class, 1.30 hours.
- Open book examination (you may also use your notes and a laptop without wireless communication).
- Exam
reading material: Chapters 9-12 of book, and respective slides.
Practice Exam: final_pract. Solutions: final_pract_sol.
|
Grader |
|
|
1. |
Yu-Shin Cho (TA 2) |
|
2. |
Jing Xi (TA 1) |
|
3. |
Yu-Shin cho |
|
4. |
Jing Xi |
|
5. |
Jing Xi |
|
6. |
Yu-Shin cho |
|
7. |
Jing Xi |
|
8. |
Yu-Shin cho |
|
9. |
Jing Xi |
Quizes with solutions can be found on webct.
Course Related
Send me any course related link you find and I will post it here
File Viewers
· Powerpoint Viewer: viewer for powerpoint documents for Microsoft Windows
· Acrobat Reader: viewer for pdf files
· GhostView: viewer for postscript (.ps) and pdf files for Microsoft Windows and Unix
Text Editors
· Emacs: editor for Microsoft Windows
Text Processors
· Latex: text processor for Microsoft Windows