Math 243: Discrete Mathematics in Computer Science - Spring 2014

In general, you will be graded not only on whether you get the correct answer but also on the clarity of your mathematical notation and reasoning.

Problem 2 from class on Wed 1/22: For each bike path problem from this handout (distributed in class 1/17), write down a graph G associated to the problem. Phrase each question from the handout as a question about G. It may be easiest to write down one graph G and then phrase each problem in terms of that graph.

You may attempt to answer the questions, but your homework assignment is only to clearly phrase the questions in terms of graph theory. Reference on graph theory: Ross and Wright, Chapter 6.

Problems 1 and 4 from the handout distributed on Friday 1/24 about degrees of graphs.

Draw all graphs with four edges without loops or vertices of degree 0.

Include an argument of why your list is complete.

Separate your list into two parts based on whether the graph is traceable (i.e. has a path that visits all edges once and only once).

Try to identify a property that all traceable graphs share, perhaps related to the degrees of vertices. (This type of guess is called a "conjecture").

Use Euler's theorem to answer the following:

(1) Prove that a finite connected graph with exactly two vertices of odd degree has an Euler path. One way to check your proof is to make sure it works for a variety of examples.

(2) Can a bug walk along the edges of a cubes without repeating any edges?

Problems 5, 7, and 8 from the "Bacon Numbers" activity passed out in class on Friday.

(1) Prove that in any tree, the number of edges is the number of vertices minus 1.

(2) If v and w are distinct vertices in a tree, then there is exactly 1 simple path from v to w. Describe how to construct this path. Be precise!

(1) Let T be a tree with n vertices. Suppose T has
   2 vertices of degree 4
   1 vertex of degree 3
   1 vertex of degree 2
All the other vertices of T are leaves. What values can n be?
Draw examples of T for each such n value.

(2) Let T be a tree with n vertices. Suppose T has
   2 vertices of degree 5
   3 vertices of degree 3
   2 vertex of degree 2
All the other vertices of T are leaves. What values can n be?
Draw examples of T for each such n value.

(1) Draw the complete graphs K_3, K_4, and K_5, and the complete bipartite graphs K_{2,3}, K_{3,3}, and K_{2,4}. Which appear to be planar? Give an informal justification for any non-planar graphs.

(2) Rewrite the Amtrak and Utility quesitons as graph theory questions using terminology from class (planarity, complete graph, complete bipartite graph, etc)

(3) How many edges do you have to remove from the Amtrak or Utility problems to produce a planar solution? (For instance, if you just allow one pair of stations not to be connected in the Amtrak problem, can you find a planar solution?)

(1) Prove that K_{3,3} is not planar

(2) Show that the average degree of vertices in a connected, planar graph with at least 3 vertices is strictly less than 6. The average degree of a vertex in a graph G is defined as the total degree of G divided by the number of vertices in G.

In class, we saw a theorem that said if a graph G has no loops or repeated edges, at least three vertices, and condition (a), (b) or (c) holds, then G is Hamiltonian. You can find the statements of (a), (b) and (c) in Theorems 1, 2, 3, repsectively in section 6.5 of Ross and Wright.

(1) Find an example of a graph that satisfies the hypothesis of the theorem with criterion (a). Explain why your example meets criterion (a) and explain why the graph is Hamiltonian.

(2) Find an example of a graph that satisfies the hypothesis of the theorem with criterion (b). Explain why your example meets criterion (b) and explain why the graph is Hamiltonian.

(3) Find an example of a graph that satisfies the hypothesis of the theorem with criterion (c). Explain why your example meets criterion (c) and explain why the graph is Hamiltonian.

(4) Find an example of a graph that has no loops or repeated edges, at least three vertices, and is Hamiltonian but does not satisfy ANY of the three criteria (a), (b), (c).

Write down at least four questions related to the material that you think are test-type questions. At least one should be a question that your group can't confidently answer.

In class, each group will write one or more question from your list on the board and we will use this to guide a review for the test.

You still have to submit your questions written up on one page like any other homework assignment. It will be graded based on effort. If you explain why you chose the problems you did, you will get full credit. If you seem to have put little thought into your chosen questions, you will have points taken off.

The test will cover everything we have done so far in class. For reference, you can look at Roos and Wright Chapter 6, excluding section 6.4 which we did not cover.

Focus on memorizing the definitions and theorems we have learned. Try to re-do homework problems on your own.

The test will be two pages. The first page will be similar in style to the quiz. The second page will be short answer questions.
 

Hammack Section 1.1 # 8, 22, 38, 50

Hammack Section 1.2 # 4, 6, 10, 12, 14

Hammack Section 1.3 # 2, 4, 10, 16

Hammack Section 1.4 # 12, 14, 16 and Section 1.5 # 6, 10

Hammack Section 3.1 # 2, 4, 8

Hammack Section 3.2 # 8 and Section 3.3 # 14

