Theoretical Computer Science
CS 390 Sample Study Schedule  Spring 2013
Last update December 4, 2012
Minor changes may be made on course contents without notice.
Below is a suggested study schedule.
If you follow the instructions in this schedule, you can complete
this course.
It also gives you an estimate of study time of
the materials. Classroom lectures for the Introduction to Theoretical Computer
Science course at ODU Computer Science by this instructor more or less follow
this schedule. Each slot corresponds to about 75 minutes of classroom time.
Sample Study Schedule
Instructions:

Click
underlined items in the table below to get to study materials (units),
homework, test and exam, and do the Tasks specified there.

At the end of most pages there are simple yesno questions. After clicking
"Yes" or "No" buttons, click the "Submit" button. You weill see whether or not
your answers are correct. Try them as much as you can. They are to assist you
in understanding the subjects and are not graded.

To get an overview of the subjects of this course,
visit
Table of Contents and Course Materials

For any questions, contact toida@cs.odu.edu
Week

Units to Study


Week

Units to Study


1

Unit 1,
Unit 2


7

Unit 13,
Unit 14

2

Unit 3,
Unit 4


Submit
Homeworks 7,
8

Submit
Homeworks 1,
2


8

Unit 15,
Unit 16

3

Unit 5,
Unit 6


9

Unit 17,
Unit 18

4

Unit 7,
Unit 8


Submit
Homeworks 9,
,
10

Submit
Homeworks 3,
4


10

Unit 19,
Unit 20

5

Unit 9,
Unit 10


11

Unit 21,
Unit 22

6

Unit 11,
Unit 12


Submit
Homework 11,

Submit
Homework 5,
6


12, 13

Unit 23,
Unit 24,


TEST : Unit 4  Unit 12 inclusive


EXAM :
Unit 4  Unit 22 inclusive 
For Test, Exam and Homework Due Dates
click here.
Unit 1
Unit 2

Task 1: Read the following:

Review of Sets

Review of Recursive Definition

Review of Mathematical Induction
These materials can also be found in Textbook: 1.2, 1.3, 1.5 and 1.6,
respectively.

Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

On Sets: Textbook: pp. 35  37: 1.7 (a)(c), 1.8 (a)(d), 1.9 (g)(i), 1.11 (b)(d) and 1.15 (a)
For solutions to these questions
click here.

On Induction: Textbook: p. 41: 1.45 and 1.48
For solutions to these questions
click here.
Unit 3

Task 1: Read the following:

Review of Relations

Review of Functions
These materials can also be found in Textbook: 1.3.

Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

On Relations: Textbook: pp. 38  39: 1.23 (a)(c) 1.24 2nd row, 1.25 (b), and 1.28
For solutions to these questions
click here.

On Functions: Textbook p. 37: 1.16 (b), 1.17 (a), 1.19 (a), 1.20 (a)(d), and 1.21 (a)
For solutions to these questions
click here.
Unit 4

Task 1: Read the following:

Introduction to Language

Definitions on Language
These materials can also be found in Textbook: 1.4 .

Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

Textbook: pp. 39  40 : 1.31, 1.32, 1.33 (b), and 1.37 (b)
For solutions to these questions
click here.
Unit 5

Task 1: Read the following:

Problem Solving and Language

General Induction
These materials can also be found in Textbook: 1.6.
Note that General Induction is called "Structural Induction" in
the textbook.

Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

Textbook: pp. 42  43: 1.60, 1.62 (a) and 1.65 (a)
For solutions to these questions
click here.
Unit 6
Unit 7

Task 1: Read the following:

Introduction to Finite Automata

Definition of DFA
These materials can also be found in Textbook: 2.1 .
Note that DFA is called FA in the textbook.

Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

Textbook: pp. 77  78: 2.1 (a)(e), 2.2 (c) and 2.3 (a)
For solutions to these questions
click here.
Unit 8

Task 1: Read the following:

Deltastar and Its Properties

Language Accepted by DFA
These materials can also be found in Textbook: 2.1 .

Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

