Recent Forum Posts
From categories:
page »


After class last Thursday night Chad mentioned it would be nice for all of us to be able to keep up with our collective program progress. Dr. Asaithambi suggested Chad set up another wiki, but Chad is near the quota limit of twenty. Consequently, I plan to set one up for we few, we happy few, we band of CSSers (with apologies to Shakespeare).

This will entail another round of invitations. If you would like to be included, leave a reply to this thread, or send me an email, or let Chad know. You may also capture the carrier pigeon mentioned in the pigeonhole principle, attach a note to it and dispatch it hence. Another option is the put a note in a bottle, seal it, and throw it in the Big Sioux or the Missouri. I will not get those messages, but it makes a good story. I did not mention smoke signals because you would have to burn a haystack, and that excites the anger of the hay farmer that owns it.

You certainly may recruit those CSSers who have completed all or part of the program before this year.

So let me know if you would like an invitation.

Best regards,

Now I see it.

Re: Solution to #20 by Tom_TiahrtTom_Tiahrt, 30 Apr 2009 19:26

Actually, that's the first way I read it and then I convinced myself I was wrong. I think you're right Jason. You do only need to find one that works for satisfiability. Please disregard my previous post.

Re: Quiz 3 Number 21 by Becky JungmanBecky Jungman, 30 Apr 2009 19:18

Here is my impression on satisfiability.

If you can find a single combination of true/false values that satisfies the Boolean expression, then the expression is satisfiable. You only need one combination for the expression to be satisfiable.

In order to prove that a Boolean expression is unsatisfiable, you have to show that the expression is false for all possible true/false combinations.

I think I'm saying the opposite of what Becky is saying. Is my reasoning sound, or do I need more sleep? ;-)

Re: Quiz 3 Number 21 by jbshepjbshep, 30 Apr 2009 19:14

For i from 1 to 8 because s0 and s9 were checked already. In the example in the notes, they had 7 vertices or s0 through s6 and they did their for loop for i from 1 to 5.

Re: Solution to #20 by Becky JungmanBecky Jungman, 30 Apr 2009 19:09

I'm not sure that not arriving at a contradiction necessarily proves that the statement is satisfiable. In the notes it says that the only way to show satisfiability is to do an "exhaustive search of the truth values". In other words we should set up a truth table for the statement. I'm going to hope that if this is on the quiz it's not satisfiable, because that's much easier to show! :)

Re: Quiz 3 Number 21 by Becky JungmanBecky Jungman, 30 Apr 2009 18:39

Did you mean 1:8 or 2:9?

Re: Solution to #20 by Tom_TiahrtTom_Tiahrt, 30 Apr 2009 18:38

Becky says that she thinks we only need to check for $i = 1 :8$, since we have already checked the endpoints in steps (2) and (3).

Re: Solution to #20 by Chad BirgerChad Birger, 30 Apr 2009 18:01

Are we allowed to do a 3-argument merge? I don't see why not since merge is analogous to performing a set-union. However, if we are only given a 2-argument merge, we could replace step #6 with this:

6. N7 = merge(N4, N5)
7. N8 = merge(N6, N7)
8. detect(N8)


Re: solution to Problem 23 by jbshepjbshep, 30 Apr 2009 17:54

I have confirmation from the big guy that there will be no sticker model on the quiz!

Re: Other Topics by chaineschaines, 30 Apr 2009 17:25

If I understand the question (admittedly a questionable assumption on the question) you would need to modify steps three, four and five.

Three: $N \leftarrow E(N,s_6)$ becomes $N \leftarrow E(N,s_9)$

Four: $N \leftarrow (N,\leq 140)$ becomes $N \leftarrow (N,\leq 200)$

Five: for $i = 1$ to $5$ becomes for $i = 1$ to $10$

Re: Solution to #20 by Tom_TiahrtTom_Tiahrt, 30 Apr 2009 03:14

Will Sticker model be on the quiz? I know that we each have a problem from it on the Final, but are we expected to know that for the quiz?

Other Topics by Chad BirgerChad Birger, 30 Apr 2009 02:37

Has anyone finished this yet? If so, please post the steps. I am unsure if we can just modify the for loop parameters or if there is something trickier.

Solution to #20 by Chad BirgerChad Birger, 30 Apr 2009 02:36

Excellent Colte! Thanks for contributing.

Re: solution to Problem 23 by Tom_TiahrtTom_Tiahrt, 28 Apr 2009 16:31

part A

  1. Input(N0)
  2. N1=S(N0,1,1)
  3. N1prime=Sneg(N0,1,1)
  4. N2=s(N1prime,3,1)
  5. merg(N1,N2)=N3

That section takes care of (X1 V X3) now on to (~X1 V X2 V ~X3)

part B

  1. N4=S(N3,1,0) this gets ~X1
  2. N4prime=Sneg(N3,1,0)
  3. N5=S(N4prime,2,1) now we have X2
  4. N5prime=Sneg(N4prime,2,1)
  5. N6=(N5prime,3,0) now we have ~X3
  6. merg(N4,N5,N6)

A.2 = 111 101 110 100
A.3 = 011 010 001 000
A.4 = 011 001
A.5 = 111 101 110 100 011 001

B.1 = 011 001
B.2 = 111 101 110 100
B.3 = 111 110
B.4 = 101 100
B.5 = 100
B.6= 100 111 110 011 001

solution to Problem 23 by chaineschaines, 28 Apr 2009 03:29

Is the following Boolean expression satisfiable? Justify your answer.

