Johnson County Community College
Course Syllabus
Computing Sciences & Information Technology (CSIT)
CS 211: Discrete Structures II
Fall 2018


 

Course Information

Class:
Discrete Structures II
Section:
001
CRN:
82502
Sessions:
T/R 11:00 am - 12:15 pm
Location:
SCI 124
Days:
08/21/18-12/16/18
Final Exam
Tuesday, 11:00 am - 12:50 pm
Course type:
F2F
Prerequisites:
CS 210
Credits:
3
Instructor:
Rachel Singh
Catalog link:
Course description:
Upon successful completion of this course, the student should be able to use fundamental discrete mathematics as it relates to computers and computer applications. The student will experiment with a variety of discrete mathematical topics. The course will include fundamental mathematical principles, combinatorial analysis, mathematical reasoning, graphs and trees, and Boolean logic circuits. 3 hrs. lecture/wk.

 

Class supplies

Textbook

Title:
Discrete Mathematics: Mathematical Reasoning and Proof with Puzzles, Patterns, and Games, 1st ed
Author:
Douglas E. Ensley, J. Winston Crawley
Publisher:
Wiley
ISBN-13:
978-0471763802
Cover:

(There are two different covers, don't worry!)

A means to digitize homework

Homework and exercises will be turned in digitally. This means you need one of the following:

  • The Canvas app - take photos of your work and turn it in via the app
  • A scanner - scan your work and turn it in via the Canvas website
  • A word processor with math symbols - type out your work and turn it in via the Canvas website

A programming language

Throughout the semester we will have small programming assignments - you are able to use any programming language that you're comfortable with. The instructions are very step-by-step and general, so it's more about learning how a program works than how to code in a specific language.


 

Instructor info

Instructor:
Rachel Singh
Email:
rsingh13@jccc.edu
Cell:
(913) 999-8271
About:
I'm currently an adjunct instructor at JCCC, and I am starting the Masters in Computer Science program at UMKC in Fall 2018. I've taught both as an adjunct and full time at JCCC since 2016, and prior to teaching I worked in web and software development with various languages. I currently have an indie game startup as well.

 

Assessment breakdown

Each assignment type has a corresponding weight. Each assignment of that type are of equal weight to each other (i.e., every lab is worth the same amount)

Point breakdown

Exercises
Weight: 20%
Approximate count: 16
In-class exercises are done as a group and meant to introduce you to a new topic.

Quizzes
Weight: 15%
Approximate count: 16
Weekly homework quizzes to be done on Canvas to review.

Textbook Homework
Weight: 15%
Approximate count: 16
Problems are assigned from the textbook, with the answers available in the back of the book. Grade for completion is given.

Exams
Weight: 50%
Approximate count: 3
Exams given will have questions that are similar to exercises and homework.

Optional final exam: The final exam is optional. Students who miss an exam, or score poorly on an exam, have the option to re-take one exam to make up those points. A higher score on the final will replace the score on the original exam. Questions will be of the same type, but not exactly the same as the original exam.

Letter grades

A: 89.5% - 100%
B: 79.5% - 89.5%
C: 69.5% - 79.5%
D: 59.5% - 69.5%
F: 0% - 59.5%

 

Course format

Lectures: At the beginning of class there will be a short lecture to introduce the new topics and work some examples.

Exercises: During each class period, groups of students will work on an Exercise together. The exercise give students a chance to work on simple problems for the new topics to get acquainted with the ideas. Each group will turn in one document, and receive the same grade.

Homework: Weekly homework problems will be assigned out of the textbook. Generally, these problems will have the solutions in the back of the book. Students are encouraged to check their work. Grade for the textbook homework is based upon completion, and will not be individually graded for correctness.

Quizzes: Weekly quizzes will be available on Canvas. These give you more chance to practice the topics, with the ability to check your work.

Chapter projects: Once finished with each chapter, we will have a small programming project, applying what we've learned. Since this isn't a programming course, the emphasis is more on writing the program than giving you a challenging assignment.

Exams: We will have one exam at the end of each chapter with questions similar to the homework, exercises, and quiz problems.


 

Course policies

Communication

Communication in this class is important. If you're having trouble, or will need to make up an exam, or have a question on how the class works, please let me know. If I don't respond right away, you might need to follow up via another medium (e.g., email and in class) to ensure that I saw your message.

The best way to get ahold of me is to email me (through JCCC email or through Canvas), or send me a text message (I don't usually answer phone numbers that I don't know).

Email: rsingh13@jccc.edu
Phone: (913) 999-8271


Absenses

I only take attendance during the first couple weeks of class, as per JCCC policy. Grade is not tied to your attendance.

If you're going to be absent from class for an extended period of time, please let me know so I know that you're still part of the class. If you have to miss part of a class period or one class period - that's fine. If you have questions about what we covered in class, you can check the class webpage or email me.

Group assignments

In-class exercises are expected to be done in groups, and homework can also be done collaboratively. Exams must be done solor.



Assignments

All assignments must be turned in via Canvas, except exams. Each assignment has a place in Canvas where you can either upload files. You can download the Canvas app and take photos of your work to upload it, or scan your work, or type out your work.


Late assignments

Assignments should be turned in by the due date. I will not accept late assignments - it delays the grading process.


Make-up assignments and make-up exams

If you're going to need to take a make-up exam, you must let me know prior to the exam. I will not give make-up exams after the exam has been given, if I haven't been notified ahead of time.

For other assignments, everything you need is online so you should be able to work on the assignments and turn them in by the due date.


Getting help

There are many resources available to help you learn programming. Make sure you abide by academic honesty policies. Some available resources are...

Instructor: If you need help with an assignment, I can come to campus to meet up and help with them, or answer questions via email, or during/before/after class.

Tutor: JCCC has a CS tutor who is available during certain times in the RC 3rd floor computer lab.

Internet: There are also many resources available on the internet to help out with any topic you may run into; these topics are not unique to our class. Feel free to review any content available online, but remember to adhere by academic honesty policy. In particular, make sure to not plagiarize other peoples' work and pass it off as your own. For assignments that are intended to be solo-work, you should not be receiving help from outside sources for these assignments.

Classmates: Sometimes your classmates can be a good resource for figuring out problems. Brainstorming is a great idea, and sometimes your peers can direct you to resources that helped them understand the content. However, remember to adhere by academic honesty policy. Do not plagiarize anybody else's work, and do not give your work to other people for them to copy off of (even if they just say it's for them to "check their work"). If you are unsure if something counts as academic dishonesty, ask the instructor, or err on the side of caution.


