ICS 6B - Boolean Algebra & Logic - Spring 2010

Homework assignments

• 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
  Solutions: Section 1.1 and Section 1.2
  
  
• 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
  Solutions: Section 1.3 and Section 1.4
  
  
• 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]
  Solutions: Section 1.5 and Section 1.6
  
  
• 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
  Solutions: Section 1.7 , Section 2.1 and Section 2.2
  
  
• 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.
  Solutions: Section 2.3 , Section 8.1 page 1, Section 8.1 page 2, Section 8.1 page 3, Section 8.1 page 4, Section 8.1 page 5, Section 8.1 page 6
  
  
• 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
  Solutions: Section 8.2-6 (10MB).
  
  
• 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
  Solutions: Section 9 (8MB).
  
  
• 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).
  Solutions: Sections 11.1-3.
  
  
• 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.