\begin{align} x_1 \wedge (\neg \, x_1 \vee x_2 \vee x_3 \vee x_4) \wedge (\neg \, x_2 \vee \neg \, x_3) \wedge (( \neg \, x_1 \wedge \neg \, x_2) \vee (x_1 \wedge x_3) ) \end{align}

Dividing the expression into its sub-expression components:

\begin{align} x_1 \wedge \end{align}
\begin{align} (\neg \, x_1 \vee x_2 \vee x_3 \vee x_4) \wedge \end{align}
\begin{align} (\neg \, x_2 \vee \neg \, x_3) \wedge \end{align}
\begin{align} (( \neg \, x_1 \wedge \neg \, x_2) \vee \end{align}
\begin{align} (x_1 \wedge x_3) ) \end{align}

To be satisfiable, $x_1$ must be true, otherwise (2) is false and its AND would falsify the entire expression.

If $x_1$ is true, then $x_3$ must be true to make (6) true, because $x_1$ being true makes (5) false, and (6) must be true for the ((5) OR (6)) sub-expression to be true.

Given that $x_3$ must be true, $x_2$ must be false, or (4) would be false, rendering the entire expression false.

Having established that $x_3$ must be true for the entire expression to be true, (3) will be true when $x_3$ is true.

Therefore the above expression is satisfiable.

Quiz 3 Number 21 by Tom_TiahrtTom_Tiahrt, 26 Apr 2009 17:15
Chad BirgerChad Birger 25 Apr 2009 19:50
in discussion Exercises / Quiz 3 Study Guide » Answers

Here is what I got (so far):
1) What is a monomer?
Single small molecule.
What is a polymer?
A bunch of monomers together
What are monomers in a DNA called?

2) What are the ingredients of each monomer in a DNA?
Deoxyribnucleotides - consist of a sugar, a phosphate, and a nitrogeneous base

3) What are the two kinds of bases in a DNA?
purines and pyrimidines

4) Name the two purines and two pyrimidines that occur in a DNA.
Purines are Adenine and Guanine
Pyrimidines are Cytosine and Thymine

5) Show a simple representation of a nucleotide indicating the position of the phosphate group, the hydroxyl group, and the base.
Picture on page 9 of text given

6) What are the two different ways in which two nucleotides can link together?

  1. 5' phosphate can link to the 3' hydroxyl group of another to form a phosphodiester bond
  2. The base of one nucleotide interacts with the base of the other to form a hydrogen bond

7) Explain what is meant by Watson-Crick complementary.
A's bond to T's
C's bond to G's

8) What is the name of the technique used for measuring the length of a DNA molecule?
gel electrophoresis

9) What is the difference between annealing and denaturation?
Annealing is used for combining - fusing two single stranded molecules by complementary base pairing
Denaturation is used for separation - Heating DNA until it melts (two strands come apart)

10) What are enzymes?
Proteins that catalyze chemical reactions taking place in living cells.

11) What class of enzymes is used for lengthening the DNA molecule?

12) What are endonucleases?
Destroy internal phosphodiester bonds in the DNA molecule
What kind of DNA manipulation do they facilitate?
Cutting DNA

13) What are exonucleases?
Shortening DNA by removing nucleotides one at a time from the end of a molecule
What kind of DNA manipulation do they facilitate?
Shortening DNA

14) What is a ligation reaction?
Linking together DNA molecules
Which enzymes are useful for ligation?

15) What does the acronym PCR stand for?
Polymerase Chain Reaction
What role does PCR play in genetic engineering?
Multiplying DNA

16) Define the operations Merge, Amplify, Detect, and Separate that can be used to develop algorithms in DNA computing.

  • Merge - Given tubes $N_1$ and $N_2$, form their union $N_1 \cup N_2$
  • Amplify - Given tube $N$, produce two copies of it.
  • Detect - Given tube $N$, return true if $N$ contains at least one DNA strand.
  • Separate - Given a tube $N$ and a word $w$ over the alphabet {A,C,G,T}, produce two tubes $+(N,w)$ and $-(N,w)$.

17) Write a program to determine whether or not a given tube consists of strands where neither A nor G occurs:
(1) input$(N)$
(2) $N \leftarrow -(N,A)$
(3) $N \leftarrow -(N,G)$
(4) detect$(N)$

18) Write a program that extracts all strands containing A or G, but not both.
(1) input$(N)$
(2) amplify$(N)$ into $N_1$ and $N_2$
(3) $N_A \leftarrow +(N_1,A)$
(4) $N_A^{\prime} \leftarrow -(N_A,G)$
(5) $N_G \leftarrow +(N_2,G)$
(6) $N_G^{\prime} \leftarrow -(N_G,A)$
(7) merge$(N_A^{\prime}, N_G^{\prime})$

19) Define the operations position-separate and length-separate.
Position-Separate - Given a tube N and word w, produce the tube B(N,w) or E(N,w) consisting of all strands in N that begin (or end) with the word w.
Length-separate - Given a tube N and an integer n, produce the tube $(N, \leqn)$ consisting of all strands in $N$ with length less than or equal to n

Answers by Chad BirgerChad Birger, 25 Apr 2009 19:50

That should be:

There is no CSS 704 class scheduled for April 9th.

I missed the last 'd' in scheduled.

In case you are wondering, we do not have class April 9th, and our quiz will be held after we have covered the DNA computing material.

No CSS 704 class April 9 by Tom_TiahrtTom_Tiahrt, 08 Apr 2009 18:51

We will not have class this Thursday.

page »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License