Each homework will be graded on the scale 0-2: A few selected problems from each problem set will be graded for correctness (one point), and the remainder of the homework will not be graded for correctness but only for effort (one point).

Homework is to be submitted on the table in the front of the lecture room before the start of lecture.

Homework will not be accepted after lecture of the due date.

- Homework 1: Due
**Friday**of week 1, i.e. April 2.- 1.1: 10, 14, 20, 24(b)(c), 28(b)(d)(f), 44, 48, 62
- 1.2: 6, 8, 10(c)(d), 12(c)(d), 20, 30, 58

- Homework 2: Due
**Monday**of week 3, i.e. April 12.- 1.1: 60,64
- 1.3: 2,4,12,18[but restrict the domain to just integers 0,1, and 2],32,38,44,60
- 1.4: 4,10,12,20,26,28,38

- Homework 3: Due
**Monday**of week 4, i.e. April 19.- 1.5: 4 (b,c), 10(a,b,e,f), 14(a,c,d), 16(a,b,c), 18, 24
- 1.6: 6, 8 [Hint: what's the smallest perfect square greater than n^2?], 16 [state the type of proof you are giving], 18(a,b), 22 [state the type of proof you are giving], 28 [for the "only if" direction, note that m^2-n^2=(m+n)*(m-n)], 34 [state the exact step where there is a mistake and explain what was done wrong]

- Homework 4: Due
**Monday**of week 5, i.e. April 26.- Section 1.7 [These few exercises can take quite a bit of time: Think of them early! We will verify one of the latter three in homework verification...]: 4, 12, 22, 36
- Section 2.1 [These are very fast if you learn what sets are...]: 8, 14, 16, 18, 20, 22, 26, 28(a,b), 34,
- Section 2.2 [Same for these...]: 2, 4, 12, 14, 16(a,d,e), 18(c), 20, 30, 46, 48

- Homework 5: Due
**Monday**, May 10.- Section 2.3: 2, 4, 6, 12, 14, 16, 18, 26, 28, 32, 38, 68
- Section 8.1: 4, 6(a,b,e,g), 8, 24, 26 (read the text before exercise 24), 32, 34, 36, 54. Bonus questions: 46, 56.

- Homework 6: Due
**Wednesday**, May 19.- Section 8.2: 8, 12, 14, 18 ["components" here means "attributes"], 23, 26 [hint: consider first m=1]
- Section 8.3: 2(b), 6, 8(a,b) [skip the irreflexive property], 10(b,c), 12, 14(a,b,c), 18(a,c), 20(a,c), 32 [skip irreflexivity and asymmetricity], 36 [do just union, intersection, and composition]
- Section 8.5: 2, 10, 14, 16 [hint: this relation has something to do with rational numbers. What is it?], 21, 22, 24, 26, 28, 42, 44, 46, 56, 58
- Section 8.6: 2, 4, 6, 8, 10, 12, 16, 18, 22(a), 24, 32, 36

- Homework 7: Due
**Wednesday**, May 26.- Section 9.1: 2, 3-9, 12, 14, 16, 18, 20, 24, 28
- Section 9.2: 4, 8, 10, 12, 16, 18 [use pigeonhole principle], 22, 24, 26, 28, 46
- Section 9.3: 9, 10, 12, 28, 29
- Section 9.4: 2, 6, 12, 14, 22, 54, 56
- Section 9.6: 2, 4, 8(a,b), 12, 14, 15, 16, 21
- Bonus Problems: Section 9.6: 22, 24

- Topics for
**Quiz 7**: Here's a list of notions from each section in Chapter 9 divided by which notions I expect you to know for quiz 7 and which are optional and will not be tested.- Section 9.1. Included: Graph (Directed, Undirected, Simple), Examples and Applications: Influence Graph, Aquaintanceship Graph, Collaboration Graph, Web Graph, Precedence Graph, Roadmap Graph
- Section 9.1: Not Included:
Multipgraph, Mixed Graph, Pseudorgraph

- Section 9.2: Included: Adjacent vertexes, Isolated nodes, Initial and Terminal vertex of an edge, Degree of a vertex, In-degree and Out-degree of vertex, Special Graphs: K_n, C_n, W_n , Q_n, Bipartite Graph, Bipartition, K_{m,n}
- Section 9.2: Not included:
Pendant, Theorems 1,2,3,4 (They are good to understand but you
won't be tested on them)

- Section 9.3: Included: Adjacency matrix
- Section 9.3: Not included:
Incidence matrix, Isomorphisms between graphs.

- Section 9.4: Included: Path (in unidrected and directed graphs), Circuit, Cycle, Simple path, Connected graph, Connected Component of a graph, Strongly and Weakly Connected directed graphs, Strongly Connected Component of a graph.
- Section 9.4: Not included:
Walk, trail, cut vertex, cut edge, GSCC, connection between
paths and isomorphisms, theorem 8 on counting paths (This theorem
is very interesting: You should read it, but it won't be on a test)

- Section 9.5: Whole section not included.
However, you should have a look at what Euler and Hamiltonian paths are,
and how one of them has an easy algorithm and the other one does not.

- Section 9.6: Included: Weighted Graph, Shortes Path, Dijkstra's Algorithm
- Section 9.6: Not included: Travelling Salesman problem. This is a very cool problem you should know about, but it is not required reading for this course.

- Homework 8: Due last day of class,
**Friday**, June 4.- Section 11.1: 2, 6(c,d), 8(c,d), 10, 12, 20, 21 (but familiarize yourself with all the other laws), 24, 32 (one way to think about this problem is to think of the properties that must be satisfies by the bitstring that defines this boolean function on 3 variables)
- Section 11.2: 2, 4(c,d), 8, 10, 12, 14 (conclude that | is functionally complete).
- Section 11.3: 2, 4, 6, 8, 10, 12 (use the circuits of exercise 10 and 11 as black boxes, i.e. just like half-adder and full-adder cicruits are used in Figures 9 and 10), 16 (conclude that NOR is functionally complete).

- A list of what material in the chapter 12 is included in the final: e them on your own but we will not test you on them.
- Section 12.1: Not included. Grammars are very interesting and I hope you'll be curious to learn about them but you won't be tested on them in the final.
- Section 12.2:
- Included: Def.1, which defines an FSM (a.k.a. "FSA with output"), and all subsequent examples of FSM's
- Not included: Def.2, because it defines a non-standard notion of what it means for an FSM to recognize a language. A standard notion is of language recognition by an FSA (not FSM), which is defined in section 12.3. In class we covered them in the other direction: We introduced FSA's (section 12.3) on Wednesday and we'll briefly discuss FSM's (section 12.2) on Friday. Also not included is the alternative "Moore FSM" model: The Moore machine is an interesting variant of the FSM notion but for homework and final will stick with the notion of FSM defined in Def 1, which is called "Mealy FSM".

- Section 12.3:
- Included: Defs 1,2,3,4. Equivalence of FSA's. Examples 1-8.
- Not included: Non-Deterministic FSA's.

- Section 12.4: Not included. Regular Expressions, Regular Sets, and Kleene's Theorem. Regular Expressions are very useful, and they appear all over Computer Science, so I hope you take this opportunity to understand them, but you won't be tested on them in the final.

- Section 12.2: 1(a,b), 4, 6, 8 [let the output alphabet consists of just two symbols, namely 0 for "do not open the door right now" and 1 for "open the door"], 10, 15, 16 [you can also construct an FSA (see section 12.3) that accepts such strings and rejects others, instead of an FSM]
- Section 12.3: 4b, 8, 9, 10, 12, 13, 16-20, 24, 26, 28, 32, 34, 39-41.

Solutions: Sections 12.1-4.