Reza Davari PhD Student @ Mila and Concordia University AI enthusiast, currently focused on NLP, CV, and CL. A watermelon connoisseur. Based in Montreal, QC.

COMP-5361: Discrete Structures and Formal Languages

Assignment Submission Instructions

  • Theory assignments: You are expected to submit your solutions as PDF. Other formats will not be graded. There will be a grade associated with how neat, readable, and organized your assignment is, hence I recommend against submitting a handwritten solution. I suggest using LaTeX and submitting the PDF. If you are not familiar with LaTex, this is a good opportunity for you to caught up with it, since sooner or later you will have to use it. Here is a good tutorial for it. The other option would be using Microsoft Word, and submitting the PDF.
  • Programing assignments: You are expected to submit the following, using Google Colab:
    1. An ipython notebook: This file should contain all your code and explanations. Be sure that you are using python 3 not python 2. Assignments done in python 2 will not be graded. You can find an example of how your ipython notebook should look like here (Colab) and here (Github).
    2. A PDF file: This file is the PDF of the ipython notebook. It is very easy to create the PDF version. Search it online and if you could not find any solutions, you can ask me during the tutorials.

Slides

Lecture 1

This lecture covers the basics of python programming language. Note that you are required to submit your programming assignments as an ipython notebook by using Google Colab.

 

Lecture 2

This lecture covers Propositional Equivalences, Predeicates, and Quantifiers.

 

Lecture 3

This lecture covers Nested Quantifiers and Rules of Inference.

 

Lecture 4

This lecture covers an Introduction to Proofs and Proof Methods and Strategies.

 

Lecture 5

This lecture covers an Introduction to Set Theory and Set Operations.

 

Lecture 6

This lecture covers an Introduction to Functions.

 

Lecture 7

This lecture covers the Relations and Their Properties, Closures of Relations, Equivalence Relations, and Partial Orderings.

 

Lecture 8

This lecture covers an introduction to Regular Languages and Deterministic Finite Automata (DFA).

 

Lecture 9

This lecture covers an introduction to Nondeterministic Finite Automata (NFA) and the equivalence of NFA and DFA.

 

Lecture 10

This lecture covers the following topics,

  • Introsuction to Epsilon-NFA
  • Epsilon-Closure
  • Conversion of Epsilon-NFA to DFA
  • Introduction to Regular Expression
  • Generalized NFA
  • Conversion of Automata to Regular Expression
  • Conversion of Regular Expression to Automata

 

Assignments

Assignment 1

Due: February, 27th, 2019 @ 11:59PM

 

Assignment 2

Due: April, 1st, 2019 @ 11:59PM