|
| |
 Announcements
This Week
( 4/24/2005 )
 |
Space complexity lecture
handouts are available in the Lecture Handouts
section. |
|
Final Exam is on Monday May
3, 2006. |
Previous Week ( 4/17/2005 )
General
|
Class
Information
|
Semester: Spring 2006
|
|
Location: Pangborn Hall 204
|
|
Lecture
time: Mon and Wed 2:10 pm - 3:25 pm
|
|
Office
Hours: Tu. 2:00 - 4:00 pm or by appointment
|
Class
Instructor
Dr. Sameh M.
Elsharkawy
Office: Pangborn Hall 311
Phone: (202) 319-4620
Email:
Elsharkawy@cua.edu
Course Syllabus
Course (catalog) Description
A systematic study of theory of computing. Topics
include Finite Automata, Fundamentals of computer programming languages
grammars, Regular Languages, Context-Free and Context-Sensitive
Languages, Turing machines, and Computability Theory. The class
introduces the concepts of Computer Problems’ Decidability,
Reducibility, Intractability, and Computational Complexity.
Prerequisites
CSC 113: Computer Programming
CSC 210: Discrete Structures
Textbook
Book name:
Introduction to the Theory of Computation (2nd Edition)
Author:
Michael Sipser
Publisher:
Thomas Course Technology
Edition:
2 nd (2005)
ISBN:
0-534-95097-3
Click
HERE for complete class syllabus available.
Lecture
Handouts
|
Lecture |
Date |
Subject |
|
1 |
Jan 19, 2006 |
Introduction |
|
2 |
Jan 23, 2006 |
Regular
Languages |
|
3 |
Jan 30, 2006 |
Regular
Languages |
|
4 |
Feb 6, 2006 |
Context-Free
Grammars |
|
5 |
Feb 13, 2006 |
Context-Free
Grammars |
|
6 |
Feb 20, 2006 |
Turing
Machines |
|
7 |
Mar 6, 2006 |
Decidability |
|
8 |
Mar 20, 2006 |
Reducibility |
|
9 |
April 10, 2006 |
Time
Complexity |
|
10 |
April 24, 2006 |
Space
Complexity |
| |
|
|
Assignments
Homework 1: Introduction
| Problems: 0.10, 0.11, 0.12 |
| Due date: January
30, 2006. |
Homework 2: Regular Languages
| Problems: 1.4, 1.5, 1.12, 1.16, 1.21 |
| Due date: February 13, 2006. |
Homework 3: Context-Free Grammars
| Problems: 2.4, 2.14, 2.19, 2.26, 2.27 |
| Due date: March
1, 2006. |
Homework 4: Turing Machines and
Decidability
| Problems: 3.2, 3.8, 4.1, 4.7, 4.12, 4.15 |
| Due date: March
20, 2006. |
Homework 5: Reducibility
| Problems: 5.3, 5.4, 5.9, 5.12, 5.16, 5.21 |
| Due date: April
3, 2006. |
Projects
Useful Links
|
| |
|
|
