Labs
Each lecture session is complemented by a lab/discussion session led by the graduate teaching assistants. A typical lab session involves reviewing the lecture material and solving problems. Labs are a crucial component of this course, providing an opportunity to solidify your understanding. Furthermore, exam review sessions will be held during some labs.
Schedule:
Five different lab sessions will be held on Wednesdays and Fridays. The time and location are:
| Lab session | Time | Location | Graduate TA |
|---|---|---|---|
| BYB | 11:00 - 11:50 a.m. | 2015 ECE Building | Jingjie He |
| BYC | 12:00 - 12:50 p.m. | 2015 ECE Building | Rishik Sathua |
| BYD | 01:00 - 01:50 a.m. | 2015 ECE Building | Owen Xu |
| BYE | 02:00 - 02:50 p.m. | 2015 ECE Building | Yuqi Wen |
| BYF | 03:00 - 03:50 p.m. | 2015 ECE Building | Deep Goradia |
Detailed information:
| Date | Topic | Lab | Solution |
|---|---|---|---|
| 01/21 | Lab 01 Mathematical preliminaries |
Lab 01 | Sol |
| 01/23 | Lab 02 Proof techniques and intro to languages |
Lab 02 | Sol |
| 01/28 | Lab 03 Intro to languages and DFAs |
Lab 03 | Sol |
| 01/30 | Lab 04 Regular languages & NFAs |
Lab 04 | Sol |
| 02/04 | Lab 05 NFAs and & language transformations |
Lab 05 | Sol |
| 02/06 | Lab 06 Regular expressions & equivalences (DFAs/NFAs/RegExs) |
Lab 06 | Sol |
| 02/11 | Rev 01 Midterm 1 review |
||
| 02/13 | Lab 07 Non-regularity & fooling sets |
Lab 07 | Sol |
| 02/18 | Lab 08 CFGs and context free languages |
Lab 08 | Sol |
| 02/20 | Lab 09 Pushdown automata |
Lab 09 | Sol |
| 02/25 | Lab 10 Turing machines |
Lab 10 | Sol |
| 02/27 | Lab 11 Univeral Turing machines |
Lab 11 | Sol |
| 03/04 | Lab 12 Recursion & reductions |
Lab 12 | Sol |
| 03/06 | Lab 13 Divide & conquer algorithms |
Lab 13 | Sol |
| 03/11 | Rev 02 Midterm 2 review |
||
| 03/13 | Lab 14 Backtracking |
Lab 14 | Sol |
| 03/25 | Lab 15 Dynamic programming I |
Lab 15 | Sol |
| 03/27 | Lab 16 Dynamic programming II |
Lab 16 | Sol |
| 04/01 | Lab 17 Graphs & basic search |
Lab 17 | Sol |
| 04/03 | Lab 18 Directed graphs |
Lab 18 | Sol |
| 04/08 | Lab 19 Shortest paths I |
Lab 19 | Sol |
| 04/10 | Rev 03 Midterm 3 review |
||
| 04/15 | Lab 20 Shortest Paths II |
Lab 20 | Sol |
| 04/17 | Lab 21 Minimum spanning trees |
Lab 21 | Sol |
| 04/22 | Lab 22 Reductions |
Lab 22 | Sol |
| 04/24 | Lab 23 NP-complete problems and reductions I |
Lab 23 | Sol |
| 04/29 | Lab 24 NP-complete problems and reductions II |
Lab 24 | Sol |
| 05/01 | Rev 04 Midterm 4 review |
||
| 05/06 | Lab 25 Decidability |
Lab 25 | Sol |