Chris Pollett> Old Classses >
CS154

( Print View )

Student Corner:
[Submit Sec1]
[Grades Sec1]

[Online Final-PDF]

[Online Midterm-PDF]

[Lecture Notes]
[Discussion Board]

Course Info:
[Texts & Links]
[Description]
[Course Outcomes]
[Outcomes Matrix]
[Course Schedule]
[Grading]
[Requirements/HW/Quizzes]
[Class Protocols]
[Exam Info]
[Regrades]
[University Policies]
[Announcements]

HW Assignments:
[Hw1] [Hw2] [Hw3]
[Hw4] [Hw5] [Quizzes]

Practice Exams:
[Midterm] [Final]

HW#1 --- last modified March 10 2020 23:45:03.

Solution set.

Due date: Feb 12

Files to be submitted:
  Hw1.zip

Purpose: To become more familiar with set theory and math notation, to be able to write simple proofs, to gain experience with the formal definition of automata and implementations of automata

Related Course Outcomes:

The main course outcomes covered by this assignment are:

CLO2 -- Construct deterministic and non-deterministic machines for various languages.

Description:

This homework consists of some exercises, a small coding assignment, and writing answers to a reading assignment. Your work for all portions of this assignment should be submitted in the file Hw1.zip. Within this file, you should have a readme.txt listing each team mate. You should put the exercises and the reading assignment answers in the file Hw1.pdf. You should put your code in the file DoubleA.java . Do not include the .class file.

Here are thee exercises I'd like you to do for this homework:

  1. Let `A = {1, 3, 7, 8, 9}` and `B = {2, 3, 4, 8}`. Write out fully the elements in each of the following sets (a) `A \cap B` (b) `B - A` (c) `S(A)` (d) `2^B` (e) `A times B`. Give the cardinality of each set.
  2. Write down all possible partitions of the set `{1,2,3,4,5}`.
  3. Construct using `^^`, `vv`, `not` gates a boolean function `{0, 1}^4 rightarrow {0, 1}` which returns `1` if and only if all but one of its inputs have the same value.
  4. Prove by induction that, `sum_(i=0)^n (3i^(2) +3i) = (n+1)^3 - (n + 1)`. Show carefully that this sum is `Theta(n^3)`.
  5. Draw a deterministic finite automata which accepts string over the alphabet `{a,b}` which don't contain the substring `aa`. So for example the strings: `epsilon`, `aba`, `\b\ba\b\ba` would be in this language. Then write down this automata formally using our 5-tuple notation.
  6. Argue using the pigeonhole principle, that any time your automata above accepts a string longer than some fixed length, it must repeat a state. For the automata you drew, what is this fixed length?

For the coding portion of the homework, I would like you to directly implement the finite automata you came up with in Exercise 5 as a java program DoubleA.java. Your program will be compile by the grader using an at most two years old version of Java from thhe command line using the command:

javac DoubleA.java

Your code should compile without errors, warning, notices, or deprecations. The grader will then run your program and test it on various srings over {a,b}. The grader will run the program by typing at a command prompt a line like:

java DoubleA some_string

Your program should output on a single line either YES or NO depending on whether some_string doesn't contain the string 'aa'. Here are some examples of what this might look like:

java DoubleA
YES
java DoubleA aa
NO
java DoubleA bab
YES
java DoubleA abbbbbbbba
YES
java DoubleA abbbaabbba
NO

For the reading assignment, I want you to look at one of the early papers on finite automata:

W. S. McCulloch and W.H. Pitts. A logical calculus of the ideas immanent in nervous activity. Bulletin of Mathematical Biophysics. Volume 5. pp. 115--133. 1943.

Find this paper. Briefly skim through it, write a half page summary, and answer the following questions:

  1. The system of logic and base theory used in the paper is not set theory. Where do the authors say it comes from?
  2. Where in the paper (page/paragraph) is something like a finite automata defined?
  3. In what other subject areas do you suppose this paper appears as one of the foundational papers?
Point Breakdown
Exercises (1pt each: 0 far from correct, 0.5pt partially correct, 1 fully correct) 6pts
Coding assignment: Program compiles (0.5pts). Directly implements the automata from the exercises using the techniques from class (0.5pts). Runs as described using command line arguments (0.5pts). Works on all grader test cases (0.5pts) 2pts
Reading assignment. Summary and three questions each 0.5pts 2pts
Total10pts