University of Nevada Las Vegas
Howard R. Hughes College of Engineering
Department of Computer Science
My Home Page
Course Page

Computer Science 456/656 Fall 2020
Formal Languages and Automata
Assignments and Lecture Topics

Revised December 3, 2020

Turning in Homework during the Covid Crisis
Your answers must be written in a pdf file and emailed to the graduate assistant, Shekhar Singh shekhar.singh@unlv.edu by the posted time on the due date. Your file must not exceed 5 megabyes, and must print out to at most 4 pages.
Monday, August 24, 2020
Welcome! If you have registration issues today, see me right after class.

Wednesday, August 26, 2020
Reading Assignment
Read and study:

Wednesday, September 2, 2020

Thursday, September 3, 2020
Turn in Assignment 1 electronically by 23:59 today.

Monday, September 7, 2020

Wednesday, September 9, 2020
Practice Exam

Thursday, September 10, 2020
Be sure to login to my Zoom office hour today.

Saturday, September 12, 2020
Answers to Practice Exam

Monday, September 14, 2020
Examination today

Wednesday, September 18, 2020

Monday, September 21, 2020
Enumeration.
Enumerable, recursively enumerable, canonical order of a language.
Every language is enumerable. Every acceptable language is recursively enumerable. Every decidable language is recursively enumerable in canonical order.

Wednesday, September 23, 2020

Thursday, September 24, 2020

Friday, September 25, 2020
Assignment 2 electronically by 23:59 today. Finished now
Here are Answers to a homework assignment from last semester which will help you understand how to draw the diagram for a PDA.
There is an error in the diagram for probllem 2. The self loop at state 0 shoulw have 6 labels instead of 2. I cannot seem to get it loaded properly. I haven't figured out what's wrong.

