Discrete Mathematical Modeling

Fall 2021
Wednesdays 1:00-3:10pm
(with additional time online)
Burkle 26
Zoom ID: See Canvas course site


 

Contact Information

Course Instructor: Professor Allon Percus
Office: CGU Math South
Phone: 909-607-0744
E-mail:
In-person office hours: Mondays 10-11am, or by appointment
Zoom office hours: by appointment

Teaching Assistant: An Ly
E-mail: an.ly@cgu.edu
In-person office hours: Wednesdays 10-11am in Math North
Zoom office hours: by appointment

Instructor Feedback and Communication
The best way to get in touch with me is by e-mail. I will do my best to respond to e-mail messages within 2 business days.

Course description

Discrete mathematics deals with countable quantities. The techniques used for discrete models are often significantly different from those used for continuous models. This course explores some of the main techniques and problems that arise in discrete mathematical modeling. Topics include combinatorial analysis, Markov chains, graph theory, optimization, algorithmic behavior as well as current research topics. The goal is for students to acquire sufficient skills to solve real-world problems requiring discrete mathematical models.

Credits/Units: 4

Background Preparation (Prerequisites)

Prior exposure to combinatorics, probability and linear algebra is assumed. Students must have sufficient programming skills (in any language) to write a basic simulation code. Other background that is helpful but not required: an undergraduate-level course in discrete mathematics, and some exposure to analysis of algorithms.

Student Learning Outcomes

By the end of this course, students will be able to:

  • Understand and apply fundamental mathematical techniques needed for discrete modeling.
  • Confidently solve real-world problems that involve discrete mathematical modeling.
  • Develop valid algorithmic and computational approaches to implement discrete models.

Texts and Journal References

All required materials, including course notes, will be posted on Canvas under the Files link.

Class Schedule

  • Sep 1: Combinatorial analysis. Product and sum rule; permutations and combinations; inclusion-exclusion; pigeonhole principle.
  • Sep 8: Combinatorial analysis. Generating functions; algorithms and complexity.
    Assignment #1 due
  • Sep 15: Markov chains. Definitions; stationary distribution.
  • Sep 22: Markov chains. Sampling; card shuffling.
    Assignment #2 due
  • Sep 29: Markov chains. Markov-chain Monte Carlo; mixing time; spectral analysis.
    Assignment #3 due
  • Oct 6: Markov chains. Strong stationary time.
    Final project proposal due
  • Oct 13: Graph theory. Connectivity; graph coloring.
    Assignment #4 due
  • Oct 20: Graph theory. Spanning trees; graph algorithms.
    Assignment #5 due
  • Oct 27: MIDTERM EXAM
  • Nov 3: Combinatorial optimization. Shortest path; minimum spanning trees.
    Assignment #6 due
  • Nov 10: Combinatorial optimization. Network flows; heuristics; simulated annealing.
  • Nov 17: Random networks and algorithms. Random graph theory; zero-one laws; phase transitions.
    Assignment #7 due
  • Nov 24: THANKSGIVING BREAK
  • Dec 1: Random networks and algorithms. Random graph coloring; first moment method; algorithmic consequences.
  • Dec 8: FINAL PROJECT PRESENTATIONS

All in-person lectures will also be broadcast via zoom (click on Zoom link in Canvas). These lectures will be recorded and made available through the Media Gallery link in Canvas. Due to copyright issues, students may not circulate these recordings or distribute them outside of the class.

Assignments and Assessments

Assignments Overview, Expectations, and Logistics

Homework assignments will be posted on Canvas. All completed assignments must be submitted electronically as a PDF file, uploaded to Canvas. You may typeset your homework in your preferred software or scan your handwritten work. I will post the LaTeX source code along with each homework assignment; those of who choose to typeset your homework submissions in LaTeX may find this helpful. Homework solutions will be posted the morning after the homework due date. Therefore, no late homework will be accepted.

Grading Plan

 

Class Element Weight
Homework assignments (lowest homework grade will be dropped) 35%
Midterm exam 30%
Final project 30%
Class participation 5%

I will make every effort to return to you each homework assignment with feedback within 7 days.

