Anne Arundel Community College

Discrete Structures

MAT250, Section 400 Spring 2016

 

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.  Do the relevant homework as soon as possible after the material is covered in class to allow time for questions.

 

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:  You cannot receive an "A" if you do not do the homework.)

 

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 (Axioms-Handout due anytime)

 

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 (see also Chap 10.1 & 11.1)

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 (Chapters 11,12&13?)

 

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 Proofs
1.1: 1−9 odd, 15, 17, 23, 29, 33, 4850                 1.2: 5, 9, 33, 38*, 39, 41
1.3: 3, 7, 9, 15, 25, 31, 39, 46* 54*                    1.4: 1, 3, 9, 27, 31, 39, 59
1.5: 1, 3, 7, 13, 39                                                  1.6: 1, 3, 5
1.7: 1, 3, 5, 27, 38                                        Read 1.8: Optional: 5, 7, 23, 32, 39-40

Chapter 2 - Sets, Functions, Sequences, Sums and Matrices
2.1: 1, 3, 4, 11, 19, 21, 46, 47                                2.2: 1, 9, 19, 27, 29, 35, 45
2.3: 1, 7, 15, 17, 19, 33, 35, 67 & Read 3.2          2.4: 1, 5, 7, 19, 27*, 28*, 35, 44
2.5: 1, 3, 11, 15, 27, 40*                                        2.6: 1, 3, 5, 17, 18, 19 (& Axioms handout)

Chapter 3 - Algorithms
3.1: 3, 9, 27, 47, 49                                          
3.3: 1, 3, 25, 41

Chapter 4 Number Theory and Cryptology
4.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, 37
4.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 TBD

Chapter 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, 37
10.3: 5, 7, 9, 17, 55                                             10.4: 11, 37
10.5: 1−5, 9, 21, 31, 33, 35                                 10.6: 1, 9, 27

Chapter 11 Trees (TBD)

Chapter 12 Boolean algebra (TBD)

12.1: 1423 odd, 39                                                  

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

Chapter 13 Modeling Computation (TBD)