**Anne Arundel
Community College**

**Discrete
Structures**

**Class:**** MW@19:00-20:15 in Math-102**

**Professor:** James
Freeman

**Office:**
Mathematics 231-I

**Office Hours:****
MW@16:00-17:00 & TTh@16:00-19:00**

**Phone:** (410)
777-2557

**Email:**
jsfreeman@aacc.edu

**Website:** http://ola4.aacc.edu/jsfreeman

**Course Description:**

This course introduces the student to some fundamental mathematical concepts and structures important for the theoretical areas of computer science. The topics will be selected from:

a) Logic, sets, relations, functions, operations and modular arithmetic;

b) Mathematical proof, including mathematical induction;

c) Counting, discrete probability and combinatorics;

d) Mathematical theories of graphs and trees;

e) Boolean algebra, logic gates, Karnaugh maps;

f) Models of computation and Turing Machines.

Course content will emphasize conceptual understanding and applications.

**Learning Objectives:**

Upon completion of this course, the student will be able to:

(i) Employ formal notations for logic, sets, sequences, summations and matrices;

(ii) Employ sequences and functions defined both explicitly and recursively;

(iii) Employ algebraic structures and methods, including modular arithmetic for encryption;

(iv) Construct direct and indirect proofs, including the use of induction;

(v) Solve counting problems using permutations and combinations;

(vi) Solve various graph theory logic and optimization problems;

(vii) Analyze and model computational problems using logic and algorithms.

**Text:
"Discrete Mathematics and Its
Applications"** (7thEd); by K.H. Rosen, McGraw-Hill(2012).

**Overview of the subject:**
http://mathworld.wolfram.com/DiscreteMathematics.html

**Other Course Material (available on my website)**:

Axioms, Algebra and Geometry; J. Freeman, AACC(2009).

SQL Relational Databases; J. Freeman, AACC(2009).

**Computer/Calculator:**
Some work on a computer using a programming language is optional in this course.
Maple, C, Shell, Fortran and/or COBOL will be used for classroom
demonstrations. Students may use any
language they choose - C++, C#, Java, VB, Perl, Python, etc.
Computers are available in both the Mathematics building and in the
library. A graphing calculator is
useful in the course - a TI-84+ is recommended.

**Suggested Further
Readings:**

**"Godel, Escher, Bach";** by D.R.
Hofstadter, Basic Books(1979)

**"Introduction to the Foundations of Mathematics";** by
R.L. Wilder, JW(1965).

**"Language, Truth and Logic";** A.J.Ayer, Penguin(1936)

**"Foundations of Projective Geometry";** by R.
Hartshorne, WAB(1967).

**"The Information: A History, A Theory, A Flood";**
James Gleick, Random House(2011)

**"Lectures on Computation";** by R.P. Feynman, Westview(1996).

**"The Art of Computer Programming";**
by Donald Knuth, A-W(1968, etc.)

**"A Relational Model of Data for Large
Shared Data Banks"**; E.F. Codd, CommACM(1970)

http://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf

**"A Mathematical Theory of Communication"**; by C.E.
Shannon, Bell Labs(1948).

http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html

**Attendance Policy:
**Regular class attendance is expected and will be recorded.
If you are absent, it is your responsibility to find out what occurred
with respect to both announcements and course work.
If you email me, I will respond with that information.
I will maintain an online version of this syllabus on my website with any changes in
dates or homework assignments. But
you should attend every class because even one absence means a lost opportunity
to learn.

**Class Activity:**
Prepare for class by reading the text (either before or after we cover the
material). Be sure to read the text - we
will not cover every topic in every chapter in class. If you do not understand
something, ask questions in class.
Ask questions even if it concerns material from a prior class or chapter.
Asking and answering questions is the main purpose of class.
During class we will review the major points in each chapter and solve
sample problems.

**Homework:**
Homework will consist of handouts and selected problems from the end of each chapter
section in the text. You are encouraged to do other problems for extra practice
and to ask questions about any problem (whether assigned or not) with which you have difficulty.
The homework will be collected and
graded. Late homework loses 10%
credit. Your homework problem
solutions should be neatly prepared (they need not be typed), with multiple
pages either stapled or otherwise bound together. Answers to the homework are in
the back of the book, so there is no reason for a wrong answer.
The homework will not be graded in detail, but will be reviewed for
completeness. **You must show your
work and not just give the answer.**
If you cannot do or do not understand a homework problem, ask about it in
class.
Do the
relevant homework as soon as possible after the material is covered in class to allow time for questions. Some homework may
optionally be done using
C, C++, Java, Maple or Excel.

**
Homework assignments will comprise 13% of your grade.**

**
(Notice:
**

**
Examinations: **There will be **three **chapter specific tests and a cumulative final exam.

**The three tests will comprise 57% of your grade - 19% each.**

**The final will comprise 30% of your grade.**

The tests may not be made up (without prior approval).
If you miss a test, the total possible points that the test was worth
will be added to the total possible points that the final is worth.
Thus, if you miss a test, your final exam will be worth a larger
proportion of your course grade. I give generous partial credit when I grade, but you must show your work neatly
to earn it. It is your
responsibility to show me what you know in a neat and orderly fashion.

**Grading Scale: **
90 - 100% A; 80-89% B; 70 - 79% C; 60 - 69% D; below 60% F.

**Additional Help:**
Do not hesitate to visit me during my office hours.
If my hours conflict with your free time, I will gladly arrange
additional times to meet with you. I
am in my office other times during the week so you can always stop by to see if
I am in.

**Academic Integrity:
**The Anne Arundel Community College Catalog states, "All students are
required to exhibit academic honesty in all academic exercises and assignments."
This includes cheating, fabrication, facilitating academic dishonesty, and
plagiarism. The instructor has the
right and obligation to impose a reasonable academic sanction including, but not
limited to, the following:

A) Assign a failing grade for the assignment;