Note that there will be a midterm exam and a final project, but no final exam. The midterm exam will be open book, and may be taken either in class or online.

Final Grades
Your grade will be calculated using the following scale. Grades with plus or minus designations are at the professor’s discretion.

 

Letter Grade Grade Point Description Learning Outcome
A 4.0 Complete mastery of course material and additional insight beyond course material Insightful
B 3.0 Complete mastery of course material Proficient
C 2.0 Gaps in mastery of course material; not at level expected by the program Developing
U 0 Unsatisfactory Ineffective

In exceptional circumstances (e.g., illness) that prevent a student from completing assigned coursework, and provided that the student’s work to date is satisfactory, the instructor may assign an I (Incomplete) grade along with a date for successful submission of course assignments and requirements.

Continual matriculation at CGU requires a minimum grade point average (GPA) of 3.0 in all coursework taken at CGU. Students may not have more than two incompletes at one time.

CGU policies on grades, including incomplete grades, registration and enrollment can be found on the Registrar’s webpage: http://www.cgu.edu/registrar.

Class Policies

The CGU institutional policies apply to each class offered at CGU. Students are encouraged to review the student handbook for their program as well as policy documentation in the Bulletin and on the Registrar’s webpages: http://bulletin.cgu.edu/ and http://www.cgu.edu/registrar. The protocols defined by the CGU’s Student Conduct Code must be upheld in all classes. For more information, please visit CGU’s Basic Code of Conduct (links to an external site).

Credit Hour

Credit hour refers to the units or credits earned by a student for the successful completion of a course at CGU. These are the units recorded on transcripts and the units that are counted toward degree requirements. For CGU courses, a single unit or credit is determined by 10.5 hours of instructional activity per semester. Instructional activity includes direct instructor contact in a physical or virtual classroom as well as asynchronous instructional content for online or hybrid courses. See the full policy here.

Attendance

Students are expected to attend all classes, whether the class is taken for credit or on an audit basis. Students unable to attend a class must seek permission for an excused absence from the instructor prior to the class meeting. Unapproved absences or late attendance for three or more classes may result in a lower grade or being involuntarily withdrawn from the class (with enrollment refunds governed by CGU’s published Academic Calendar). If students have to miss a class, they should arrange to get notes from a fellow student.

Scientific and Professional Ethics

The work you do in this class must be your own. You may collaborate on homework assignments. However, all your answers must be explained in your own words. Your homework submission must also state the names of all those with whom you collaborated.

Feel free to build on, react to, criticize, and analyze the ideas of others but, when you do, make it known whose ideas you are working with. You must explicitly acknowledge when your work builds on someone else’s ideas, including ideas of classmates, professors, and the authors you read. If you ever have questions about drawing the line between others’ work and your own, ask the instructor for guidance. Exams must be completed independently and, unless expressly permitted, without using cell phones, tablets, or computers to search or retrieve material. Any collaboration on answers to exams, unless expressly permitted by the instructor, may result in an automatic failing grade and possible expulsion from the program.

Additional information on CGU’s Policy and Procedures for Violations of Standards of Academic Integrity can be found at: https://cgu.policystat.com/policy/3903703/latest/.  In addition, the Claremont Colleges Library has a number of resources on academic honesty and integrity, including the following online tutorial: https://library.claremont.edu/exploring-academic-integrity/

Standards of Appropriate Behavior for Students Attending Online

Web based programs define the area in view of the camera as part of the classroom. Students must therefore present themselves and their surroundings as much as possible as though they are in a physical classroom. Attending class remotely, you can easily forget that your home environment is fully visible and can be distracting to you and your classmates. Here are some guidelines to help you to be more intentional and effective in how you attend class online:

Appropriate Dress: Even though you are at home, dress in casual professional attire for class so that you present yourself appropriately to your instructor and peers on camera. Remember, there is no back row in a video meeting. What you wear is amplified and speaks loudly!

