CSCE 235H - Introduction to Discrete Structures (Honors)

Spring 2021

Resources & Announcements

• Detailed schedule
• Piazza is the discussion board. All questions and comments to instructor, TAs (private) and to class (broadcast) and all online discussions must be done through Piazza. You can state your name or write anonymously. No email messages sent directly will be answered.
• Handin: Homework must be submitted on handin
• Web Grader: Use the Web Grader to check your submissions
• Canvas: All grades will be posted on Canvas.
• Anonymous Suggestion Box

General Info

Detailed Schedule

Handouts & Files

Rules & Tools for Success

• Syllabus (PDF)
• Introduction (PPTX)
• Logical Equivalences Cheat Sheet (PDF).
• How to Prepare for an Exam (PPTX).

Slides

• Logic (PPTX).
• Logical Equivalences Cheat Sheet (PDF).
• Predicates & Quantifiers (PPTX).
• Proofs (PPTX).
• Sets (PPTX).
• Functions (PPTX).
• Relations: original slides (PPTX).
• Partial Orders (PPTX).
• Induction (PPTX).
• Algorithms (PPTX).
• Algorithms Analysis (PPTX).
• Asymptotics (PPTX).
• Sequences and Summations (PPTX).
• Recursion (PPTX).
• Master Theorem (PPTX).
• Combinatorics (PPTX).

Homework

• All homework are due before class on the due date (by 12:30 P.M.).
• Checklist: Guidelines for Submitting Homework (.pdf)


• Homework 01 (.pdf) - Due Friday, Feb 5, 2021
• Homework 02 (.pdf) - Due Wednesday, Feb 17, 2021
• Homework 03 (.pdf) - Due Monday, Feb 22, 2021
• Homework 04 (.pdf) - Due Monday, March 1 2021
• Homework 05 (.pdf) - Due Monday, March 8, 2021
• Homework 06 (.pdf) - Due Friday, Mar 12, 2021
• Homework 07 (.pdf) - Due Friday, Mar 19, 2021
• Homework 08 (.pdf) - Due Friday, Mar 26, 2021
• Homework 09 (.pdf) - Due Friday, Apr 2, 2021
• Homework 10 (.pdf) - Due Friday, Apr 9, 2021
• Homework 11 (.pdf) - Due Friday, Apr 16, 2021
• Homework 12 (.pdf) - Due Friday, 23, 2021
• Homework 13 (.pdf) - Due Friday, Apr 30, 2021
  

SAT Study

• Part 1: Introduction to Satisfiability
  
  • Slides (PPT, PDF)
  • Homework (PDF) - Due Wednesday Feb 17, 2021
  • Search Tree powerpoint example (SearchTree.pptx)
• Part 2:
  
  • Modeling Sudoku as a CNF: Slides (PPT, PDF)
  • Simple modeling: Homework (PDF) - Due Feb 22, 2021
• Part 3: MiniSAT
  • Installing MiniSAT: Slides (PPT, PDF)
  • Running MiniSAT: Homework (PDF) - Due Mar 8, 2021
  • DIMACS cnf example file (test.cnf)
• Part 4:
  • SATviz (satviz.unl.edu)
  • Encoding for MiniSAT, Sudoku file MiniSAT (Part 1 of 3): Homework (PDF) (GenerateSudoku.java) - Due Mar 15, 2021
  • Two Sudoku Rules in Conjunctive Normal Form (TEX, PDF)
• Part 5:
  
  • Unit Propagation and Variable Ordering in MiniSAT: Slides (PPT) (PDF)
  • Sudoku file MiniSAT (Part 2 of 3): Homework (PDF)- Due Mar 22, 2021
• Part 6:
  • Clause Learning and Intelligent Backtracking in MiniSAT: Slides (PPT) (PDF)
  • Sudoku file MiniSAT (Part 3 of 3): Homework (PDF) (SudokuInstances.tar.gz) - Due Mar 29, 2021
• Part 7:
  • Watched Literals and restarts: Slides (PPT) (PDF)
  • Terminology, assignment trail, implication graph: Homework (PDF) (ImplicationGraphTemplate.ppt) - Due April 5, 2021

Recitations (informal notes)

