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.

Tutorial 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 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 Grammars 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.