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]
|
CS154 Spring 2020Practice Midterm
Due to the coronavirus the midterm will be online and open book/internet. That said,
you will be on the honor system not to communicate with other members of the class or internet
community about problems on the test. I will give 24 hours from when I post the test to complete it.
If you have a correctly filed AEC accommodation and need more time please send me an email.
To study for the midterm I would suggest you:
- Know how to do (by heart) all the practice problems.
-
Go over your notes at least three times. Second and third time try to see how much you can remember from the first time.
-
Go over the homework problems.
-
Try to create your own problems similar to the ones I have given and solve them.
-
Skim the relevant sections from the book.
-
If you want to study in groups, at this point you are ready to quiz each other.
The practice midterm is below.
- Define the following set theory concepts: (a) one set is a subset of another (define using `in`), (b) ordered pair `(a,b)` (define as a set), (c) partition of sets.
- Prove: (a) the set of even numbers is countable. (b) `sum_{i=1}^n i^2 = Omega(n^3)`.
- The binary relation on pair integers `tilde` given by `(a, b)` `\tilde` `(c, d)` iff `a cdot d=c cdot b` is an equivalence relation.
- Given a graph `G=(V,E)` and two vertices `s, t in V`, give the algorithm from class to determine a path from `s` to `t` in `G` if it exists.
- (a) Draw a DFA for the language: {w | w has 010 as a substring}. (b) Write down your DFA formally as a 5-tuple. (c) Prove formally your machine accepts the string 10101.
- Show that the class of regular languages is closed under (a) intersection, (b) homomorphism.
- Explain how the DFA state minimization algorithm from class works. Give a concrete example of using it.
- Use the algorithms from class (a) to step-by-step convert the regular expression `(00 cup 11)^{\star}` to an NFA. (b) convert this NFA to a DFA (only need to show portion reachable from start state).
- Show step by step how the algorithm from class could determine directly from the NFA (no powerset construction) of the last problem whether 001101 was in the language or not.
- Prove {w| `w=xy` such that `x in {0,1}^\star`, `y \in {0}^{\star}` and `|x|=|y|` } is not regular.
|