Intro to Theoretical Computer Science

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 yes-no 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

Orientation Materials

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.

Study Units

Unit 1

Task 1: Read the following:
These materials can also be found in Textbook: 1.1.

Unit 2

Task 1: Read the following:
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.

Unit 3

Task 1: Read the following:
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.

Unit 4

Task 1: Read the following:
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.

Unit 5

Task 1: Read the following:
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.

Unit 6

Task 1: Read the following:
These materials can also be found in Textbook: 3.1 .
Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

Unit 7

Task 1: Read the following:
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.

Unit 8

Task 1: Read the following:
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.

Unit 9

Task 1: Read the following:
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.
1. Prove that every finite langauge is regular.

Unit 10

Task 1: Read the following:
These materials can also be found in Textbook: 3.2.
Task 2: Do the following exercises:
These exercises are NOT homework questions.
They are for helping you understand the materials of this unit.

Unit 11

Task 1: Read the following:
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.

Unit 12

Task 1: Read the following:
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.

Unit 13

Task 1: Read the following:
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.

TEST: Covers Unit 4 - Unit 12 inclusive.

Unit 14

Task 1: Read the following:
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.

Unit 15

Task 1: Read the following:
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.

Unit 16

Task 1: Read the following:
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.

Unit 17

Task 1: Read the following:
Non-regular languages can also be found in Textbook: 2.3 and 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.

Unit 18

Task 1: Read the following:
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.

Unit 19

Task 1: Read the following:
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.

Unit 20

Task 1: Read the following:
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.

Unit 21

Task 1: Read the following:
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.

Unit 22

Task 1: Read the following:
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.

-------------------------------------------------------------------------------------------------------------------

Table of Contents and Course Material

Back to CS 390 Home Page

Theoretical Computer Science

CS 390 Sample Study Schedule - Spring 2013

Last update December 4, 2012

Sample Study Schedule

For Test, Exam and Homework Due Dates click here.

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.

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.

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

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

Textbook: pp. 117 - 118: 3.1 (c), 3.2 (b), 3.3 (a), 3.6 (a) and 3.7 (a)(e), For solutions to these questions click here. Interactive exercises on regular expression 1 click here. Interactive exercises on regular expression 2 click here.

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

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

For solutions to these questions click here.

Textbook: p. 79: 2.10 (a) For solutions to these questions click here.

Textbook: pp. 120 - 123: 3.21 (c), 3.22 (a)(d), 3.25, 3.26, 3.30 and 3.32(a) For solutions to these questions click here.

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

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

Textbook: p. 124: 3.28 (b)(d) and 3.36 For a solution to this question click here.

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

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.

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.

Application of FA Simulation of FA Non-Regular Languages --- Myhill-Nerode Theorem --- To be continued in Unit 18

Textbook: pp. 81 - 83: 2.21 (c) and 2.29 (a)(c)(e)(i) For solutions to these questions click here.

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

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.

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

Combination of Turing Machines Types of Turing Machines --- Optional

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

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

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.

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.

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

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

Textbook: pp. 117 - 118: 3.1 (c), 3.2 (b), 3.3 (a), 3.6 (a) and 3.7 (a)(e),
For solutions to these questions click here.
Interactive exercises on regular expression 1 click here.

Interactive exercises on regular expression 2 click here.

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

Textbook: pp. 77 - 78: 2.5 , 2.8 (a)(b) and 2.12 (b)(e)

For solutions to these questions click here.

Textbook: p. 79: 2.10 (a)
For solutions to these questions click here.

Textbook: pp. 120 - 123: 3.21 (c), 3.22 (a)(d), 3.25, 3.26, 3.30 and 3.32(a)
For solutions to these questions click here.

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

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

Textbook: p. 124: 3.28 (b)(d) and 3.36
For a solution to this question click here.

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

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.

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.

Application of FA
Simulation of FA
Non-Regular Languages --- Myhill-Nerode Theorem --- To be continued in Unit 18

Textbook: pp. 81 - 83: 2.21 (c) and 2.29 (a)(c)(e)(i)
For solutions to these questions click here.

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

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.

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

Combination of Turing Machines
Types of Turing Machines --- Optional

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

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