cse2321

Discrete Mathematics

Course Description:

Propositional logic, Boolean algebra, first-order logic, sets, functions, basic proof techniques, graphs and trees, analysis of algorithms, asymptotic analysis, combinatorics, graph algorithms.

Textbook:

Combinatorial and Algorithmic Mathematics: From Foundation to Optimization, by Baha Alzalg. Kindle Direct Publishing. ISBN: 9798353826934

Online Lecture Notes:

The following lecture notes were written by my former student Sery Gunawardena in Fall 2019.

Lec. #	Topic(s)
1	General intro. Intro to propositional logic
2	Truth tables, logical operators (negation, and, or)
3	Implication
4	Contrapositive, converse, inverse, biconditional
5	Tautologies, contradictions, contingencies, negating cmpd stats
6	Propositional logic modeling, important laws
7	Disjunctive normal form
8	Sets, power set, manipulating sets
9	Set builder notation, conjunctive normal form
10	Intro to predicate logic, quantifiers
11	Multiple quantifiers
12	Negating quantified statements, mixing quantifiers
13	Symbolizing statements
14	Scope of variables, mathematical induction
15	Solving recurrences by induction, summations
16	Intro to asymptotic analysis, algorithmic statements, choosing an alg.
17	Analysis of an algorithm with types
18	Comparing algorithms, insertion sort
19	More examples on running time, upper/lower bounds
20	Asymptotic notations
21	Properties of asymptotic notations
22	More examples on asymptotic notations, proofs using limits
23	Describing the running time of a program
24	Linear search, selection sort, nonrecursive programs
25	Recursive programs, substitution method
26	Iterative method, binary search, merge sort
27	Recursion-tree method
28	Intro to graphs
29	Graph terminology
30	More graph terminology
31	More properties, Eulerian path/cycle
32	Hamiltonian path/cycle, graph coloring
33	Directed graphs, graph representation
34	Breadth-first search algorithm
35	Depth-first search algorithm
36	Topological sorting

cse2321

Main Menu