Math 132 - Discrete and Combinatorial Mathematics

[Top]     [Home]     [e-mail]     Office: SA-130     Phone: x2135
Final exam is to be held on Wednesday, May 28, at 15:30, at rooms EB203 (Agah -- Öztürk) and EB102 (Satir --Yildirim).
Using a wrong room may result in a penalty!
These problems are highly recommended for self-study.
A common make-up is to be held on Monday, May 31st, at 10:00-12:00.
 `Common' means that it is for ALL exams missed and ALL topics covered during the semester are included!
Important announcements/assignments/grades etc. are to be placed here. Check often to be informed!
[Top]     [Home]
 
  • Tentative course schedule * (2004)
  • Midterm I **  
    		•  [2005]
  • Midterm II **  
    		•  [2005]
  • Final
    		•  [2005]
    		 
  • Exam rules and terms
  • Suggested problems   [Updated 05/12/2005]
  • Midterm I review problems   [Updated 02/26/2010]
  • Midterm II review problems   [Updated 04/21/2010]
  • Final review problems   [Updated 05/20/2010]
    • * This schedule is tentative. Depending on the class and/or requests of other related departments, I reserve the right to skip/fast forward certain topics in order to pay more attention to certain others
    ** Exam dates can be changed provided the request is filled in advance and majority of the class supports it
    Exam contents listed below are tentative and are subject to change (depending on the actual pace of the class)
    [Top]     [Home]
    Informal course contents --- see Suggested problems
    [Top]     [Home]
    Midterm I    (25%)   Saturday, March 13, 14:00--16:00    
    See:   [    important remarks]   [samples]   [problems]   (updated 02/26/2010)

    Topics covered (tentative): (updated 02/26/2010)
  • Formulas for the number of linear arrangements (without or with repetitions), circular arrangements (without repetitions), and combinations (without or with repetitions).
  • Algebraic properties of binomial coefficients; identities; applications.
  • The concept of (closed) statement = Boolean variable. Elementary Boolean operations and Boolean expressions, properties (identities), simplification. Disjunctive normal form. Applications.
  • Open statements; quantifiers and their simplest properties.
  • Sets, elements, subsets. Sets as open statements.
  • The number of subsets; applications (counting and combinatorial identities).
  • Set operations (union, intersection, complement, difference, symmetric difference) and their properties.
  • Venn diagrams; applications to counting.
  • Well ordering and its applications; induction.
  • Divisibility of integers, primes, greatest common divisor, Euclidean algorithm, prime factorization and its uniqueness.

    Chapters:   1 (1-4), 2 (1, 2, 4), 3 (1-3), 4 (1, 3-5)
    [Top]     [Home]
    Midterm II    (25%)   Friday, April 30, 6pm--8pm (Room B206)    
    See:   [    important remarks]   [samples]   [problems]   (updated 4/21/2010)

    Topics covered (tentative)*: (updated 4/19/2010)
  • Cartesian product. Relation as a subset. Functions. Counting relations, functions, injections, and surjections. Stirling numbers.
  • Properties of relations (mainly, the terminology: reflexive, (anti-)symmetric, and transitive relations).
  • Partial orders: definition and properties; Hasse diagrams; maximal/minimal and greatest/least elements; least upper bound and greatest lower bound; lattices; extending a partial order to a total order.
  • Equivalence relations and partitions.
  • The pigeonhole principle and related tricks (extensive practice is highly recommended).
  • The principle of inclusion and exclusion: the basic formula, the formulas for Ek and Lk, applications to counting, the Euler function.
  • Graphs (general notions, subgraphs, isomorphisms).
  • Trees: definition and basic properties; (minimal) spanning tree of a graph; Kruskal's and Prim's algorithms.
  • Euler circuits and Hamilton cycles.
  • Planar graphs (Kuratowski's theorem, Euler's theorem, dual graphs); applications.
  • Graph coloring (chromatic polynomials and chromatic numbers)

    Chapters:   5 (1-3, 5), 7 (1, 3-4), 8 (1-2), 11 (1-6), 12 (1), 13 (2)
    * The material covered in Midterm I is fully included
    [Top]     [Home]
    Final    (35%)   TBA    
    See:   [    important remarks]   [samples]   [problems]   (updated 05/20/2010)

    Topics covered (tentative)* (updated 05/12/2005):
  • Generating function: choosing and writing down the function related to a problem, computing the coefficients (whenever possible) and related tricks (including a few `known' functions and partial fractions).
  • Linear recurrence relations with constant coefficients: homogeneous (both methods) and nonhomogeneous (via generating functions). Applications to counting: setting a recurrence relation for a sequence in question, examples (Fibonacci numbers, compositions of integers, etc).

    Chapters:   9 (1, 2), 10 (1, 2, 4)
    * The material covered in Midterm I and Midterm II is fully included
    [Top]     [Home]
    Quizzes and Homeworks     (10%)   Quizzes are to be held weekly in class (10-15 mins at the end) except midterm weeks. Hopefully, 8 to 9 quizzes will be given, with disregarding the two worst.

    All questions regarding the quizzes are to be directed to the assistant. The assistant is instructed to  give no credit  to identical papers. The same applies to the exams.
    [Top]     [Home]
    Remarks    

    Most exam problems will be taken from the textbook. Solve them in advance, and you will do well! Same concerns quizzes.
    During the exams please keep in mind the following:
  • Calculators are  not  allowed 
  • Identical solutions (especially identically wrong ones) will  not  get credit. I reserve the right to decide what "identical" means. You still have the right to complain 
  • Do not argue about the distribution of the credits among different parts of a problem. I only accept complaints concerning my misunderstanding/misreadung your solution 
  • Show all your work. Correct answers without sufficient explanation might  not  get full credit 
  • Indicate clearly and unambiguously your final result. In proofs, state explicitly each claim 
  • Do not misread the questions or skip parts thereof. If you did, do not complain 
  • If you believe that a problem is misstated, do not try to solve it; explain your point of view instead. However, do not take advantage of this option: usually problems are stated correctly! 
  • Each problem has a reasonably short solution. If your calculation goes completely out of hands, something must be wrong (e.g., you might have chosen a wrong basis) 

    Grading policy     *
    I will take off a few (2-3) points for arithmetical mistakes. However,  a lot  of points will be taken off for `obvious' mistakes, i.e., either those that you can easily avoid or those showing a deep misunderstanding of the subject. This includes, but is not limited to, the following:
  • Things that don't make sense
  • A count of a case exceeding the total count
    Furthermore, solving a different problem (other than stated), even if perfect, will give you  no credit 
    * Of course, this only applies to problems that I am grading personally
    [Top]     [Home]

    Last update: May 12, 2005