Grade feedback

Points for homework will be given based on completion; you are expected to check your own work in the back of the book.

In-class exercises will be graded for correctness so you can see what work your group did correctly and incorrectly.

Questions on exams will have a weight associated with it, and you can score 0, 1, 2, 3, or 4 out of 4 points. The exam front page will explain the grading method further.


Academic Honesty

At JCCC, we are required to report cases of academic dishonesty. It can be difficult to define what exactly counts as academic dishonesty, but JCCC has descriptions in their student handbook. In general, you should avoid...

Plagiarism: This is passing off somebody else's work as your own. Even modified ("paraphrased") work can be considered plagiarism if you are simply restating somebody else's work as your own without giving credit. In programming, this most commonly occurs as students copying program code from each other - either partially, or the entire program. Unless stated otherwise, assignments are assumed to be solo-work and should be reflecting the knowledge of the individual student.

Do not ask other students for their code, and do not give your code to another student.

Commonly, one student might ask another to see their code in order to "check it against their own", but actually just turns in the other students' code as their own. In this case, both students receive a score of 0 on the assignment and both must be reported.

Unapproved materials: The usage of resources and materials on assignments and exams that were not previously approved by the instructor also counts as academic dishonesty. For example, bringing in extra notes to an exam to reference. Any student reasonably suspected of cheating will not be allowed to complete the exam, be given a score of 0, and be reported.


Instructor objectives

  • I will try to provide as many resources as are needed for students to do well in this course.
  • I will make sure students have what they need prior to being assessed on a topic.
  • I will treat all students with respect.
  • I will be patient and open to any questions for all students.
  • I am available for questions, whether about class content, the software development industry, or general advice.
  • I will advocate for students.
  • I will try to return graded work in a timely manner.
  • I will try to provide grading breakdowns to help students understand how they earned the grade they receive on assignments.
  • I will try to respond to all student contact (email, phone, etc.) in a timely manner, within 24 hours.

