CMPSC 464 Name:
Assignment 4
Nov/03/2022
Time Limit: Due on Nov 17th
Copyright By PowCoder代写 加微信 powcoder
This assignment contains 9 pages (including this cover page) and 7 questions.
Instructions for TEX : If you are writing down the solution in tex, comment out the empty-
box and write your solution in Tex. Make sure your solution does not overflow (meaning it
should stick to a single page)
CMPSC 464 Assignment 4 – Page 2 of 9 Nov/03/2022
1. (15 points) Exercise 8.4 (p.g. 357)
(a) (5 points) Union
(b) (5 points) Concatenation
CMPSC 464 Assignment 4 – Page 3 of 9 Nov/03/2022
(c) (5 points) Star
CMPSC 464 Assignment 4 – Page 4 of 9 Nov/03/2022
2. (15 points) Exercise 8.11 (p.g. 358)
CMPSC 464 Assignment 4 – Page 5 of 9 Nov/03/2022
3. (10 points) Show that PALINDROME is in L
CMPSC 464 Assignment 4 – Page 6 of 9 Nov/03/2022
4. (15 points) Exercise 8.22 part (a) (p.g. 359)
CMPSC 464 Assignment 4 – Page 7 of 9 Nov/03/2022
5. (10 points) Exercise 8.22 part (b) (p.g. 359) (Hint: You may assume previous result)
CMPSC 464 Assignment 4 – Page 8 of 9 Nov/03/2022
6. (20 points) Exercise 8.23 (p.g. 360) (Hint : How to do DFS on a tree using Logspace?)
CMPSC 464 Assignment 4 – Page 9 of 9 Nov/03/2022
7. (15 points) Exercise 8.25 (p.g. 360)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com