Computer Science 60
Principles of Computer Science
Fall 2001

Assignment 1, Due WEDNESDAY, September 12, 2001

Introduction

This warm-up assignment is due on Wednesday, September 12. (Per the automatic grace policy, you actually can turn it in as late as Thursday midnight. However, there will be another more extensive assignment by then, so it is best not to wait, unless you have an emergency.) Please see the tutoring schedule for the schedule of tutoring hours. You may also send e-mail to cs60help@cs.hmc.edu for specific questions.

Readings

Before submitting this assignment, you will need to familiarize yourself with Unix, the operating system used on turing. You will also need to learn the basics of emacs, the text editor of choice. (If you have another editor that you prefer to use on turing, that is fine.) Finally, it may be worth spending some time learning to an e-mail program such as pine or elm. Documentation on Unix, emacs, and other items can be found on the CS 60 homepage under "Reference Links". Please spend some time reading this, and trying out Unix, emacs, and pine before embarking on the main part of the assignment. The grutors and CS staff in the terminal room will be happy to help you when you have questions.

You should also have read Chapters 1 and 2 in the course text before starting this assignment.

Submission Process

    cs60submit assign1.rex

(Make sure that assign1.rex is in the current directory when you do this!) You will be prompted for theassignment number; answer with the number 1. Remember, you can submit the assignment as many times as you want. The graders will grade only the last submission you make, so this is a great way to make backups of your work as you go along.

The Assignment

1. Products of primes
   • In a rex comment, describe how one could use lists to represent strictly positive integers as products of prime numbers. Be sure to explain how one can reconstruct the natural number from the list representation. Your encoding of an integer should have a size roughly proportional to the number of distinct prime factors.
   • Define the variable thirty to be the result of representing the number 30 using this representation. [It is very important that in all assignments you use exactly the names specified for variables and functions! Some assignments will use an automated grading process that will give you no credit if you fail to follow directions.]
     
     
2. Map Coloring

   Consider a computer application that colors 2-dimensional maps for publication purposes. A map consists of a set of countries (or other political regions). Assume that each country is a contiguous region. Any two countries either touch or do not. When the application colors a map, it cannot color two touching countries with the same color. The application always uses the smallest number of colors possible to color a map.

   1. As a rex comment, describe a representation of the input for this problem, which would be a description of which countries touch which other countries. (Assume that every country touches at least one other country; we then know that every country is mentioned in the description of adjacent countries.)
   2. As a rex comment, describe a representation of the output for this problem, an assignment of a color number to each country, starting with numbers 1, 2, ... up to whatever number of colors is necessary.
   3. Define the rex variables map_input and map_output to be the corresponding list representations for the following example (selected North African countries, from http://www.sas.upenn.edu/African_Studies/CIA_Maps/Africa_19850.gif)

      Input:

      • Algeria touches Libya, Mali, Mauritania, Morocco, Niger, Tunisia, and Western Sahara.
      • Chad touches Libya, Niger, Sudan.
      • Egypt touches Libya, Sudan.
      • Libya touches Algeria, Chad, Egypt, Niger, Sudan, Tunisia.
      • Mali touches Algeria, Mauritania, Niger.
      • Mauritania touches Algeria, Mali, Western Sahara.
      • Morocco touches Algeria, Western Sahara.
      • Niger touches Algeria, Chad, Libya, Mali.
      • Sudan touches Chad, Egypt, Libya.
      • Tunisia touches Algeria, Libya.
      • Western Sahara touches Algeria, Mauritania, and Morocco.

      Output:

      • Algeria is color number 1.
      • Chad is color number 1.
      • Egypt is color number 1.
      • Libya is color number 2.
      • Mali is color number 2.
      • Mauritania is color number 3.
      • Morocco is color number 3.
      • Niger is color number 3.
      • Sudan is color number 3.
      • Tunisia is color number 3.
      • Western Sahara is color 2.
3. Equivalence Relations

   The text explains that binary relations can be identified with sets of ordered pairs; two elements x and y are said to be related by this relation if the pair (x,y) is in the set. A relation is reflexive if every element in the domain of interest is related to itself; that is, if the pair (x,x) is in the relation for every relevant x. A relation is symmetric if whenever (x,y) is in the relation so is (y,x). Finally, a relation is said to be transitive if whenever (x,y) and (y,z) are in the relation, so is (x,z).
   
   An equivalence relation is a binary relation that is reflexive, symmetric and transitive. For example, given the finite set S = {1,2,3,4,5,6,7}, the relation on this set that relates two numbers in this set if they have the same remainder when divided by three (also known as equivalence mod 3) is an equivalence relation. As discussed in the text, we can represent relations on a finite set as a list of all the pairs that are related:

           [[1,1], [1,4], [1,7],
            [2,2], [2,5], 
            [3,3], [3,6], 
            [4,1], [4,4], [4,7],
            [5,2], [5,5], 
            [6,3], [6,6], 
            [7,1], [7,4], [7,7]]
       

   However, the properties of equivalence relations permit a more compact encoding.
   
   
   1. In a rex comment describe how, given a finite set, one could efficiently encode any equivalence relation on this set. Ideally your encoding should mention each element of the set only once.
   2. Define the variable mod3 to be the result of representing the above relation using your encoding.
      
      
4. Labeled Graphs

   The text describes ways to represent directed graphs; a labeled directed graph is a directed graph where every arrow has a corresponding label. In such graphs we permit more than one arrow between two nodes (or from a node to itself) as long as the arrows have different labels. The same label may appear on several different arrows (as long as the arrows do not have both the same source node and target node).

   1. In rex comments, describe at least 3 different representations of labeled directed graphs using lists.
   2. Define the variables graph1, graph2, etc. to be implementations of the following labeled graph for each of your representations. (Remember that you will need to represent the nodes using strings such as "a" in your rex code.)