Expectations of students

  • Students are responsible for knowing what resources they need.
  • Students are responsible for coming to class as-needed, and to let the instructor know what they need if they miss a class.
  • Students are responsible for doing their own work and making sure they turn in their work on time.
  • Students are responsible for abiding by the JCCC and course Academic Honesty policies and to avoid all cheating, plagiarism, and so on.

 

Tentative schedule

Week Days Topics In class Homework Notes
1

Tue, Aug 21

Thu, Aug 23

  • Chapter 7.1: Graph Theory
  • Chapter 7.2: Proofs about Graphs and Trees

Lectures:

Exercises:

Homework:

Quizzes:

Due Friday:

  • Exercise 7.1
  • Exercise 7.2
2

Tue, Aug 28

Thu, Aug 30

  • Chapter 7.3: Isomorphism and Planarity
  • Chapter 7.4: Connections to Matrices and Relations

Lectures:

Exercises:

Homework:

Quizzes:

Due Monday:

  • Quiz 7.1
  • Quiz 7.2

Due Friday:

  • Homework 7.1
  • Homework 7.2
  • Exercise 7.3
  • Exercise 7.4
3

Tue, Sep 4

Thu, Sep 6

  • Chapter 7.5: Graphs in Puzzles and Games
  • Chapter 7.6: Binary Trees
  • Chapter 7.7: Hamiltonian Cycles and the TSP

Lectures:

Exercises:

Homework:

Quizzes:

Due Monday:

  • Quiz 7.3
  • Quiz 7.4

Due Friday:

  • Homework 7.3
  • Homework 7.4
  • Exercise 7.5
  • Exercise 7.6
  • Exercise 7.7
4

Tue, Sep 11

Thu, Sep 13

  • Chapter 7 project

Projects:

Due Monday:

  • Quiz 7.5
  • Quiz 7.6
  • Quiz 7.7

Due Friday:

  • Homework 7.5
  • Homework 7.6
  • Homework 7.7
5

Tue, Sep 18

Thu, Sep 20

  • Chapter 7 review and exam

Exam:

Due Friday:

  • Chapter 7 Project
6

Tue, Sep 25

Thu, Sep 27

  • Chapter 5.1: Introduction to Combinatorics
  • Chapter 5.2: Basic Rules for Counting

Lectures:

Exercises:

Homework:

Quizzes:

Due Friday:

  • Exercise 5.1
  • Exercise 5.2
7

Tue, Oct 2

Thu, Oct 4

  • Chapter 5.3: Combinations and the Binomial Theorem
  • Chapter 5.4: Binary Sequences

Lectures:

Exercises:

Homework:

Quizzes:

Due Monday:

  • Quiz 5.1
  • Quiz 5.2

Due Friday:

  • Homework 5.1
  • Homework 5.2
  • Exercise 5.3
  • Exercise 5.4

Fruit box solver

Binary Sequence solver

8

Tue, Oct 9

Thu, Oct 11

  • Chapter 5.6: Solving Recurrence Relations
  • Combinatorics review

Lectures:

Exercises:

Homework:

Quizzes:

Due Monday:

  • Quiz 5.3
  • Quiz 5.4

Due Friday:

  • Homework 5.3
  • Homework 5.4
  • Exercise 5.6
9

Tue, Oct 16

Thu, Oct 18

  • Chapter 5 project

Projects:

Due Monday:

  • Quiz 5.6

Due Friday:

  • Homework 5.6
10

Tue, Oct 23

Thu, Oct 25

  • Chapter 5 review and exam

Exam:

Due Friday:

  • Chapter 5 Project
11

Tue, Oct 30

Thu, Nov 1

  • Chapter 6.1: Introduction to Probability
  • Chapter 6.2: Sum and Product Rules for Probability

Lectures:

Exercises:

Homework:

Quizzes:

Due Friday:

  • Exercise 6.1
  • Exercise 6.2
12

Tue, Nov 6

Thu, Nov 8

  • Chapter 6.3: Probability in Games of Chance
  • Chapter 6.4: Expected Value in Games of Chance

Lectures:

