CS61A Homework 14

Due by 11:59 PM on (that is, the end of) Tuesday, 8/7

This homework must be submitted online. We do not require a paper copy. If you would like a reader to give you written feedback on your homework, submit a paper copy to the homework box.

To turn in the electronic copy, submit all of your answers in files named hw14.py. Follow the instructions here to submit the electronic copy.

If you would like, you can use the template files hw14.py. To copy this file to your lab account you can run the command:

      cp ~cs61a/lib/hw/hw14/hw14.py .

to copy it into your current directory.

This homework uses the PyGic interpreter, which can be found in lib/python_modules/pygic. If you are on an instructional machine, you should not need to copy this file to your account. However, if you would like to copy it to your account you can use the command:

      cp -r ~cs61a/lib/python_modules/pygic .

to copy it into your current directory.

To load your homework file into the PyGic interpreter, run the following command in the directory that contains the pygic folder:

      python3 -m pygic.interpreter hw14.py

This assumes that the homework file is located in the same directory that contains the pygic folder. The path to the homework file should be changed if it is in a different directory.

You can then type the test cases provided below, along with your own test cases, to check your rules, facts and queries.

In homeworks, we have three different categories of questions:

Core Questions — Questions that we believe test a core concept of the course and should be your highest priority when attempting the homework.
Reinforcement Questions — Questions that we believe have material that is either covered by other questions in this homework or in past homeworks, and can therefore be considered second priority after the core questions have been completed.
Extra for Experts — As in earlier homeworks, these problems are completely optional. You are encouraged to try these questions once you have completed questions from the other two categories. However, these are questions that we consider either more difficult than what we would ask you on an exam or that focus on ideas we are not concerned with in this course, so please do not be discouraged if you do not solve them.

It is our hope that these categories will help guide you in deciding how to divide your time when working on the homeworks.

Contest Voting

Please vote for your favorite entry in this summer's CS61A Recursion Exposition contest. The winner should exemplify the principles of elegance, beauty and abstraction that are prized in the Berkeley computer science curriculum. As an academic community, we should strive to recognize and reward merit and achievement (translation: please don't just vote for your friends).

To see the entries, look at the contest gallery. Then, vote for your favorite contest entry by replacing the entry numbers in the facts at the top of your HW14 submission, and turning it in as usual.

We will award prizes for the winning entry in each of the following categories.

Featherweight. At most 128 words of Scheme, not including comments and delimiters.
Heavyweight. At most 1024 words of Scheme, not including comments and delimiters.

Core Questions

Q1. In the template file, we have provided the relationships between many of the characters in the Harry Potter universe. For this question, we will use the PyGic interpreter to deduce a few facts about these relationships.

(a) Provide the query that will list all the children of Molly (Weasley). Each child will be listed when the query is asked for more.

(b) Provide the query that will list all the people who are married and their spouses. Each couple will be listed when the query is asked for more.

(c) Write the rule that will determine if a person is a sibling of another person. Two people are siblings if they have the same parent. We show a few sample queries below:

      P?> sibling(ron, fred)
      Yes.
      P?> sibling(fred, ?who)
      Yes.
      ?who = bill
      P?> more?
      Yes.
      ?who = charlie

(d) Notice that, when we specify who is married to whom, we use facts of the form

      fact married(ron, hermione)
      fact married(hermione, ron)

We could just as easily have defined just one fact

      fact married(ron, hermione)

and the following rule

      rule married(?who, ?spouse):
          married(?spouse, ?who)

This does not work as expected, however. What happens, and why?

Hint: We have provided the suggested rule as a comment. You can uncomment it and comment out the fact that Hermione marries Ron, and then run the query

      married(?who, ron)

Try asking the same query for more responses.

Q2. A molecule of deoxyribonucleic acid, or DNA, consists of two long strands of four nucleotides: adenine (A), thymine (T), cytosine (C), and guanine (G). The two strands are complementary to each other. This means that a nucleotide on one strand is bonded to its complement on the other: adenine will be bound to thymine, and cytosine will be bound to guanine.

In the template, we have asserted facts about the complements of these nucleotides. Using these facts, write rules and facts for rev_comp_strand, which will relate a strand of DNA, represented as an arbitrarily long list of four symbols, with its reverse complement, which is another strand of DNA that has the complementary nucleotides, but in reverse order.

      P?> rev_comp_strand(<t, c, t, g, a>, ?what)
      Yes.
      ?what = <t, c, a, g, a>

