Assignments and Evaluation
All students will be graded by the following components:| Component | Weight | Deadline | Submission |
|---|---|---|---|
| Assignment 1 | 5% | Thursday, January 26th by start of tutorial session | Gradescope |
| Assignment 2 | 5% | Thursday, February 9th by start of tutorial session | Gradescope |
| Assignment 3 | 5% | Thursday, March 2nd by start of tutorial session | Gradescope |
| Assignment 4 | 5% | Gradescope | |
| Assignment 5 | 5% | Thursday, April 6th by start of tutorial session | Gradescope |
| Midterm test | 25% | Thursday, February 16th, During Tutorial Session | Remote/online in OWL |
| Final Exam | 50% | Sunday, April 23rd, 10am-12pm. | Alumni hall AH15, in person |
Assignment Formatting Requirements
You must use a software tool for any diagrams involving automata. Hand-drawn automata diagrams will not be accepted.How to draw Finite State Machines
There are several options for drawing automata in software. Here are two.Option 1: LaTeX with TiKZ
LaTeX is a typesetting markup language. It has a bit of a learning curve, but if you want to produce documents like a real computer scientist or mathematician, this is for you.If you don't want to install LaTeX on your local machine, Overleaf provides a cloud-based interface, and is a common choice for many graduate students.
TiKZ is a LaTeX package for drawing diagrams. Here's a good tutorial on how to draw automata.
Option 2: Graphviz Online Editor
If you want the "easy-button" option, the online Graphviz editor is for you.Here's an example of a deterministic finite automaton on the alphabet {0,1} that accepts all strings that contain one or more 1's:
digraph finite_state_machine {
node [fontname="Helvetica,Arial,sans-serif"]
edge [fontname="Helvetica,Arial,sans-serif"]
rankdir=LR;
#Define final/accepting states
node [shape = doublecircle]; b;
node [shape = circle];
#Define initial state
start -> a;
#Define state transitions
a -> a [label = "0"];
a -> b [label = "1"];
b -> b [label = "0,1"];
}