[Autumn 2020: CSE 2321] Foundations I – Discrete Structures (Online)
This course is 100% online. All course activities will be conducted on Carmen. I will consider recording my lectures and require you to watch recordings on every class day by logging in to the course in Carmen. You will also log into Carmen for completion of assignments, projects, exams, etc. For more details read course syllabus and review all course information.
My Teaching Schedule > Autumn 2020
| Class | Class Title | Days & Times | Room |
| CSE 2321-0140 (36775) | Fndns 1: Discr Str (Lecture) | MoWeFr 9:10AM – 10:05AM | Online |
| CSE 2321-0120 (11013)* | Fndns 1: Discr Str (Lecture) | MoWeFr 10:20AM – 11:15AM | Online |
| CSE 2321-0090 (10554) | Fndns 1: Discr Str (Lecture) | MoWeFr 3:00PM – 3:55PM | Online |
| CSE 2321-0080 (10553) | Fndns 1: Discr Str (Lecture) | MoWeFr 4:10PM – 5:05PM | Online |
* Also CSE 5032-0030 (10035).
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.
Course Syllabus (click here) which also includes a tentative schedule, and topics covered.
Text: Introduction to Algorithms, 3rd edition, by Cormen, Leiserson, Rivest, and Stein, The MIT Press.
Below are lecture-by-lecture topics covered in Autumn 2020.
| 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 |