## Discrete Structures Fall 2007 - WEEKS 1 THRU 7 Graduate Teaching Assistant help hours for CS I, CS II, CS III and Discrete Structures. Mike Volz and Minal Tol are the TAs. How to prepare and be more effective at getting help.

Textbook web site at www.wiley.com publishers.

The Flash Games, Animations and Applets that accompany the textbook.

Week Dates Topics Homework or Quizzes
1 08/21-08/23
• The Truth Tables interactive practice application. (Hooray for Flash).

• The Logically Equivalent Propositions Flash application. Try it out.

• Try the Draw This!! puzzle/game that is covered in our textbook.

• The Josephus Game problem will be covered in some depth on Tuesday in class #3.

• The Binary, Base 2 number system. F and T or false and true can be expressed as 0 and 1, the 2 binary digits, also known at bits. With 8 bits, we can represent 256 things. With 10 bits we can represent 1,024 things. Propositional Logic ideas such as AND and OR and NOT are actually part of the electronic hardware components of computers. AND gates, OR gates, NOT gates, NAND gates, and NOR gates were mentioned in class.

• Another nice applet for Playing with and looking for Patterns and Strategies with the Josephus game.

# Textbook is in: What to read and do for 08/28/Tuesday.

Textbooks and online practice assignment using Flash applications to practice AND, OR, NOT, Truth Tables, Implications, and Logical Equivalence. Review of first class.
Read section 1.3 if you have the textbook. Do the online practice activities discussed in the above email note is the higher priority for everyone, until the textbooks are in.
Email note: Read page one of U Vic propositional logic summary. This will be handed out in class on Thursday, 08/23.

The U Vic PDF 5 page summary file.

### Homework Assignment is here, so do some of the suggested tasks. It will NOT be collected. Just review, practice, rewrite notes, study handouts and practice with the web resources.

2 08/28-08/30
• 88DCFF as in RRGGBB: RBG Hexadecimal Chart. Base 16 and R=Red, G=Green and B=Blue for RGB graphics.
• Thinking Hexadecimally. Color charts for web pages and why FF = 255 and why FF00FF would be Purple color. Base 16.
Floors, Logarithms, Where to stand to be the last standing, binary two bit blues: The Josephus Problem and how to win the game by choosing the right place to stand.

More Josephus and binary links.

3 09/04-09/06
```HOMEWORK ONE due Tuesday 09/04
Problems    Page #
--------    ------
4, 5b, 5d      37       4, 5B, 5D
9, 11b, 11c    38       9, 11B, 11C

16. What is 379 in binary?
Solve it BOTH WAYS and SHOW YOUR WORK.

18.  What is the binary number 101101110111 in decimal (base ten)?
```

### Read section 1.2 Number Puzzles and Sequences Read section 1.5 Implications

Recursion using bc calculator programming language. We will relate this to section 1.2 and recursive formulas (RF). Not to be confused with closed formulas (CF).
4 09/11-09/13

### Homework #2 Assignment and Suggestions, with a comment about 1+2+ ... + 100 and Gauss.

Predicate Logic example with Universal and Existential Quantifiers. To be discussed on 9/18/Tuesday. If you like Corvettes, or Bees, or Flowers or Porsches, or brothers and sisters (aka Siblings), you will like these examples.
HW #2 due on Tuesday 9/11
The Island of Knight and Knaves where Knights always tell the truth and Knaves always lie. Handout from 9/13/Thursday class.
5 09/18-09/20 HW #3 due on Tuesday
Read chapter 2, section 1 Proofs about Numbers are the focus. Even and Odd numbers. Direct and Indirect proof techniques for an implication.
Every positive integer greater than 1 is either PRIME or can be expressed as a PRODUCT OF PRIMES: 1 through 50 expressed only using the PRIME number building blocks: Prime numbers. See page 88 of textbook for Definition of PRIME numbers.
```Think about how you would prove the following:

if (x divides y) and (y divides z) then (x divides z)

or using | as our divides symbol, restated, it is

prove the following implication about the integers,
for all x, y and z

( (x | y) and (y | z) ) ---------------> (x | z)

P  --------------------------->   Q

Try to prove it by direct proof, like we did in class on 9/18.

Remember, x divides y means there exists some integer p such that
y = px

------------------------------------------
a | b means that b = ka for some integer k
------------------------------------------
```

### HW #3 due: Pages 65-67 Problems 1B, 3, 6, 25B, 25D, 25E Due on Tuesday, 09/18

6 09/25-09/27 Inductive Proofs: Read 2.3 Mathematical Induction

HW and Exam email note.

1. Try the Inductive Proof textbook online exercise (Flash player). Note that (n(n + 1)) / 2 can be written as:
```  2
n  +  n       n (n + 1)
----------  = -------------
2               2
```
2. Proof practice from the textbook web site.

3. The Proof Scrambler is excellent practice also.

.. Which card will be facing the opposite direction of the other cards?
1. HCDs is how they started.
2. CDsH might be how they look if you moved 3 cards to the bottom.
3. CDhS would be how they look after you flipped the top two cards over.
7 10/02-10/04

# First Exam: TEST ONE THURSDAY 10/04 Helpful Outline/Study Guide of topics on test one.

DO PROBLEMS EFFECTIVELY. How to study effectively for math exams.
Discrete Structures Curriculum 2001 discussion by ACM/IEEE Ironman Draft.