198:314 Principles of Programming Languages
Fall 2001
Nonprogramming Homework

9/26/2001: These non-programming homeworks will be posted on Wednesday and then collected during the 2nd lecture of the following week (i.e., Thursday for Kremer and Borgida, Weds for Ryder). Throughout the semester, at random we will choose problems on these assignments to grade for credit towards your final grade.

• Assign1 Scott text Ch 2, Exercise 2.3 a,b,c.
  Due in recitation during the week of September 17, 2001.
  
  
• Assign2 Consider strings of 0's and 1's, which have an even number of 0's (i.e., 2k 0's for k=1,2,3,...). Find a finite auotmaton accepting this language.
  Now consider the language that has either 2k *or* 3k 1's in every string, for k=1,2,3,... Give a regular expression and a finite automaton describing this language. (Remember, this may be graded.)
  Due in recitation during the week of September 26-October 3, 2001.
  
  
• Assign3
  1. Write a regular expression for the language of all strings of letters which if they contain vowels, the vowels appear in order (that is, all a's appear before all e's which appear before all i's, etc.). Now write an FSA that recognizes this language.

  2. Build a Prolog predicate stutter(S,T) which when given a list of constants in S (e.g., [1,2,3] or [a,b,c]) builds a new list that repeats every element of the original list, in a sublist. For example, stutter([a,b,c],[[a,a],[b,b],[c,c]]) is true. Also, stutter([1,2],X) associates the value [[1,1],[2,2]] with variable X.
  Due during second lecture in the week of October 1, 2001.
  
  There are some typos in this homework and they have been corrected now. Make sure that you have the corrected version of the assignment. (Updated 10/08/2001 1:21 p.m.)
  

• Assign 4 on Prolog lists, C pointers, arrays and structures. (Last updated 9:30am, 10/4/2001)
  Due during second lecture in the week of October 8, 2001.
  
  
• Assign 5 on pointers and parameter passing.
  Due during second lecture in week of October 15, 2001.
  
  
• Assign 6 on scoping
  Due during the second lecture in the week of November 5, 2001.
  
  
• Assign 7 C++ and memory layout ( pdf)
  Due during the second lecture in the week of November 12, 2001.
  
  
• Assign 8 Types,C++,Scheme ( pdf)
  Due during the second lecture in the week of December 3rd, 2001.
  
  
• Assign 9 Context free grammars
  Due during the second lecture in the week of December 3rd, 2001.
  
  
• Assign 10 Concurrency
  This homework will not be graded. A sample solution will be made available before the final exam. (Done - 12/14/2001)
  

Answers.

last changed by AB 12/14/01 .