Exercises:

Homework:

Quizzes:

Due Monday:

  • Quiz 6.1
  • Quiz 6.2

Due Friday:

  • Homework 6.1
  • Homework 6.2
  • Exercise 6.3
  • Exercise 6.4
13

Tue, Nov 13

Thu, Nov 15

  • Chapter 6.6: Matrices and Markov Chains
  • Chapter 6 Project

Lectures:

  • 6.6 Lecture

Exercises:

Projects:

Homework:

Quizzes:

Due Monday:

  • Quiz 6.3
  • Quiz 6.4

Due Friday:

  • Homework 6.3
  • Homework 6.4
  • Exercise 6.6
14

Tue, Nov 20

Thu, Nov 22

  • Chapter 6 project
  • Thanksgiving break

Projects:

15

Tue, Nov 27

Thu, Nov 29

  • Chapter 6 review and exam

Exam:

Due Monday:

  • Quiz 6.5
  • Quiz 6.6

Due Friday:

  • Homework 6.6
  • Chapter 6 Project
16

Tue, Dec 4

Thu, Dec 6

  • Optional final

Exam:

  • Final review
  • Optional final
17

Tue, Dec 11

Thu, Dec 13

  • Optional final

Exam:

  • Final Exam (Optional): Thursday, Dec 13th, 8:00 - 10:00 pm

Important JCCC dates, Fall 2018

August 14
Payment deadline
August 20
First day of classes
August 27
Last day to drop a full-semester course and receive a 100 percent refund.
September 17
Last day to drop a full-semester course without a withdrawal "W" on the student's permanent record. Deadline is 11 p.m. for drops completed on the web.
October 15
Application deadline for fall graduation
November 15
Last day to request a pass/fail grade option or to withdraw with a "W" from a full-semester course.
November 21
Classes not in session. College offices closed.
November 22-23
Thanksgiving Day holiday. College closed.
December 10-16
Final exams
December 17
Final grades entered by professors by 5 pm.


To view the deadline dates for dropping this course, please refer to the schedule on the JCCC web page, under Admissions > Enrollment Dates > Dropping Credit Classes.

After the 100% refund date, you will be financially responsible for the tuition charges; for details, search on Student Financial Responsibility on the JCCC web page.

Changing your schedule may reduce eligibility for financial aid and other third party funding. Courses not dropped will be graded. For questions about dropping courses, contact the Student Success Center at 913-469-3803.


 

Success, accommodations, and hardships

JCCC Resources

  • Tips for success
    Information on time management, participate, balance personal obligations, study environment, be respectful, speak up if you have problems, apply what you learn, stay motivated
  • Time management for students
    Information on time management: Keep a monthly schedule, make a weekly schedule, prioritize your activities. Use small pockets of time, tackle the hard things first, identify your best time, start projects as soon as they're assigned, keep to-do lists, divide tasks into small chunks, take care of yourself.
  • Dealing with test anxiety
    Information on test anxiety and coping.
  • Dealing with anxiety and stress
    Information on coping with anxiety and stress.
  • Hardships
    If you have a hardship (family death, medical problem causing you to miss school, etc.) you need to make sure to communicate with me if you're planning on staying in the course. Make sure to email me so that it is harder for the email to get lost! And if you don't hear back from me, make sure to follow up in another way. I am not a fan of getting makeup exam requests after the exam has passed!

Contacting Accessibility for Accommodations

JCCC has a branch called Access Services. If you work with Access Services, they will work with your teacher to provide services that we offer include testing accommodations, note-taking assistance, sign language interpreting services, audiobooks/alternative text, assistive technology and tutoring (when available). All accommodations are determined on a case-by-case basis during a meeting with an Access Services advisor.

You can get permanent or temporary accommodations, such as if you're facing a temporary hardship in your life. Stress and anxiety also count as hardships, so if you have test anxiety or social anxiety, it can help to reach out, so that you can make a plan with A.S. and the teacher for being able to be properly assessed academically in class while minimizing the challenges presented by your situation.

Some examples of accommodations are:

  • Note-taking assistance
  • Letting the teacher know that the student does not perform well in a group
  • Being able to take tests in the testing center, a quiet location without distractions, rather than in the classroom
  • Testing accommodations such as 1.5x time on exams

 