B) Assign a grade reduction for the course;

C) Assign a failing grade for the course;

D) Assign an alternative learning assessment.

I will choose **A** for most situations involving academic
dishonesty. **Do not leave the classroom without permission during a test.****
**
**If you do, I will collect your test and grade it based upon what you have
already finished.** ** **

**Student Conduct: **
The Anne Arundel Community College Catalog states; "All students while engaged
in college activities shall comply with all college policies and procedures.
Students shall conduct themselves in accordance with accepted standards of
behavior, respect the rights of others, refrain from conduct or activity which
obstructs the work of the college and is damaging to the welfare of the college
community or the college." It continues to describe Acts of Misconduct.

**Cell Phones: **Place
cell phones OUT OF SIGHT during class. Cell phones visible during
class MAY be confiscated. If you must make or receive a call, I trust that you will
leave the room to do so.** Do not use your cell phone during a test - such use may be construed as
a form of academic dishonesty. **

**
Notice of Nondiscrimination:** AACC is an
equal opportunity, affirmative action, Title IX, ADA Title 504 compliant
institution. Call Disability Support Services, 410-777-2306 or Maryland Relay
711, 72 hours in advance to request most
accommodations. Requests for sign language interpreters, alternative format
books or assistive technology require 30 days' notice. For information on Anne Arundel Community College's
compliance and complaints concerning discrimination or harassment, call Kelly
Koermer, J.D., AACC's federal compliance officer, at 410-777-2607 or Maryland Relay
711.

**Course Schedule (All dates are tentative.)**

**Dates
Assignments**

**Jan 20 First Class**

**Jan 27 Chapter 6.1 homework due**

**Feb 10 Chapter 1 homework due
**

**Feb 23
Chapter 2 homework due (see also Chap 9.1)**

**Feb 29
Examination Chapters 1 & 2 ****
& 6.1
**

**Mar 09 Chapter
3 homework due**

**Apr 04 Chapter
4 homework due
**

**Apr 04 Examination Chapters 3 & 4
**

**Apr
20
Chapter 5,6,7 homework due **

**May 02
Chapter 9 homework due (SQL-Handout )
**

**May 02
Chapter 10 homework due **

**May 04
Examination Chapters 5 - 10 **

** Review and additional topics as
time allows**

**May 18 (Wed) Final Examination (17:30-19:30)**

**Jan 25**** ****Last day to drop with full refund**

**Apr 20**** ****Last day to
Withdraw
**

**Homework
Assignments ****(A
"*"ed problem means hard and important.)**

**Chapter 6 – Counting Basics **

**6.1: 1, 3,
17, 21, 39, 51, 55, 73 - Due the first week **

**Chapter 1 - Logic and Proofs1.1: 1−9 odd, 15,
17, 23, 29, 33, 48–50 1.2: 5, 9, 33, 38*, 39, 411.3: 3, 7, 9, 15, 25,
31, 39, 46* – 54* 1.4: 1, 3, 9, 27, 31, 39, 591.5: 1, 3, 7, 13, 39
1.6: 1, 3, 51.7: 1, 3, 5, 27, 38 Read 1.8:
Optional: 5, 7, 23, 32,
39-40Chapter 2 -
Sets, Functions, Sequences, Sums and Matrices2.1: 1, 3, 4, 11, 19, 21, 46,
47 2.2: 1, 9, 19, 27, 29, 35, 452.3: 1, 7, 15, 17, 19, 33, 35, 67
& Read 3.2
2.4: 1, 5, 7, 19, 27*, 28*, 35, 442.5: 1, 3, 11, 15, 27, 40* 2.6: 1, 3,
5, 17, 18, 19 (& Axioms handout)Chapter 3 - Algorithms3.1: 3, 9, 27, 47, 49 3.3: 1,
3, 25, 41Chapter 4 – Number Theory and Cryptology4.1: 1, 3, 5, 15,
17, 31 4.2: 1, 3, 5, 15, 17, 29, 35, 41
4.3: 1−13 odd, 33, 35
4.4: 1, 5, 17, 33, 374.5: 1, 3, 19, 33
4.6: 1, 3, 5, 25, 27 Chapter 5 - Induction and Recursion
5.1: 1, 3, 13, 19, 5.3: 1, 3, 5, 25, 35, 43, 49, 51 5.4: 1−5
odd, 13
Chapter 6 – Counting ( Chapter 8 − Advanced Counting)6.1: 1, 3,
17, 21, 39, 51, 55, 73 - Done the first week **

**6.2: 1, 3, 15 6.3: 4, 5, 6, 13, 21, 25,
31**

Chapter 7 - Discrete
Probability

7.1: 1−5 odd, 11, 13, 15, 17, 25, 38*, 39* 7.2: 1, 3, 5, 13,
19, 29, 39*

**7.3: Bayes TBDChapter 9 - Relations 9.1: 1−5
odd, 11, 13, 25, 29, 49 9.2: 1−9 odd,
19, 29 (& SQL handout)
9.5: 1, 3, 5, 19, 43, 57, 59 **

**9.3: 1−7 odd, 15, 23, 27
Chapter 10 - Graphs 10.1: 3−9, 19, 29 10.2: 1, 3, 7, 21, 3710.3:
5, 7, 9, 17, 55 10.4: 11, 3710.5: 1−5, 9, 21, 31, 33, 35 10.6: 1,
9, 27Chapter 11 – Trees (TBD)Chapter 12 – Boolean algebra (TBD)**

**12.1: 14–23
odd, 39
**

**12.3: 1−5, 9,
13 12.4: 1,
3, 5, 9, 11**

**Chapter 13 – Modeling Computation (TBD)**