In addition to learning Theory of Computation concepts, we will be using four technologies this semester: piazza, python, $\LaTeX$, and git. One of the goals of this lab is to familiarize yourself with these tools. Piazza is an online discussion forum. You can post questions publicly to the class, anonymously to the class, or privately to the instructor. Feel free to post questions about the lecture material, or ask for clarification of homework questions. Please do not post solutions to homework questions or completed lab assignments publicly. If you are unsure, you can post the message privately and I may choose to anonymously repost some parts of the post as a public announcement if I feel other students may likely have the same question.

One nice feature of Piazza is that you can embed syntax-highlighted code by enclosing code between <pre></pre> tags, or $\LaTeX$ expressions by enclosing the formula between ${\tt $$\ $$}$ tags.

Instead of using update/handin to submit labs/homework, you will be using git–a distributed version control system. The distributed part is nice since it allows you to share code with me, and version control, because, well, it comes with git. We won't be using that part too heavily.

I have semi-automated the most annoying parts of the initial setup.

~adanner/public/bin/init46

cd cs46
git status
git add homework/wk1/hw01.tex
git add labs/wk1/power.py
git commit -m "my first commit"
git push

The equivalent to handin is git push, but push only pushed things that have been committed and commit only commits things that have been added. You should only submit source code. Do not submit files that can be autogenerated/compiled. I have set up a .gitignore file to ignore the most common auto-generated files for this course, but feel to add to this list if needed. Use git status to determine if you need to do something

$ git status
# On branch master
# Untracked files:
#   (use "git add ..." to include in what will be committed)
#
#	homework

$ git add homework/wk1/hw01.tex

$ git status
# On branch master
# Changes to be committed:
#   (use "git reset HEAD <<file>..." to unstage)
#
...

$ git commit -m "msg"

$ git status
# On branch master
# Your branch is ahead of 'local/master' by 1 commit.
#

$ git push

$ git status
# On branch master
nothing to commit (working directory clean)

The cs46/examples folder links to a public folder where I will occasionally post examples, homeworks, or starting point code for lab. The init script has already copied over stuff for this week, and in the future we will copy additional files out of this directory.

If you love editors, math, and compiling things, you'll love $\LaTeX$, a compiled document format for typsetting math. I will post homeworks in .tex format. You can compile this to pdf using the command pdflatex hw01.tex and view the pdf with evince. The homework writeup will usually contain examples of the types of formulas you will need to use in your solution, and you can just modify the writeup to contain your solutions. If you need to include figures, you can feel free to draw them on a separate sheet, or I can write up some notes on how to use inkscape or import images into $\LaTeX$. Here is some sample output for the (non-$\LaTeX$) programming part of the lab

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

$  python power.py 1

''
'a'

Your algorithm should run in $O(2^n)$ time. That may sound terrible, but recall that the size of the power set of $n$ elements is $2^n$, so you can't really make it faster and still display all the elements. Also, $n < 26$ 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^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: ", 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)

Home Page

Last updated: Tuesday, September 22, 2020 at 09:07:44 AM