• Working with Latex: Introduction To LaTeX, LaTexHowTo.doc, hw-example.tex, hw-example.pdf, BibliographyFile.bib. Here are the figures (which can be generated with any drawing software): FIG, EPS, PDF. The example Hello World shown in recitation. If tables become to large, you can place a table sideways. An example tex file is given with its pdf output.
• Propopositional Logic (PDF, TEX)
• Proofs in PL and FOL (PDF, TEX)
• Proofs and FOL (PDF, TEX)
• Proofs and Sets (PDF, TEX)
• Sets and Functions(PDF, TEX)
• Relations (PDF, TEX)
• Transitive Closure and Partial Orders (PDF, TEX)
• Partial Orders (PDF, TEX)
• Induction (PDF, TEX)
• Asymptotics and Summations (PDF, TEX)
• Solving Recurrence Relations (PDF, TEX)

Videos

• Relations: Relations-P1 (Review), Relations-P2 (Warshall Algorithm), Relations-P3 (Equivalence Relations).
• Partial Orders POSET-P1 (Partial Orders), POSET-P2 (Principle of Well Ordered Induction), POSET-P3 (Lexicographic order), POSET-P4 (Hasse Diagrams), POSET-P5 (Extremal Elements), POSET-P6 (Lattices), POSET-P7 (Topological Sorting).
• Induction: Induction-P1 (Induction), Induction-E1 (Example 1), Induction-E2 (Example 2), Induction-E3 (Example 3), Induction-E4 (Example 4), Induction-E5 (Example 5), Induction-E6 (Example 6),Induction-P2 (Strong Induction), Induction-E7 (Example 7), Induction-E8 (Example 8).
• Algorithms: Algorithms-P2, Algorithms-P3.
• Algorithms Analysis: Algorithms-P4 Algorithms-P5
• Asymptotics: Asymptotics-P1 Asymptotics-P2
• Sequences and Summations: Sequences-P1 Sequences-P2
• Recursion: Recursion-P1, Recursion-P2, Recursion-P3, Recursion-P4. Recursion-P5. Recursion-P6.
• Master Theorem: Master Theorem.
• Combinatorics: Combinatorics-1, Combinatorics-2, Combinatorics-3, Combinatorics-4, Combinatorics-5, Combinatorics-6.

Useful Links

• Discrete Math
• A nice overview of the various types of proofs with examples .
• Proofs by induction: Great pointers identified by Geoffrey Priester
  • Induction exercises by Devadas and Lehman: Induction I, Induction II, Induction III.
  • Proof by induction on YouTube: Example I, Example 2, Example 3.
• Common Mistakes in Discrete Math, from textbook's page.
• A Guide to Proof-Writing, from textbook's page.
• Online Learning Center of the textbook
• Book Of Proof, by Richard Hammack (pdf)
• CSE 235 webhandin
• SAT
• A three-part introduction to SAT solving on Coding Nest: Part 1, Part2, Part3.
• Dr. Scott's Tips On Technical Writing
• UNL Computer Science and Engineering Academic Integrity Policy
• Java
  • Java Tutorials
  • Using Commandline Arguments
  • Java for C++ Programmers
  • Java IDEs
    • Netbeans IDE
    • Eclipse IDE
• C++
  • Java to C++ Transition Tutorial
  • C++ For Java Programmers (PDF, Lecture series)
  • C++ Tutorial
  • Makefile Tutorial
  • Using Command Line Arguments example
  • Cornell's Numerical Recipes in C
• Code Documentation
  • C++ Coding Standard
  • JavaDoc -- The original documentation tool for Java
  • PHP Doc Documentation tool for PHP code.
• LaTeX
  • LaTex on Wikibooks
  • Example Homework LaTeX document (TEX, PDF). Here are the figures files (which you could generate with your favorite drawing software): FIG, EPS, PDF.
  • TeX Users Group
  • Getting Started With LaTeX
  • LaTeX Tutorial
  • The Not-So-Short Introduction to LaTeX 2e (PDF)
  • LaTeX Quick Reference Card (.pdf)
  • The Comprehensive LaTeX Symbol List (.pdf)
  • MikTeX -- A Windows LaTeX Distro (Includes TeXworks, a LaTeX Frontend)
  • WinEDT -- A Windows LaTeX Frontend (Shareware, a free alternative is TeXworks which comes included in MiKTeX)
  • LyX -- User Friendly LaTeX Frontend
  • MacTeX -- An OS X LaTeX Distro (Includes TeXworks and TeXShop, two LaTeX Frontends)
  • Overleaf -- An online LaTeX editor, free for individual student users.
  • Texmaker -- A cross-platform LaTeX editor (includes many nice features)
  • Excel2Latex -- Useful for converting Excel tables to LaTeX. It is helpful to uncheck all the options when converting the table, and \usepackage{bigstrut} in your document.
  • Calc2Latex -- Useful for converting OpenOffice Calc tables to LaTeX.
  • Classify LaTeX Symbols -- Draw the symbol you are looking for