EXERCISES for Weeks 9--12 1. Write a C program that takes an integer and a file name as input and prints out all instances in the file where the number of consecutive occurrences of some character is greater than the given integer. 2. Characterize the language (set of strings) generated by the grammar: S := Ab A := bBa B := Ac A := b 3. Is the language of Question 2 context-free? 4. Give the parse tree that shows why a = b is an "expression" in C. 5. Consider the context-sensitive grammar: S := Ab A := bBa B := Ac Aca := bA A := b Which of the following strings is not in the language generated by this grammar? bb, bbcab, bbbcacab, bbbbbbbbb, bbbcacacacab, bbbbbbcacab, ... 6. The file badnews.c contains #include badnews.c What happens when it is compiled? 7. What does the following program do? #include int f() { int i = 3; while (i > 1) { int i = 3; printf("%d ", i--); if (i > 1) break; } return i--; } main() { int i = 3; printf("%d %d %d\n", f(), f(), f()); } 8. Replace "int" by "static int" in the first line of f in the program above. Now what does it do? (See page 83 of K and R.) 9. Suppose that a disk has 2^24 blocks, 2^12 bytes per block. All files are defined by a block with 2^6 bytes of descriptive info, followed by pointers to data blocks. How big a file can be accommodated? 10. The same disk is configured with 2^16 blocks, 2^20 bytes per block. How big a file can be accommodated? 11. What is wrong with the following program fragment? for (i = 0; i < strlen(a); i++) insert(a+i); 12. Give an input string of length 10 for which the tree of Program 7 produces a tree with all null left links. 13. Show that the string 011001111 is in the language recognized by the following nondeterministic FSA. 14. Find a set of strings that is not in the language recognized by the FSA in question 13. 15. Give a deterministic FSA that recognizes the same language as the nondeterministic FSA in question 13. 16. Draw a nondeterministic PDA that accepts the set of all even-length palindromes. 17. Draw a Turing machine that halts if and only if the input consists of just 1's, and the number of 1's is even. 18. Draw a Turing machine that halts if and only if the input is an alternating sequence of 1's and 2's 19. In Java, suppose that a linked list is made up of nodes of type class Node { public int key; public Node next; Node(int t) { key = t; next = null; } } that you are given a Node "list" which refers to the first node of the list; that the last node has a null link; and that there are at least two nodes on the list. Write a code fragment to delete the second node of the list. 20. Under the same conditions as the previous question, write a code fragment to add a new node with key 5 just after the second node of the list. 21. Sedgewick, Exercise 2.2 22. Sedgewick, Exercise 6.15 23. Sedgewick, Exercise 7.1 24. Sedgewick, Exercise 7.5 25. Sedgewick, Exercise 12.47. (fix bug: "bottom tree in 12.5" -> "4th tree in 12.6") Answers to Exercises for Weeks 9--12 1. main(int argc, char *argv[]) { int i, j, c, prev; int max = atoi(*++argv); FILE *text = fopen(*++argv, "r"); for (i = 0, j = 0; (c = getc(text)) != EOF; i++, j++, prev = c) if ( c != prev ) { if ( j > max ) printf ("%2d %c's at %d\n", j, prev, i - j); j = 0; } } 2. bb, bbcab, bbbcacab, bbbbcacacab, bbbbbcacacacab, bbbbbbcacacacacab, ... Any string in the language must begin and end with a "b". In between there is a string of k "b"s followed by k "ca"s for some k. 3. The language is context-free because it can be generated by a context-free grammar. In general, it's much easier to test if a *grammar* is context- free (check that it follows the rules) that to test if a *language* is (have to find a grammar or prove that none exists). 4. expression assignment-expression unary-expression assignment-operator assignment-expression postfix-expression = unary-expression primary-expression postfix-expression identifier primary-expression identifier 5. bbbcacacacab. There have to be more "b"s than "ca"s, not counting the "b"s at the start and at the end. 6. Puts the preprocessor in a loop. Different compilers react differently. % lcc badnews.c badnews.c:1: badnews.c: Too many open files % cc badnews.c cpp: error ./badnews.c:2: Unreasonable include nesting badnews.c:1: warning: empty input file % gcc badnews.c In file included from badnews.c:1, from badnews.c:1, from badnews.c:1, from badnews.c:1, from badnews.c:1, from badnews.c:1, from badnews.c:1, ... badnews.c:1: macro or `#include' recursion too deep 7. 3 3 3 3 3 3 8. 3 3 3 2 1 9. Pointers must be 3 bytes to accommodate 24-bit addresses. Thus, 1344 pointers ((2^12 - 2^6) / 3) can fit in the defining block, so the file size is 1344 * 2^12 = 5505024. 10. (2^20 - 2^6 / 2) * 2^20 = 1099444518912. (Use bc). 11. Calls strlen() every time through the loop. Takes time proportional to the square of the length of a. (This code was found by Prof. Hanson in a program written by a certain well-known COS 126 professor!) 12. aaaaaaaaaa 13. State transistions A -> A -> B -> A -> A -> A -> B -> B -> B -> B 14. None (accepts all nonempty strings). 15. See slide 15.9 (note use of state 0 for "impossible") A B 0 1 ---- ---- 0 0 0 0 0 0 1 1 0 3 1 0 2 2 1 1 1 3 2 3 16. 17. 18. 19. list.next = list.next.next; 20. Node t = new Node(5); t.next = list.next.next; list.next.next = t; 21. Depends on the computer! These times are on a DEC Alpha. % gcc billion.c time a.out 313.35u 1.16s 10:36 49% 0+1k 1+0io 14pf+0w % gcc -O9 billion.c time a.out 30.64u 0.20s 1:02 49% 0+1k 1+0io 14pf+0w % cc billion.c time a.out 289.52u 1.31s 9:51 49% 0+1k 3+0io 14pf+0w % cc -O9 billion.c time a.out 289.49u 0.96s 9:45 49% 0+1k 10+0io 16pf+0w % lcc billion.c time a.out 45.79u 0.16s 1:31 50% 0+0k 2+0io 2pf+0w 22. E A S Y Q U E S T I O N A E S Y Q U E S T I O N A E S Y Q U E S T I O N A E S Y Q U E S T I O N A E Q S Y U E S T I O N A E Q S U Y E S T I O N A E E Q S U Y S T I O N A E E Q S S U Y T I O N A E E Q S S T U Y I O N A E E I Q S S T U Y O N A E E I O Q S S T U Y N A E E I N O Q S S T U Y 23. E A S Y Q U E S T I O N E A I E N* U Y S T S O Q E A E* I A* E E* I* N O Q* S T S U Y N O* N* S T S U Y* S T S U* S S* T S* T* A E E I N O Q S S T U Y 24. N lg N. It divides the file in half because the partitioning pointers stop on keys equal to the partitioning element. 25. A S E R C H I N G X M P A S E R H C I N G X M P A S E R H I C N G X M P A S E R H I N C G X M P A S E R H I N G C X M P A S E R H I N G X C M P [numerous other answers] STUDY GUIDE for final exam Material that you are responsible for: Lectures 1-24 Kernighan and Ritchie Chapters 1-7, except for certain overly complex sections Sedgewick pages 27-38, 53-119, 127-149, 153-170, 187-212, 217-223, 230-241, 253-258, 303-309, 477-508. Midterm exams Exercises for Weeks 1--12 Programming Assignments 1--8 at least ONE-THIRD of the exam will be taken from the exercises at least ONE-THIRD of the exam will be taken from the midterms at least ONE-THIRD of the exam could be rephrased as "did you do the reading?" Final exam will be "closed-book" EXCEPT that you can bring 1 page of notes (your handwriting, on 8.5 by 11 inch paper, front and back).