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-335: Introduction to Theoretical Computer Science

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.

Slides

Lecture 1

This lecture covers examples from Sets, Functions, Relations, and Proof Techniques.

 

Lecture 2

This lecture covers examples from Regular Languages and DFA's.

 

Lecture 3

This lecture covers examples from conversion of NFA's to DFA's.

 

Lecture 4

This lecture covers examples from Regular Expressions (RegEx) and conversion of FA's to RegEx.

 

Lecture 5

This lecture covers examples from conversion of RegEx and NFA to CFG as well as Regular Grammers to NFA.

 

Lecture 6

This lecture covers examples from Pumping Lemma on Regular Languages.

 

Lecture 7

This lecture covers examples from Contex Context Free Grammars.

 

Lecture 8

This lecture covers examples from Parse Trees (Left Most and Right Most), Simplification of CFGs, and Chomsky Normal forms.

 

Lecture 9

This lecture covers examples from Ambiguous Grammers and their disambiguation.

 

Lecture 10

This lecture covers examples from Pushdown Automata design.

 

Lecture 11

This lecture covers examples from conversions of CFGs to PDAs.

 

Lecture 12

This lecture covers examples of Pumping Lemma for CFG.

 

Lecture 13

This lecture covers examples from Turing Machines.