程序代写 CMPSC 464 Name:

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