Textbook: pp. 77  78: 2.5 , 2.8 (a)(b) and 2.12 (b)(e)
For solutions to these questions
click here.
Unit 9

Task 1: Read the following:

Properties of Regular Language
Some of these materials can also be found in Textbook: 2.2 .

Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

Textbook: p. 79: 2.10 (a)
For solutions to these questions
click here.
 Prove that every finite langauge is regular.
Unit 10
Unit 11

Task 1: Read the following:

Conversion of NFALambda to NFA
These materials can also be found in Textbook: 3.3.

Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

Textbook: p. 124: 3.37 (a)(e)
For solutions to these questions
click here.
Unit 12

Task 1: Read the following:

Conversion of NFA to DFA
These materials can also be found in Textbook: 3.3.

Task 2: Do the following exercise question:
This exercise is NOT a homework question.
It is for helping you understand the materials of this unit.

Textbook: p. 124: 3.38 (b)(d)
For a solution to this question
click here
Unit 13

Task 1: Read the following:

Equivalence of NFALambda and NFA
These materials can also be found in Textbook: 3.3.

Task 2: Work on the questions of Homework 7 and do the following exercise
question:
This exercise is NOT a homework question.
It is for helping you understand the materials of this unit.

Textbook: p. 124: 3.28 (b)(d) and 3.36
For a solution to this question
click here.
TEST: Covers Unit 4  Unit 12 inclusive.
Unit 14

Task 1: Read the following:

Kleene's Theorem  Part 1
These materials can also be found in Textbook: 3.4.

Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

Textbook: pp. 126  127: 3.45, 3.46 and 3.49(c)
For solutions to these questions
click here.
Unit 15

Task 1: Read the following:

Kleene's Theorem  Part 2

Complement of Regular Language
These materials can also be found in Textbook: 3.5 .

Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

Textbook: p. 127: 3.51 (a)
 Find the complement of the DFA of Figure 3.39 (a) on p. 127 of the textbook.
For solutions to these questions
click here.
Unit 16

Task 1: Read the following:

Regular Grammar

Minimization of DFA
These materials can also be found in Textbook: 4.1, 4.3, 2.5 and 2.6.

Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

Textbook: p. 86: 2.55 (a)(c)

Textbook: pp. 158  159: 4.26(a)(b), 4.29(a)(b).
For solutions to these questions
click here.
Unit 17
Unit 18

Task 1: Read the following:

NonRegular Languages  Pumping Lemma
These materials can also be found in Textbook: 2.4 .

Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

Textbook: p. 81: 2.22 (a)(d)
For solutions to these questions
click here.
Unit 19

Task 1: Read the following:

ContextFree Grammar
These materials can also be found in Textbook: 4.2, and 5.1  5.4.

Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

Textbook: pp. 154  157: 4.1 (b)(f), 4.3 (b) and 4.15

Textbook: p. 197: 5.5 (b)
For solutions to these questions
click here.
Unit 20

Task 1: Read the following:

Turing Machines
These materials can also be found in Textbook: 7.1 and 7.2.

Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

Textbook: p. 257: 7.2, pp. 261  262: 7.33 (a) and 7.34(a)
For solutions to these questions
click here.
Unit 21

Task 1: Read the following:

Combination of Turing Machines

Types of Turing Machines
 Optional
These materials can also be found in Textbook: 7.3 and 7.4, and 7.5  7.8 .

Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

Textbook: pp. 258  259: 7.4 (b), 7.5 (b), 7.9, and 7.17 (b)
For solutions to these questions
click here.
Unit 22

Task 1: Read the following:

Unsolvable Problems
These materials can also be found in Textbook: 9.1 and 9.2 ,
though treated in a different way.
Unit 23

Task 1: Read the following:

More Unsolvable Problems (Reduction of Problems)
These materials can also be found in Textbook: 9.3 .

Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

Textbook: pp. 326  327: 9.3, 9.12 (a) and 9.15 (a)
For solutions to these questions
click here.
Unit 24

Task 1: Read the following:

Time Complexity
These materials can also be found in Textbook: 11.1  11.4 .
FINAL EXAM: Covers Unit 4  Unit 22 inclusive.
