CSE 30151 Spring 2008: Theory of Computing

General Information

Class Schedule

Instructor

Teaching Assistant

Course Description

This course introduces students to formal languages and automata, computability theory, and complexity theory with the goal of developing understanding of the power and limits of different computational models. The topics covered include:

Grading

Grading for this course will be based on homework assignments (HW), a course project (CP), two midterm exams (ME), and the final exam (FE). Tentatively, the grade will consist of 30% HW, 15% CP, 15% each ME, and 25% FE. There will be several homeworks and a course programming consisting of three parts.

Textbooks

Textbook: Additional resources:

Assignment Policies

Academic Integrity

Computer science, as a profession, requires us to seek truth not only in scientific discoveries, but also in dealing with the public, as the public depends on our expertise and honesty to construct their computing infrastructure. Thus, competence and trust are essential to being a scholar and a computing professional in particular.

Your instructor will treat you as a professional, and you should plan on conducting yourself in an appropriate way. No behavior that compromises academic honesty (such as use of someone else's work or code, using prohibited materials during tests, or making your work available to others) will be tolerated in this course. If you need assistance with anything, do not hesitate to contact the instructor.

Both ND Academic Code of Honor and ND CSE Honest Policy are in effect. It is expected that your work represents your own understanding of the problem. If work of others is used, it must be properly cited. Use of properly cited material is acceptable, but no referencing is treated as claiming the work as your own.

Course Schedule

Date Topic Textbook sections Assignments
Tuesday, January 15 Introduction and course outline Section 0.1  
Thursday, January 17 Preliminary math Section 0.2  
Tuesday, January 22 Proof types and languages Sections 0.3–0.4 hw1 is assigned
Thursday, January 24 Finite automata Section 1.1 project 1 is assigned
Tuesday, January 29 NFAs and DFAs Section 1.2 hw1 is due; hw2 is assigned
Thursday, January 31 Closures and regular expressions
pp. 57-69
Sections 1.2–1.3  
Tuesday, February 5 Regular and nonregular languages Sections 1.3–1.4 hw2 is due; hw3 is assigned
Thursday, February 7 Nonregular languages; state minimization Section 1.4 project 1 is due on Friday
Tuesday, February 12 State minimization, context-free grammars Section 2.1 hw3 is due; hw4 is assigned
Thursday, February 14 Context-free grammars, ambiguity Section 2.1  
Tuesday, February 19 Midterm review   hw4 is due
Thursday, February 21 First midterm Sections 0 and 1  
Tuesday, February 26 Pushdown automata Section 2.2 hw5 is assigned
Thursday, February 28 PDA and CFGs; determinism Section 2.2 project 2 is assigned
Tuesday, March 4 Spring break    
Thursday, March 6 Spring break    
Tuesday, March 11 Parsing; non-context-free languages Section 2.3 hw5 is due; hw6 is assigned
Thursday, March 13 Practice session    
Tuesday, March 18 No class    
Thursday, March 20 No class    
Tuesday, March 25 Non CGLs; Turing machines Sections 2.3 and 3.1 hw6 is due; hw7 is assigned
Thursday, March 27 Turing machines and algorithms Sections 3.1–3.3 project 2 is due on Friday
Tuesday, April 1 Universal TMs; decidability Section 4.1 hw7 is due; hw8 is assigned
Thursday, April 3 Undecidable languages; reducibility Sections 4.2 and 5.1  
Tuesday, April 8 Midterm review   hw8 is due; project 3 is assigned
Thursday, April 10 Second midterm    
Tuesday, April 15 Reducibility; time complexity Sections 5.2–5.3 and 7.1–7.2 hw9 is assigned
Thursday, April 17 Class NP; NP-completeness Sections 7.3–7.4  
Tuesday, April 22 NP-complete problems Section 7.5 hw9 is due; hw10 is assigned
Thursday, April 24 Introduction to cryptography    
Tuesday, April 29 Course review   hw10 is due; project 3 is due on Thursday