Additional information

Student Handbook

http://www.jccc.edu/student-resources/student-handbook.html


Student code of Conduct Policy

http://www.jccc.edu/about/leadership-governance/policies/students/student-code-of-conduct/student-code-conduct.html


College Emergency Response Plan

http://www.jccc.edu/student-resources/police-safety/police-department/college-emergency-response-plan/index.html

RC third floor Emergency Response Plan (PDF) detailed emergency instructions with storm security locations. During a weather emergency individuals should seek shelter in the interior most portion of the building away from exterior windows and doors.

RC storm security areas: RC 311, 321, 323, 334, 340, 342, 344, 345, 353, 355, 346, 347, and
RC 361A and 361B, 372D, Mens' and Womens' bathrooms.


Academic Dishonesty

No student shall attempt, engage in, or aid and abet behavior that, in the judgment of the faculty member for a particular class, is construed as academic dishonesty. This includes, but is not limited to, cheating, plagiarism or other forms of academic dishonesty.

Examples of academic dishonesty and cheating include, but are not limited to, unauthorized acquisition of tests or other academic materials and/or distribution of these materials, unauthorized sharing of answers during an exam, use of unauthorized notes or study materials during an exam, altering an exam and resubmitting it for re-grading, having another student take an exam for you or submit assignments in your name, participating in unauthorized collaboration on coursework to be graded, providing false data for a research paper, using electronic equipment to transmit information to a third party to seek answers, or creating/citing false or fictitious references for a term paper. Submitting the same paper for multiple classes may also be considered cheating if not authorized by the faculty member.

Examples of plagiarism include, but are not limited to, any attempt to take credit for work that is not your own, such as using direct quotes from an author without using quotation marks or indentation in the paper, paraphrasing work that is not your own without giving credit to the original source of the idea, or failing to properly cite all sources in the body of your work. This includes use of complete or partial papers from internet paper mills or other sources of non-original work without attribution.

A faculty member may further define academic dishonesty, cheating or plagiarism in the course syllabus.


ADA compliance / disabilities

JCCC provides a range of services to allow persons with disabilities to participate in educational programs and activities. If you are a student with a disability and if you are in need of accommodations or services, it is your responsibility to contact Access Services and make a formal request. To schedule an appointment with an Access Advisor or for additional information, you can contact Access Services at (913) 469-3521 or accessservices@jccc.edu. Access Services is located on the 2nd floor of the Student Center (SC202)


Course Catalog information

View the full course catalog at: http://catalog.jccc.edu/coursedescriptions/cs/#CS_211

Objectives

  1. Use the mathematical tools and techniques basic to and needed for most courses in computer science
  2. Use logic and truth tables
  3. Use sets and apply set operations
  4. Use functions
  5. Use integer and mod arithmetic
  6. Apply matrix operations
  7. Develop discrete proofs including mathematical induction
  8. Develop and use recursive algorithms
  9. Use combinatorial analysis
  10. Use recurrence relations
  11. Use relations and apply their properties
  12. Use elementary database principles
  13. Represent relations with matrices
  14. Use Hasse diagrams to illustrate partial orderings
  15. Use the principles of graph theory
  16. Use the principles of trees
  17. Use logic, Boolean expressions and circuits and minimize each
  18. Use simple grammar applications

Content Outline and Competencies:

I. Use fundamental mathematical tools
   A. Use logic
   B. Use truth tables
   C. Use propositional equivalences
   D. Use predicates and quantifiers
   E. Use sets
   F. Use Venn Diagrams
   G. Apply set operations
   H. Use power sets and cartesian products
   I. Use functions and their characteristics
   J. Use sequences and summations
   K. Use integer/mod arithmetic
   L. Use matrices
   M. Apply matrix operations

II. Do mathematical proofs
   A. Do proofs with truth tables
   B. Do proofs using mathematical induction
   C. Use rules of inference

III. Recursion
   A. Develop recursive algorithms
   B. Develop recursive functions
   C. Evaluate recursive definitions