Location: Attend class in a location that allows for your full attention and participation. Aim to be on-camera in an environment free of auditory or visual distractions, and that allows for open, focused participation in class discussion. While home situations differ and some interruptions might be unavoidable, aim for the following:

  • Be mindful of your background. Your camera captures you and anything in your background, so find a background that is appropriate to be viewed by your classmates. You can always set up a virtual background in Zoom that will hide the real background in your location.
  • Stay on camera – leaving the camera frequently or for extended periods of time disengages you and others from class work.
  • Make prior arrangements with family members to give you dedicated uninterrupted space and time for the duration of each class meeting. Avoid public locations, especially locations that are noisy and distracting or where you cannot freely speak to engage in discussions.
  • Stay focused. Avoid the following to the extent you are able: Interacting with persons not part of the class, behaving in an overly inattentive manner, multi-tasking with non-class related work.

We understand that you may have challenges with caregiving or finding a distraction-free space for the duration of each class meeting. Please speak with your professor about this so that we can work out ways to optimize your engagement and reduce interruption and distractions.

Other Resources

Accommodations for Students with Disabilities
CGU is committed to creating courses that are inclusive and accessible. If you would like to request academic accommodations due to temporary or permanent disability, contact the CGU Dean of Students and Coordinator for Student Disability Services at DisabilityServices@cgu.edu or (909) 607-9448. Reasonable accommodations are considered after you have conferred with the Office of Disability Services (ODS) and presented the required documentation of your disability to the ODS. Planning is essential, so please communicate to the ODS as soon as possible.

Mental Health Resources
Graduate school is a context where mental health struggles can arise or be exacerbated. If you ever find yourself struggling, please ask for help. If you wish to seek out campus resources, here is some basic information: services.claremont.edu/mcaps/

Monsour Counseling and Psychological Services (MCAPS) is committed to promoting psychological wellness for all students at The Claremont Colleges. Professional and well-trained psychologists, psychiatrists, and post-doctoral and intern therapists offer support for a range of psychological issues in a confidential and safe environment.

Phone (909) 621-8202
After hours emergency (909) 607-2000

Tranquada Student Services Center, 1st floor
757 College Way
Claremont, CA 91711

Title IX
One of my responsibilities as an instructor is to help create a safe learning environment.  I am a mandatory reporter. Thus, if I learn of any potential violation of CGU’s gender-based misconduct policy (e.g., rape, sexual assault, dating violence, domestic violence, or stalking) by any means, I am required to notify the CGU Title IX Coordinator at Deanof.Students@cgu.edu or (909) 607-9448. Students can request confidentiality from the institution, which I will communicate to the Title IX Coordinator. If students want to speak with someone confidentially, the following resources are available on and off campus: EmPOWER Center (909) 607-2689, Monsour Counseling and Psychological Services (909) 621-8202, and The Chaplains of The Claremont Colleges (909) 621-8685. Speaking with a confidential resource does not preclude students from making a formal report to the Title IX Coordinator if and when they are ready. Confidential resources can walk students through all of their reporting options. They can also provide students with information and assistance in accessing academic, medical, and other support services they may need.

Campus Security
Campus security can be reached 24 hours/day at (909) 607-2000. Please download the CGU Safety Resource Card to your phone’s contacts.

Office of Information Technology (OIT)
The Office of Information Technology has a helpdesk to support you with CGU wireless access and email issues. They also have good documentation you can use to learn to connect and use online resources. Websitehttps://mycampus.cgu.edu/web/it

Center for Writing and Rhetoric (CWR)
CGU has a graduate studies-focused Center for Writing and Rhetoric that works with you no matter where you are in the writing process. The CWR is not just for remediation of your writing, but for all writers to provide partnership and consultation to improve your academic work at all levels. The CWR can work with you in planning, outlining, drafting, and final review of documents and presentations for class work, conferences, and publications. Websitehttps://mycampus.cgu.edu/web/writing-rhetoric

The Claremont Colleges Library
The Claremont Colleges Library has a wealth of resources, including subject specialist librarians, to support your academic work. Use the library for class work and research to access and use databases for articles, books, and data sets, to understand how to conduct effective searches and evaluate sources, use digital tools, and much more. The library offers workshops and 1-1 consultations with students as well. Website: https://library.claremont.edu/