Name _________________________

CS 60

Information Structures Worksheet 1

This worksheet is keyed to the first part of Chapter 2 of the notes. Completing and submitting it by the next class, Sept. 13, is worth 15 points of the (around) 1000 on which your grade is computed. (Learning the concepts could be worth more.)

You may refer to the hard copy of the notes or the on-line version.

Instructions: Write your answers above each line. Anything you write after the discussion in class is to be written below the line.

1. Using the notation of Chapter 2 of the text, [7, 11, 13] represents:

________________________________________________________.

2. The differences between a list and a set are:

________________________________________________________.

3. Under what conditions are two lists equal?

________________________________________________________.

4. What does the fundamental list dichotomy say?

________________________________________________________.

5. What is mean by the first and rest of a list?

________________________________________________________.

6. Under what condition(s) are first and rest not meaningful?

________________________________________________________.

7. What is meant by a binding?

________________________________________________________.

8. The notation [F | R] represents what?

________________________________________________________.

9. In the rex language, what does the equation [F | R] = L mean?

________________________________________________________.

10. When is the above equation not meaningful?

________________________________________________________.

11. The notation [F, S, T] represents what?

________________________________________________________.

12. The notation [F, S | R] represents what?

________________________________________________________.

13. The notation [F | S , R] represents what?

________________________________________________________.

14. In the equation [F, S | R] = [7, 11, 13, 17] what are the resulting bindings?

________________________________________________________.

15. In using a list to represent a set, we agree to what convention?

________________________________________________________.

16. What do we mean by the length of a list having lists as elements?

________________________________________________________.

17. What do we mean by the leafcount of a list ?

________________________________________________________.

18. The notation [ [F, S], T | R] represents a list of what form?

________________________________________________________.

19. What is meant by a binary relation?

________________________________________________________.