CSIT 242 (Discrete Math II) Topics I cover

1. Recurrence Relations. This includes Solving homogeneous linear recurrence relations with constant coefficients, solving nonhomogeneous linear recurrence relations with constant coefficients, solving linear recurrence relations with nonconstant coefficients, solving nonlinear recurrence relations. Methods we'll use are iteration, substitution, reduction, and the rules for linear recurrence relations. Topics you need for this section include solving equations, solving linear systems of equations, and induction.
   Problems and answers.

Nonhomogeneous linear recurrence relations of order 1 or 2 and with constant coefficients.

2. The binomial and the multinomial theorems (all forms including negative exponents and more than two terms).
3. Undirected graphs I.
   Handout 1
   Handout 2
   Handout 3
   Handout 4
   Topics covered: Pseudograph (multigraph); simple graphs: Representation of a graph as an adjacency matrix (and the space complexity of the representation), the degree of a vertex (and even, isolated, and odd vertices), regular graphs, degree sequence (relationship between the degree sequence, the adjacency matrix, the square of the adjacency matrix, and the number of edges), the complement of a graph, maximum number of edges in a graph, adjacent vertices and adjacent edges, parallel edges, loops, how to get the adjacency matrix of the complement of a graph G from from the adjacency matrix of G, examples on previous topics, representation of a graph as an adjacency list and the space complexity of that, when to use the adjacency matrix representation and when to use the adjacency list representation, complete graphs, bipartite graphs, complete bipartite graphs, bipartition sets, test for bipartite graphs, null (discrete graphs), linear graphs, cyclic graphs, n-cubes, G-{e}, G-{v}, facts related to the previous topics, subgraphs, paths, simple paths, cycles, simple cycles, n-cycles, odd cycles, even cycles, Euler cycle and Eulerian graph, Hamiltonian cycle and Hamiltonian graph, Eulerian path, Hamiltonian path, connected and disconnected graphs, traveling salesman tour and problem, facts related to the previous topics, isomorphic graphs, examples and facts on isomorphisms, vertex cover, independent set, weighted graphs, bipartite graphs and odd simple cycles, cliques, relationship between powers of the adjacency matrix and paths, facts and examples on independents sets, cliques, and vertex covers, the traveling salesman problem, acyclic graphs.
• Graph Questions (Group 1) (Solutions).
• Graph Questions (Group 2)
• Graph Questions (Group 3) (Solutions).
4. Digraphs and digraphs algorithms.

Handout 1.

Handout 2.

Topics covered: Similar to the topics covered for graphs. In addition to that, we covered in-neihborhoods, out-neighborhoods, balanced and semi-balanced vertices, pseudodigraphs and binary relations, adjacency relation and reachable relation, tournaments, unilateral digraphs, oriented digraphs, the converse of a digraph, theorems about Eulerian cycles, Eulerian paths, Hamiltonian cycles, Hamiltonian paths, digraph algorithms like graph reachability and maximum network flow.

5. Undirected trees and their algorithms.

Handout 1

Handout 2

Handout 3

Topics covered: Basic definitions, m-ary trees, full m-ary trees, balanced m-ary trees, complete m-ary trees, maximal complete m-ary trees, spanning trees, theorems and facts about trees, tree traversal and algorithms for that, tree labeling, Polish and Reverse Polish notation (infix, postfix, prefix forms and their binary tree representation), minimal/minimum spanning trees, maximal/maximum spanning trees, Kruskal's algorithm, Prim's algorithm, isomorphisms of free trees, rooted trees, and binary rooted trees, other topics.

6. Generating functions.
   Topics Covered: Adding, subtracting and multiplying generating functions, the extended (generalized) polynomial coefficients, Newton's (the extended/generalized) binomial theorem, solving recurrence relations by using generating functions.
7. Combinatorics:
   Handouts:
1. Examples
2. Exercises (Group I)
3. Exercises (Group II)
4. Combinatorics


Topics Covered: set theory and number theory theorems, the addition principle, the multiplication principle, permutations, combinations, generalized permutations and combinations, the pigeonhole principle, derangements, recursive formulas for D_n (number of derangements of n objects) of first and second order, solving the two recursive formulas for D_n, the generating function for D_n/n! and using the generating function to find D_n.

8. Languages
   Introduction: sets, multisets, and sequences, and the differences between them; alhpabets, strings, operations on strings, langauges, operations on languages.
9. Automata
   Handout 1
   Topic covered:
   Deterministic finite automata (DFA), nondeterministic finite automata (NFA) inclduing NFA with lambda transitions, converting NFA to DFA, minimmizing DFA, regular expressions and grammar, regular languages and facts about regular languages.