Hammack Section 3.3 # 10, 12 and Section 3.4 # 4, 6

Hammack Section 11.1 # 2, 6, 8

(1) Describe all possible equivalence relationships on the set {a,b,c}. It will help to think about the equivalence classes and/or the corresponding arrow diagram / graph for each possible relationship

(2) Define the relation R on the integers by: xRy means x-y is even (zero counts as even). Show that R is an equivalence relation on the integers. Then describe the equivalence classes of R

(3) Hammack Section 11.2 # 4

(1) Which, if any, of these integers: 80, 103, -29, -122, is equivalent to 5 modulo 17?

(2) Hammack Section 11.4 # 4, 5, 6

Write down at least four questions related to the material that you think are test-type questions. At least one should be a question that your group can't confidently answer.

In class, each group will write one or more question from your list on the board and we will use this to guide a review for the test.

You still have to submit your questions written up on one page like any other homework assignment. It will be graded based on effort. If you explain why you chose the problems you did, you will get full credit. If you seem to have put little thought into your chosen questions, you will have points taken off.

The test will cover everything we have done in class since Test 1. This includes Sections 1.1-1.5, 3.1-3.5, and 11.1-11.4 from Hammack.

Focus on memorizing the definitions and theorems we have learned. Try to re-do homework problems on your own.

The test will be two pages. The first page will be similar in style to the quiz. The second page will be short answer questions.
 

Using only the symbols P, Q, ∼, ∨, ∧, we can generate statements with 16 possible truth tables. We came up examples for 10 of these in class (4 that looked like ...∨..., 4 that looked like ...∧..., and examples for all true and all false). Find statements that have truth tables for the 6 examples we didn't already discuss.
 

Hammack Section 2.2 # 2, 10 and Section 2.3 # 2, 6, 10, 12

Hammack Section 2.5 # 2, 8, 10 and Section 2.6 # 10, 12

Hammack Section 2.7 # 2, 4, 6, 8

Calculators are NOT allowed (and wouldn't help anyways!) Focus on memorizing the definitions we have learned. A good way to study is to do odd-numbered problems in the textbook and check your answers in the back.
 

Write out line-by-line proofs of the following arguments, like we did in class. Justify each step with "premise", "modus ponens", "modus tollens", or "simple inference", and indicate the previous lines in the proof that pertain (e.g. "Modus ponens, using the lines 3 and 5" or "Simple inference from lines 2 and 6").

Argument I:
1) ¬ A ⇒ (C ∧ D)
2) A ⇒ B
3) ¬ B
---------
∴ C

Argument II:
1) ¬(P ∨ Q) ⇒ R
2) ¬ P
3) ¬ R
---------
∴ Q

Argument III:
1) X ∧ ¬ X
---------
∴ Y

In class, I wrote three statements on the board A., B., C., which are exercises 2, 10, and 8, respectively, from Hammack Chapter 10 (page 167). For each of these, you should

1. Write out what the statement S_n means.
2. Prove S₁.
3. State the inductive hypothesis (i.e. S_k)
4. State what you need to prove (i.e. S_k+1)

In case it was not clear, do not just write "S_k" for part 3 or "S_k+1" for part 4, actually write out what each means in the context of the problem.

ALSO, choose one of these problems and write out a complete proof by induction, which includes an actual argument of why S_k implies S_k+1.

Prove, using mathematical induction: for any natural number n>3, the following inequalities hold: n< 2ⁿ and 2ⁿ< n!

Write down at least four questions related to the material that you think are test-type questions. At least one should be a question that your group can't confidently answer.

In class, each group will write one or more question from your list on the board and we will use this to guide a review for the test.

You still have to submit your questions written up on one page like any other homework assignment. It will be graded based on effort. If you explain why you chose the problems you did, you will get full credit. If you seem to have put little thought into your chosen questions, you will have points taken off.

The test will cover everything we have done in class since Test 2. This includes Chapters 2 and 10 from Hammack.

Try to re-do homework problems on your own, along with similar questions from the book.

The test will be two pages, similar in style to the previous tests.
 

*** Every student must do this assignment - not just one per group! ***

Write down at least three questions related to the material that you think are test-type questions. At least one should be a question that you can't confidently answer.

In class, you will spend some time with your groups discussing the questions that you have brought. Each group will select one or more questions to pose to the class.

You will turn in your list of questions at the end of class. This is the last homework assignment!

The final exam is scheduled to be from 1-3pm on Monday May 12 in our regular classroom (Psych 204).

The exam will be cumulative meaning it covers everything we discussed in the course. Standalone calculators are allowed but cel phones, tablets, notes, books, etc. are not allowed.

The exam is three pages front and back on three different sheets (white, yellow, and green). Be sure to write your name on the front and back of each sheet or I won't be able to grade it.

Bring your CatCard or other form of ID to the exam.

As with any exam, it always helps to eat a good meal before the test.