Monday, September 28, 2020
Some True False Questions
These true false questions involve material we have covered in class up to now. The list will be updated before the examination.
(i),(ii),(iii),(iv),(v),((vi),(vii),(viii),(ix),(x),(xi),(xii),(xiii), (xvii),(xviii), (xxxii) ,(xxxiv),(xliv),(xlv),(xlvii),(xlviii),(li),(liii),(liv), (lv),(lvi),(lviii),(lix).
(xiv),(xv),(xvi),(xix),(xix),(xx),(xxiii),(xxvii),(xxix),(xxxvii), (xxxix),(xliii),(xlvi),(lii),(lxii).

Wednesday, September 30, 2020

Friday, October 2, 2020
I plan to hold a Zoom office hour today from 3pm to 5pm. No one joined yesterday, although I know some students tried to get in. Sorry abou that, I'll try to fix it.

Monday, October 5, 2020
Answers to Practice Exam Finished
Corrected 5pm October 6

Tuesday, October 6, 2020
Office hour today 3-5. You will get an invitation on canvas, as usual.

Wednesday, October 7, 2020
Examination today
Practice Exam 2 Ready I might add another problem.

Monday, October 12, 2020

Wednesday, October 14, 2020
I have told you during lecture that SAT is NP-complete, as proved by the Cook-Levin theorem. I also mentioned that I will not give the proof, which is strightforward, but quite detailed and difficult to grasp. However, you can read the proof on the internet.
Cook-Levin theorem: SAT is NP-complete.

I have told you that there is a P-time reduction of SAT to 3-SAT. Since 3-SAT is clearly NP, that proves that 3-SAT in NP-complete. I have not yet (and might not ever) give you that reduction in lecture, but here it is.
Reduction of SAT to 3-SAT

Today I gave a polynomial time reduction of 3-SAT to the independent set problem. Since the independent set problem is NP, and since 3-SAT is NP-complete, the independent set problem is NP-complete. Here is a pdf document summarizing that proof.
Reduction of 3-SAT to the independent set problem.

Today I gave the reduction of the independent set problem to the subset sum problem. The subset sum problem is (trivially) in the class NP. Thus, since the independent set problem is NP-complete, the subset sum problem is NP-complete. Here is a pdf document summarizing that proof.
Reduction of the independent set problem to the subset sum problem.
Reduction of the subset sum problem to the partition problem.

Thursday, October 15, 2020
I plan to hold a Zoom office hour today from 3pm to 5pm.

Monday, October 19, 2020
Computational Classes for CS456
A Simple NC algorithm
Every regular language is NC

Wednesday, October 21, 2020

Thursday, October 22, 2020
Office hour today 3-5

Friday, October 23, 2020
Turn in Assignment 3 by midnight today.
Office hour today 3-5
Problem 3: Addition is NC

Monday, October 26, 2020

Wednesday, October 28, 2020

Thursday, October 29, 2020
I plan to hold a Zoom office hour today from 3pm to 5pm.

Monday, November 2, 2020

Wednesday, November 4, 2020

Friday, November 6, 2020
Turn in Assignment 4 by midnight today.
Corrections: Sat Oct 31 10:56:03 PDT 2020
Condensed version. All problems on one page.
Expanded version. Each problem on a separate page, giving you room to write the answers.
Answers
Remarks on Problem 5. I came up with a proof, but it was sort of complicated, so I searched the internet for a simpler proof that the dominating set problem is $\calN\calP$-complete. At first all I found were proofs that MSC (the minimum set cover problem) reduces to Dominating set, but I didn't give you MSC in the list. Finally, I found a page that gives a reasonably simple proof that one of the problems in my list reduces to Dominating set. Look for it!
Office hour today 3-5
By popular demand, I am postponing the due date to Monday midnight.


Monday, November 9, 2020
Today I gave a polynomial time reduction of 3-SAT to the dominating set problem. Since the dominating set problem is NP, and since 3-SAT is NP-complete, the dominating set problem is NP-complete. Here is a pdf document summarizing that proof.
Reduction of 3-SAT to the dominating set problem.
Office hour today 3-5
Wednesday, November 11, is Veterans' Day, a holiday.

Thursday, November 14, 2020
Office hour today 3-5

Friday, November 15, 2020
Office hour today 3-5 New

Monday, November 16, 2020
Examination today
Practice for Test 3
Answers Newly Corrected! Refresh your Browser!

Wednesday, November 18, 2020

Thursday, November 19, 2020
No office hour today.

Monday, November 23, 2020
Some simple LALR parsers.
Updated Nov 30 15:32:03
GOTO Table of Example 1 Corrected November 27

Wednesday, November 25, 2020

Thursday, November 26, 2020
No office hour today because of the Thanksgiving holiday.

Friday, November 27, 2020
I plan to hold a Zoom office hour today from 4pm to 5pm, even though, technically, we are still in the Thanskgiving recess.

Saturday, November 28, 2020
I plan to hold a Zoom office hour today from 4pm to 5pm.
Monday, November 30, 2020
Turn in Assignment 5 by 23:59 tonight
Answers to Assignment 5 Updated Dec 2 11:02
Corrected
I plan to hold a Zoom office hour today from 4pm to 5pm.

Wednesday, December 2, 2020
Turn in Assignment 6 by 23:59 tonight
Corrected
Consider Assignment 6 to be ``extra credit," meaning that if you haven't mastered the previous topics in the course, skip it.

Thursday, December 3, 2020
I plan to hold a Zoom office hour today from 3pm to 5pm.
Friday, December 4, 2020
ABET Assessment Test
The Accreditation Board of Engineering and Technology (ABET)
requires that we give an assessment test in each required course
for the Bachelor of Science degree in Computer Science.
Print out the above file, answer the questions, and email
a scanned copy to the TA. Do not write your name on the paper.
The requirement applies only to 456 students, not 656.

Wednesday, December 9, 2020
Final Examination 10:10 - 12:10
Practice Final
Updated Nov 30 15:01:59
Answers to Practice Final
Corrected Sat Dec 5 13:40:13 PST 2020
A Lot of True/False Questions
Be sure to also look at true/false questions on the three previous tests.

Back to Course Page