The goals of this lab are to:

• Introduce you to $\LaTeX$ for writing mathematical documents.
• Practice the git electronic submission system.
• Gain proficiency with basic mathematical concepts we will be using regular.
• Transfer basic mathematical concepts into small working programs.

This assignment consists of two parts: a written homework and a programming portion. Write your written solution using $\LaTeX$. You can use python, C, C++, or java for your coding portion, but I strongly encourage you to use python. Submit both the written and coding portion using github. This is an individual assignment. It is OK to discuss approaches at a high level, but you must do your own write-up. Do not share your write up with others, and do not read other student's solutions. Please refer to the syllabus or ask me if you have questions about the policy.

As with all lab assignments this semester, you will use git, a version control system, to get starting files as well as handing in your assignments. When you start an assignment, you'll execute a git command to grab some starting files. Similarly, when you want to submit an assignment, you'll execute a couple of git commands. Later on in the course, you'll be using git to facilitate paired lab assignments.

Git is a large piece of software, and there is a lot to learn with git. Fortunately, it is easy to get up and running on git with just a small number of commands.

1. If you have not set up account before, there are a couple of steps you need to take to start using git. First do the initial setup steps listed here. It is assumed most students have done this as part of CS31 or CS35.
2. Create a cs46 folder and change to that directory

   cd ~/
   mkdir cs46
   cd cs46
   

3. Finally, clone the git repo for lab01 by executing this command:

   git clone git@github.swarthmore.edu:CS46-S18/lab01-<user>.git  ./lab01
   

   where <user> is your ITS username.
4. At this point, you should have the lab starter code and be ready to start the lab.
5. We recommend that you read the "Commands for using a git repo" that lists the commands that you will need to submit your lab assignments. In particular, you should understand how to use "git add", "git commit" and "git push".

As a reminder, the git commit cycle is git add, git commit, git push. Don't forget to git push when you have completed an assignment.

These questions appear in hw01.tex which you can edit to write your solution. Please read Sipser Chapter 0 before starting this homework.

1. Sets and Strings.
   1. For a set $A$ of size 3, how many elements are in the powerset of $A$? What is the fewest number of elements in any element of $2^A$? What is the maximum number of elements in any element of $2^A$?
   2. Let $\Sigma = \{a,b,c\}$ be an alphabet over three letters. How many unique strings $w$ of length $|w| \leq 3$ can you make from $\Sigma$? How does this compare to the number of elements in $2^\Sigma$?
   3. Let $A=\{a,b,c\}$ and $B=\{b,c,d\}$. Formally define the sets $A \cap B, A \cup B$, and $A \times B$ by listing their elements.