Q3. Write the facts and the rules for add_to_all, which will add an item to the front of every sublist in a list.

      P?> add_to_all(a, <<b, c>, <b>, <foo>>, ?what)
      Yes.
      ?what = <<a, b, c>, <a, b>, <a, foo>>
      P?> add_to_all(?what, <<c>, <d, e>, <>>, <<b, c>, <b, d, e>, <b>>)
      Yes.
      ?what = b
      P?> add_to_all(?what, ?list, <<b, c>, <d, e>, <b>>)
      No.

Q4. Write the facts and the rules that will relate one list with a list of sublists of elements in the first list.

      P?> sublists(<1, 2, 3>, ?what)
      Yes.
      ?what = <<>, <3>, <2>, <2, 3>, <1>, <1, 3>, <1, 2>, <1, 2, 3>>

Hint: You will find the add_to_all rule that you defined in the previous question useful.

Reinforcement Questions

Q5. Write the facts and the rules that will "unzip" a list into two smaller lists, where the first smaller list consists of the elements at the odd positions (counting from 1) of the original list, and the second smaller list consists of the elements at the even positions. You may assume that the list is of even length.

      P?> unzip(<a, b, c, d, e, f>, ?odds, ?evens)
      Yes.
      ?odds = <a, c, e>
      ?evens = <b, d, f>
      P?> unzip(?what, <a, b, c>, <d, e, f>)
      Yes.
      ?what = <a, d, b, e, c, f>

Q6. For this question, we will invent an arithmetic system within PyGic. We will use the unary representation of positive numbers, where each number is represented as a list (of any item) that is as long as the number is big. Here, we will represent any number as a list of as. For example, the number 3 is represented by the list <a, a, a> and the number 0 is represented by the list <>.

(a) Write the facts and the rules that will relate two numbers and their sum:

      P?> sum(<a, a, a>, <a, a>, ?what)
      Yes.
      ?what = <a, a, a, a, a>
      P?> sum(<a, a, a>, ?what, <a, a, a, a, a, a, a>)
      Yes.
      ?what = <a, a, a, a>

Hint: What other rule on lists is this similar to?

(b) Write the facts and the rules that will relate two numbers and their difference:

      P?> difference(<a, a, a>, <a, a>, ?what)
      Yes.
      ?what = <a>
      P?> difference(<a, a, a, a, a, a, a>, ?what, <a, a, a>)
      Yes.
      ?what = <a, a, a, a>

Hint: How does this relate to the rules for addition (sum)? In other words, if a + b = c, what does this tell us about c - b?

(c) Write the facts and the rules that will relate two numbers and their product:

      P?> product(<a, a, a>, <a, a>, ?what)
      Yes.
      ?what = <a, a, a, a, a, a>
      P?> product(<a, a>, ?what, <a, a, a, a, a, a>)
      Yes.
      ?what = <a, a, a>

Hint: The product of two numbers can be defined recursively, and the definition will use the rules for addition.

(d) Write the facts and the rules that will compare two numbers:

      P?> gt(<a, a, a, a>, <a, a, a>)
      Yes.
      P?> lt(<a, a, a, a>, <a, a, a>)
      No.
      P?> gt(<a, a, a, a>, <a, a, a, a>)
      No.
      P?> ge(<a, a, a, a>, <a, a, a, a>)
      Yes.
      P?> le(<a, a, a, a>, <a, a, a, a, a, a, a, a>)
      Yes.

Hint: Note that the gt comparison and the lt comparison are related, as are the ge and the le comparisons.

(e) Write the facts and the rules that will check the equality of two numbers:

      P?> eq(<a, a, a, a>, <a, a, a>)
      No.
      P?> ne(<a, a, a, a>, <a, a, a>)
      Yes.
      P?> eq(<a, a, a, a>, <a, a, a, a>)
      Yes.

Hint: You may find the difference rules useful.

(f) Write the facts and the rules that will divide two numbers:

      P?> quotient(<a, a, a, a, a, a>, <a, a, a>, ?quo, ?rem)
      Yes.
      ?quo = <a, a>
      ?rem = <>
      P?> quotient(<a, a, a, a, a, a>, <a, a, a, a>, ?quo, ?rem)
      Yes.
      ?quo = <a>
      ?rem = <a, a>

Hint: If we divide a number N by a divisor D, then the quotient Q and the remainder R are related as N = D * Q + R, where R < D.

Extra for Experts

(Open-ended) Extend the arithmetic system to include negative numbers and rational numbers.