CMPS 2120 Discrete Structures

Eddie Rangel
Office: Sci III 336
Office Hours: by appointment
Email: eddie@cs.csubak.edu
Course web site: http://www.cs.csubak.edu/~eddie/cmps2120-s19/index.html
Lecture
Course meets in Sci III room 315
T 4:00pm - 5:15pm
Th 4:00pm - 5:15pm
Laboratory
Course meets in Sci III room 311
F 4:00pm - 6:30pm

Catalog Description
Discrete structures and applications in computer science. Provides an introduction to proof techniques, propositional and predicate logic, functions, relations, sets, big-oh notation, counting techniques, summations, recursive definitions, recurrence relations, discrete probability and simple circuit logic. CMPS 2010 or CMPS 2020 with a grade of C- or better; MATH 1040 or MATH 1050

This course covers the following ACM/IEEE Body of Knowledge student learning outcomes:

CC-DS: Discrete Structures
CC-AL: Algorithms and Complexity
CE-DSC Discrete Structures

The course maps to the following program/student outcomes for Computer Science (CAC/ABET) and Computer Engineering (EAC/ABET):

(CAC PIa5, EAC PIa5): Use discrete mathematics techniques and algorithms.
Assessed by question on mid term and/or final exam.

Attendance:
It is recommended that you attend every class session. Roll is taken during labs. Some or all lab assignments will require attendance for full credit.

Lecture Topics and Rough Schedule

propositional logic and logical connectives
truth tables and logical equivalences
converse, inverse, contrapositive
o normal forms (conjunctive and disjunctive)
week 1
predicate logic with single and nested quantifiers
predicate logic operations
week 2
use of inference rules to analyze arguments
syllogisms and fallacies
week 3
the structure of formal proofs
direct proof, proof by counter example
proof by contradiction, proof by cases
week 4
functions (surjections, injections, inverses, composition)
sequences & summations
week 5
sets (power sets, Venn diagrams and tables, Cartesian product)
set operations (complement, union, intersection, difference)
cardinality and countability
week 6
algorithms and algorithm analysis
function growth & big-oh notation
week 7
integer division, modulo
primes and greatest common divisor
week 8
positional number systems
binary, octal, hexadecimal conversions and operations
week 9
standard strong and structural induction
proving recursive algorithms by induction
week 10
basic combinatorics
sum and product rule, rule of falling powers
inclusion/exclusion and pigeonhole principles
permutations and combinations
binomial coefficients and Pascal's triangle
week 11
introduction to discrete probability
complements and unions of events
week 12
properaties of relations (reflexivity, symmetry, transitivity)
relation composition
week 13
recursive definitions
solving recurrence relations
week 14
Boolean circuits
logic gates and logic diagrams
week 15

Estimated ABET Category Content
Math and Basic Sciences: 3 Credit Hours


View the calendar on the course website to see the order in which these topics will be presented.

Grading Policy:

Homework...........  10 points x 10  100  20%
Labs...............  10 points x 10  100  20%
Quizzes............  10 points x 10  100  20%
Mid Term Exam...... 100 points x  1  100  20%
Final Exam......... 100 points x  1  100  20%
                                    ---- 
Total points possible............... 500

The overall distribution of scoring is reflected above.
The number of assignments may change slightly.
Letter grade will be based on percentage of total possible. 
A 93%
A- 90%
B+ 87%
B 83%
B- 80%
C+ 77%
C 73%
C- 70%
D+ 67%
D 63%
D- 60%
F 0%
Scores will be posted on the course website during the quarter.

Labs
Lab assignments ask you to write some assembly language programs in class. There will usually be a brief lecture at the beginning of each lab session. Roll will be taken during lab. 20% of the lab grade is based on attendance.

Lab Submission
All lab files due should be located in your designated folder on Sleipnir.
This area on the Sleipnir server will be set up for you during the 1st week of class.
Instructions will be gived during the course to help you submit your assignments correctly.

Homework
Homework assignments are posted on our web page. Please work out the problems on paper with a pencil and eraser. Homeworks are due on Fridays just prior to the weekly quiz.

Late Policy
Late assignments will not be accepted.

Final Exam
The final exam will be given during finals week, and be similar to the quizzes given during the quarter.

Individual Work Policy
All work done in this course is individual work.
Sharing of code is not acceptable.
Possession of code written by other students in not acceptable.
Copying another student's work is plagiarism.
Copying answers or source code from the Internet is also plagiarism.
Asking a tutor or another person to do your work for you is cheating.

Do your own work please.
If you are struggling to learn the material, then do the following:
1. Complete all the reading assignments.
2. Ask the tutors some specific questions about what you're stuck on.
3. Come to every class session.
4. Practice your programming every day.
5. Contact the instructor for help.


note: This syllabus could be amended during the semester.