cse2321

Page Image


Page Content Discrete Mathematics
Course Description:
Propositional
logic, Boolean algebra, firstorder 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

Recursiontree 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

Breadthfirst search algorithm


35

Depthfirst search algorithm


36

Topological sorting