IV. Counting
   A. Use the Sum Rule
   B. Use the Product Rule
   C. Use the Pigeonhole Principle
   D. Use Inclusion-Exclusion Principle
   E. Use Tree diagrams to solve appropriate counting problems
   F. Use Permutations
   G. Use Combinations
   H. Use discrete probability
   I. Use generalized permutations and combinations
   J. Use recurrence relations
   K. Solve recurrence relations
   L. Apply the inclusion-exclusion principle

V. Relations
   A. Use relations on a set
   B. Use the properties of relations
      1. reflexive
      2. irreflexive
      3. symmetric
      4. asymmetric
      5. antisymmetic
      6. transitive
   C. Combine relations
   D. Use n-ary relations
   E. Use elementary database principles
   F. Represent relations in matrix form
   G. Represent relations in digraph form
   H. Define equivalence relations
   I. Define partial orderings
   J. Use Hasse Diagrams to represent partial orderings

VI. Graph Theory
   A. Define graphs, digraphs, simple graphs, multigraphs, pseudographs
   B. Represent graphs as pictures
   C. Represent graphs in matrix form
   D. Use graph terminology
   E. Apply graph theory to applications
   F. Use adjacency and incidence matrices
   G. Use isomorphisms and their properties
   H. Use connectivity, paths and circuits
   I. Create Euler paths and circuits
   J. Create Hamilton paths and cycles
   K. Using Dijkstra's Algorithm, find the shortest path between points
   L. Use planar graphs and their properties
   M. Color maps, create graphs of maps, and use their properties

VII. Trees
   A. Define a tree and related vocabulary
   B. Use the properties of trees
   C. Create binary search trees
   D. Use trees for preorder, postorder, and inorder expressions
   E. Develop preorder, postorder, and inorder expressions
   F. Translate trees  into preorder, postorder, and inorder expressions
   G. Translate preorder, postorder, and inorder expressions to trees
   H. Use tree transversal methods
   I. Evaluate preorder, postorder, and inorder expressions
   J. Evaluate preorder, postorder, and inorder trees
   K. Define spanning trees
   L. Create minimum and maximum spanning trees of graphs
   M. Create depth-first and breadth-first spanning trees of graphs

VIII. Boolean Algebra
   A. Use Boolean expressions and operations
   B. Create a Truth Table from a Boolean expression
   C. Represent Boolean Expression as sums of products
   D. Define logic gates and related properties
   E. Create Boolean expressions from circuits
   F. Use logic gates to include OR, AND, NOT, NOR, and NAND
   G. Create circuits using OR, AND, NOT, NOR, and NAND gates
   H. Use Karnaugh Maps to minimize circuits and Boolean expressions
   I. Use Quine-McCluskey method to minimize circuits and Boolean
expressions

IX. Grammars
   A. Define grammars and related properties
   B. Use Phrase-Structure grammars
   C. Use finite-state machines 

Campus safety

JCCC Police & Safety: Information regarding student safety can be found at http://www.jccc.edu/student-resources/police-safety/

Classroom and campus safety are of paramount importance at Johnson County Community College and are the shared reponsibility of the entire campus population. Please review the following:

  • Report Emergencies to Campus Police (availalbe 24 hours a day)
    • In person: at the Carlsen Center (CC115)
    • Call: 913-469-2500 (direct line) - Tip: program in your cell phone
    • Phone app: download JCCC Guardian (the free campus safety app jccc.edu/guardian)
      -- It has an instant panic button and texting capability to Campus Police.
    • Anonymous reports: to KOPS-Watch jccc.edu/kops or 888-258-3230
  • Be Alert:
    • You are an extra set of eyes and ears to help maintain campus safety
    • Trust your instincts
    • Report suspicious or unusual behavior/circumstances to Campus Police (see above)
  • Be Prepared:
  • During an Emergency: Notifications/alerts (emergencies and inclement weather) are sent to all employees and students using email and text messaging.
    -- Students are automatically enrolled. See, the emergency notification page: http://www.jccc.edu/student-resources/police-safety/jccc-alert.html
  • Weapons Policy: Effective July 1, 2017, concealed carry handguns are permitted in JCCC buildings subject to the restrictions set forth in the Weapons Policy. Handgun safety training is encouraged of all who choose to conceal carry. Suspected violations should be reported to JCCC Police Department 913-469-2500 or if an emergency, you can also call 911.