CSCI 341 Theory of Computation
|Time:||Tuesday & Thursday 4:10PM - 5:30PM|
|Room:||L.K. Downing Hall 2113|
|Instructor:||Dr. Chunmei Liu|
|Office:||Levis K. Downing Hall 2038|
|Email:||chuliu AT howard.edu|
|Office Hour:||2pm - 3:30pm Tuesday and Thursday|
|URL:||hucs.dynu.net/liu or www.networks.howard.edu/liu|
|Textbook:||Introduction to the Theory of Computation, by Michael Sipser, Thomson Course Technology, third edition. ISBN: 113318779X.|
1. General Course Information
1.1 Current Catalog Description:
Introduction to the classical theory of computer science. A study of the formal relationships between machines, languages and grammars; we will cover regular, context free, recursive and recursive enumerable languages. Sequential machines and their applications to devices, processes, and programming. Models of computation: finite state automata, push down automata, and Turing machines. This course will also introduce undecidability and time complexity theory.
1.2 Prerequisites by Topic:
There is no prerequisite for this course, although taking "Fundamentals of Algorithms" is preferred.
2 Learning Resources
2.1 Required Textbooks
2.2 Department Resources
3 Aims, Objectives, & Program Outcomes
3.1 Course Aims
This course aims to teach students to
- learn core ideas in theory of computing, including how to define and investigate a formalized model of computation
- learn the relative power of the models, and the characterizations of each model
- deepen his/her ability to think clearly, originally and devise correct proofs
3.2 Learning Objectives:
Critical, logical-mathematical reasoning
Ability to transform informal problems into formal ones and vice versa
Ability to apply mathematical knowledge and logic in solving problems
Ability to analyze and summarize problems
Understanding of formal grammars, analysis and compilation
Understanding of the relationship between generative processes and recognition processes
Understanding of hierarchical organization of problems depending on their complexity
Understanding of the logical limits to computational capacity
Understanding of undecidable problems
3.3 Relationship between Learning Objectives and Program Outcomes
A. An ability to apply knowledge of computing and mathematics appropriate to the discipline
J. An ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices
4 Teaching and Learning Activities
4.1 Learning Activities
Tuesday and Thursday Lectures (Lecture Series): A detailed teaching plan can be found in section 4.2
1, 2, 3, 4, 5, 6, 7, 8, 9
4.2 Major Topics Covered in the Course (tentative schedule)
|Part 0: Introduction||Ch. 0||Introduction: Sets, strings and languages, theorems and proofs||1 week: 8/20|
|Part 1: Automata and Languages (Ch.1-Ch.2)||Ch. 1||Regular Languages: finite automata, nondeterminism, regular expressions, nonregular languages, the pumping lemma||4 weeks: 8/27, 9/3, 9/10, 9/17|
|Ch. 2||Context-free Grammars: context-free grammars, pushdown automata, non-context-free languages, the pumping lemma||3 weeks: 9/24, 10/1, 10/8|
|Part 2: Computability Theory||Ch. 3||The Church-Turing Thesis: Turing machines, variants of Turing machines, the definition of algorithm||3 weeks: 10/8, 10/15, 10/22|
|Part 3: Undecidability||Ch. 4.2||Undecidability||1 week: 10/29|
|Part 4: Time Complexity||Ch. 7.1||Time Complexity Theory (P and NP)||1 week: 11/5|
The instructor reserves the right to change the course content, omit parts of
the topics listed above or introduce new material midstream to supplement the course text.
5.1 Assessment Summary (tentative schedule)
|Assessment Task||Assignment Date||Due Date||Weighting|
1.1, 1.2, 1.3, 1.4 (a, c, e, f, g), 1.6(a, c, e, f, g)
1.5 (c, d), 1.7 (b, c), 1.8a, 1.9a, 1.10 a
1.16 b, 1.17 a, 1.21 a, 1.29b
|Project||9/20||10/2, 10/12, 11/2, 11/27||20%|
2.1 (b, d), 2.4 (b, c, e, f), 2.16, 2.30 a
5.2 Course Grading (actual grading percentage may change during the term)
The assignments and exams all contribute significantly to your grade. Specifically, your final course grade will be calculated as follows:
Class participation: 5%
Midterm exam: 20%
Final Exam: 25%
A: 90-100, B: 80-89, C: 70-79, D: 60-69, F: 0-59
a. No late submissions are accepted.
5.4 Attendance policy:
You are expected to and should attend classes regularly and complete all assignments on time. Class attendance may be a factor in determining the course grade. If you must miss a class, it's a good idea to let your instructor know in advance or as soon thereafter as possible. If you don't explain your absence, your instructor may assume you don't care about the class or your grade. Coming to class late three times will be counted as one class absence. And later than 10 minutes will also be counted as one class absence. Students are required to attend class during the regularly scheduled tests and the final exam unless prior arrangements have been made.
5.5 Plagiarism Policy
Howard University has adopted a new policy on plagiarism and cheating. In short, all instances of plagiarism will be resolved by an office of the administration, which will conduct the appropriate hearings. See the section entitled "ACADEMIC CODE OF STUDENT CONDUCT" on pages 26-27 of the "Student Reference Manual and Directory of Classes."
The Americans with Disabilities Act requires institutions to accommodate the needs of persons with disabilities. If you need special arrangements such as sign language interpreters or audiotapes of lectures, please make an appointment to see me.
7. Howard University Statement on ADA Policies and Procedures
Howard University is committed to providing an educational environment that is accessible to all students. In accordance with this policy, students in need of accommodations due to a disability should contact the Dean of Student Services for verification and determination of reasonable accommodations as soon as possible. Note: Accommodations are not retroactive. The Office of Student Services is located in Suite 725 of the Howard Center and may be reached at (202) 238-2420.
8. Howard University Statement on Interpersonal Violence
Howard University takes sexual assault, dating violence, domestic violence, stalking and sexual harassment seriously. If a student reveals that he or she needs assistance with any of these issues, all Responsible Employees, which includes faculty, are required to share this information with the University Title IX Office (806-2550) or a student can be referred for confidential services to the Interpersonal Violence Prevention Program (IVPP) (238-2382) or University Counseling Services (806-6870). For more information about these services, please go to www.CampusSafetyFirst.howard.edu.
9. Syllabus Addendum
The following understandings, expectations, and requirements shall apply to all classes that are offered by the College of Engineering and Architecture, effective fall 2016. These are the expectations that the students can have from their professors, and the expectations that the professors will have from each student taking her/his class. These are intended promote the success of our students here at Howard, and after graduation.
Students expect that their professors will:
1. Care about the success of each student, and promote mutual respect.
2. Come to every class, and on time.
3. Keep abreast of the technical field she/he is teaching.
4. Explain how the subject being taught is broadly connected to the field and possibly to other courses.
5. Keep abreast of, and adapt to, evolving teaching approaches.
6. Have office hours for each class, and be present at these times.
7. Coordinate any travel with his/her Department Chairs.
Students who feel that a professor fails in the above expectations may confidentially express his concerns in the Comments box in the Office of Student Services in the L. K. Downing Building, Room 1114, or email Dr. Rhoulac Smith, Director of Student Services, at firstname.lastname@example.org. Your communication must be respectful, professional, and truthful.
Professors expect that their Students will:
(Failing to comply will result in appropriate penalties. In certain cases these penalties are expressly defined below.)
Take a professional approach to all class activities and interactions. Show that your take the class seriously and come to class prepared.
2. Absenteeism: Come to every class.
， 2% penalty from total class grade for every unexcused absence
3. Lateness: Not come to class after it begins.
， 1% penalty from total class grade for every instance of infraction
4. Leaving Early: Not leave class before it ends.
， 1% penalty from total class grade for every instance of infraction
5. Disruption: Avoid entering and leaving the classroom during instruction.
6. Eating: No eating in class.
， 1% penalty from total class grade for every instance of infraction.
7. Electronics: No use of laptop, cell phone, iPad, headphones or other electronic equipment that are not explicitly requested to be used by the Professor.
， 1% penalty from total class grade for every unexcused absence
8. Cheating: Any form of cheating, including plagiarism, in an exam or assignment shall automatically result in a zero-grade for all involved, for that exam or assignment.
9. Communication: Communication, oral or written, with the Professor, including email, in all matters concerning the course, shall be done professionally; that is, as it would be done with a potential employer. (e.g., respectful, include your full name, clearly articulate the objective of the communication concisely)