Discrete Structures II, CSCI/MATH 2113.

Dalhousie University,

Department of Mathematics and Statistics, and

Faculty of Computer Science.

Class notes and slides:

• Week 11. April 22-26.
  Languages. Test on April 24.
  Section 6.1.

• Week 10. April 15-19.
  More coding theory, languages.
  • Class 10.2 Notes on Coding Theory! Pdf, Html.
  • Class 10.3. Languages. Section 7.1.

• Week 9. April 8-12.
  Equivalence relations. Modular arithmetic. Introduction to error-correcting codes.
  Sections 7.4, 16.4.
  • Class 9.1 Pdf, Html. More on partial orders. Review graphs and trees. Section 7.3
    
  • Class 9.2 Pdf, Html. Equivalence relations. Modular arithmetic. Section 7.4, 14.3
    
  • Class 9.3. Introduction to coding theory. Section 16.4.

• Week 8. April 1-5.
  Review of trees. Relations.
  Sections 12.2, 12.3, 7.1-7.3.
  • Class 8.1 Pdf, Html. Tree traversals, depth-first and breadth-first search. Section 12.2.
  • Class 8.2 Pdf, Html. Merge sort, review of relations. Sections 12.3 and 7.1.
  • Class 8.3 Pdf, Html. Relations and graphs and matrices. Partial orders. Sections 7.2 and 7.3.

• Week 7. Feb. 26-March 1.
  Trees.
  Sections 12.1, 12.2.
  • Class 7.1 Pdf, Html. Trees and connectivity. Section 12.1.
  • Class 7.2 Pdf, Html. Introduction to rooted trees. Section 12.2.
  • Class 7.3. Huffman coding. Section 12.4.

• Week 6. Feb. 11-15.
  More graph theory.
  Sections 11.3, 11.5.
  • Class 6.1. More about adjacency matrix. Review for test.
  • Class 6.2: Test.
  • Class 6.3: Euler circuits and Hamiltonian cycles.

• Week 5. Feb. 4-8.
  Graph theory
  Sections 11.2, 11.3.
  • Class 5.1. Subgraphs, complement, and introduction to isomorphisms. Section 11.2.
  • Class 5.2 Pdf, Html. Graph isomorphism. Section 11.2.
  • Class 5.3 Pdf. Adjacency matrix.

• Week 4. Jan. 28-31.
  More generating functions. Review of graph theory
  Class handout, section 11.1.
  • Class 4.1 (pdf). This contains a step-by-step description of how to use generating functions to obtain a direct formula. It is demonstrated with the Fibonacci numbers. More examples can be found in the class handout.
  • Class 4.2 (pdf). Review of graph theory, and a review of manipulating generating functions.

• Week 3. Jan. 21-25.
  Generating functions.
  Chapter 9.
  • Class 3.1 (pdf)
    
  • Class 3.2: Maple worksheets for the problems done in class can be downloaded below. I have also included web pages giving the text of each of the work sheets. Maple is extremely user-friendly, and available on many machines in campus (try the lab in the Life Sciences building, near the hallway to Chemistry). A student version is available pretty cheap at many comuter stores. I recommend that you give it a try! Maple web site.
    • Danish pastries. *** Maple worksheet.
    • Diner. *** Maple worksheet.
    • Oranges. *** Maple worksheet.
  • Class 3.3 (pdf)
    
    • Fibonacci numbers in nature. Lots of pictures!
    • Fibonacci number web page.

• Week 2. Jan. 14-18.
  Generating permutations. Inclusion/exclusion revisited. Derangements.
  Class notes. Sections 8.1 and 8.3.
  • Class 2.1 (pdf)
    
  • Class 2.2 (pdf) and html
    
  • Class 2.3 (pdf)
    
    • Link with information on the Traveling Salesman Problem

• Week 1, Jan. 7-11.
  More on permutations and combinations
  Sections 1.1, 1.2 and 1.4.
  • Class 1.1
    
  • Class 1.2 (pdf)
    
  • Class 1.3 (pdf)
    
    • Java applet imitating the Enigma machine.