2. Review the definitions of reflexive, symmetric, and transitive on page 9 of the text before answering this questions. Consider the following set of family members $A = $ {you, sister, mother, father's brother (uncle), paternal grandfather, maternal grandmother}. Let $R \subseteq A \times A$ be the ancestor relation, meaning the ordered pair $(a,b) \in R$ if $a$ is an ancestor of $b$.
   1. List three ordered pairs from the set $A \times A$ that are in the relation $R$.
   2. List three ordered pairs from the set $A \times A$ that are not in the relation $R$.
   3. Is the ancestor relation symmetric? Explain.
   4. Is the ancestor relation transitive? Explain.
3. A natural isomorphism between sets $A$ and $B$ is a simple bijective function, $f: A \mapsto B$, that can be considered a slight re-writing of elements from either set. For example, let $A = \{ a, b, c \}$ and let $B = \{ (a), (b), (c) \}$ be a set of singleton tuples. While there are many bijections between $A$ and $B$, the one that maps $ x \in A $ to $ (x) \in B$ seems "natural". In addition to the term natural isomorphism, we define for two sets $A$ and $B$ the expression $B^A$ to be the set of all functions from $A$ to $B$. Let $B= \{ 0, 1 \}$, and let $A = \{ p, q, r \}$.
   1. Give an example of one element of $B^A$
   2. Write the power set of $A$, $2^A$.
   3. Describe a natural isomorphism between $B^A$ and $2^A$.

Write a program that lists all the elements of the power set of $n$ elements in short lexicographical order. You may assume that the elements are labeled ${a, b, c, \ldots}$ and that $n \leq 15$. Your program should take a single command line argument as the parameter $n$. A skelton version of this program is provided for you in power.py where you only have to modify the makePowerSet function. Here is some sample output:

$ python power.py 3
''
'a'
'b'
'c'
'ab'
'ac'
'bc'
'abc'

$ python power.py 1
''
'a'

Your algorithm should run in $O(n2^n)$ time. That may sound terrible, but recall that the size of the power set of $n$ elements is $2^n$, and each element is set of size $O(n)$, so you can't really make it faster and still display all the elements. Also, $n < 15$ is small. That said, what you can't do is produce the power set in unsorted order and then run a sort algorithm to put the elements in short lexicographical order. That would take a minimum of $O(n^2 2^n)$ time. So, you have to be clever and generate the elements of the power set in order. One way to do this is to consider that sets of size $k+1$ are generated by adding 1 element to sets of size $k$. Thus, if you have a list of all subsets of size $k$ you can inductively build larger lists. Again, you have to be a bit careful in the way you design this step so that it doesn't take too long and generate a bunch of elements that don't belong. Python has a set and frozenset class. You are not allowed to use these. Python lists and maybe a dictionary are the only tools you need. You can use the argv list from the sys module to get a list of all command line options:

import sys

print("command: %s" % sys.argv[0])

if len(sys.argv) < 2:
  print("Usage %s <n>" % sys.argv[0])
  sys.exit(1)

n=int(sys.argv[1])
print n

The function ord(let) returns the integer ASCII value of character let; the function chr(val) returns the ASCII character with integer value val. Note ord(chr(val))==val and chr(ord(let))==let. You can construct a set of n letters using the following snippet

def shiftLet(ch, num):
  return chr(ord("a")+num)

n=int(sys.argv[1])

alpha=[]
for i in range(n):
  alpha.append(shiftLet("a",i))

If L1 and L2 are two lists, you can combine the two sets using either L3=L1+L2 or L1.extend(L2). The first example makes a new list L3, while the second modifies L1 by appending all elements in L2.

Use strings to represent elements of the power set. Instead of writing {a, b, c} you can just use 'abc'

Sometimes it might be helpful to copy a list. Use the string slicing operator l[:] to do this, e.g.,

l=range(5)
l2=l #this probably doesn't do what you want

l.append(10)
print(l)
print(l2)

#------------

l=range(5)
l2=l[:] #OK

l.append(10)
print(l)
print(l2)

Don't loop over a list that you are modifying inside the loop. This is weird, and often wrong, e.g.,

l = range(5)
for i in l:
  l.append(2*i) #wee infinite loop

#--better, non-infinite solution below --

l = range(5)
newL = []
for i in l:
  newL.append(2*i)

l.extend(newL)

Once you have edited the files, you should publish your changes using the following steps:

$ git add hw01.tex power.py

The git add step adds modified files to be part of the next commit to the github server.

$ git commit -m "completed lab1"

The git commit step makes a record of the recently added changes. The -m "completed lab1" part is a descriptive message describing what are the primary changes in this commit. Making a commit allows you to review or undo changes easily in the future, if needed.

$ git push

The git push command sends your committed changes to the github server. If you do not run git push before the submission deadline, the instructor will not see your changes, even if you have finished coding your solution in your local directory.

If you make changes to files after your push and want to share these changes, repeat the add, commit, push loop again to update the github server.

To recap, the git commit cycle is git add, git commit, git push. Don't forget to git push when you have completed an assignment.

You can review the basic git commands on the github help pages. Eventually, you should get in the habit of using git status to see if everything has been published, but we will talk about this more throughout the semester.

Remember to add, commit, push. You may commit and push as often as you like, and only the most recent push will be graded.