Labs
Each lecture session is complemented by a lab/discussion session led by the graduate teaching assitants. 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 |
|---|---|---|---|
| BYA | 10:00 - 10:50 a.m. | 114 Transportation Building | Haochen Shen |
| BYB | 11:00 - 11:50 a.m. | 2015 ECE Building | Haoyuan You |
| BYC | 12:00 - 12:50 a.m. | 2015 ECE Building | Tue Do |
| BYE | 01:00 - 01:50 p.m. | 2015 ECE Building | Jingjie He |
| BYD | 03:00 - 03:50 p.m. | 2015 ECE Building | Owen Xu |
| CSP | Asynchronous | Online | Owen Xu |
Detailed information:
| Date | Topic | Lab | Solution |
|---|---|---|---|
| 01/22 | Lab 01 Mathematical preliminaries |
Lab 01 | Sol |
| 01/24 | Lab 02 Proof techniques and intro to languages |
Lab 02 | Sol |
| 01/29 | Lab 03 Intro to languages and DFAs |
Lab 03 | Sol |
| 01/31 | Lab 04 DFAs & regular languages |
Lab 04 | Sol |
| 02/05 | Lab 05 Language transformations & NFAs |
Lab 05 | Sol |
| 02/07 | Lab 06 Regular expressions & equivalences (DFAs/NFAs/RegExs) |
Lab 06 | Sol |
| 02/12 | Rev 01 Midterm 1 review |
||
| 02/14 | Lab 07 Non-regularity & fooling sets |
Lab 07 | Sol |
| 02/19 | Lab 08 CFGs and context free languages |
Lab 08 | Sol |
| 02/21 | Lab 09 Pushdown automata |
Lab 09 | Sol |
| 02/26 | Lab 10 Turing machines |
Lab 10 | Sol |
| 02/28 | Lab 11 Univeral Turing machines |
Lab 11 | Sol |
| 03/05 | Lab 12 Recursion & reductions |
Lab 12 | Sol |
| 03/07 | Lab 13 Divide & conquer algorithms |
Lab 13 | Sol |
| 03/12 | Rev 02 Midterm 2 review |
||
| 03/14 | Lab 14 Backtracking |
Lab 14 | Sol |
| 03/26 | Lab 15 Dynamic programming I |
Lab 15 | Sol |
| 03/28 | Lab 16 Dynamic programming II |
Lab 16 | Sol |
| 04/02 | Lab 17 Graphs & basic search |
Lab 17 | Sol |
| 04/04 | Lab 18 Directed graphs |
Lab 18 | Sol |
| 04/09 | Lab 19 Shortest paths I |
Lab 19 | Sol |
| 04/11 | Rev 03 Midterm 3 review |
||
| 04/16 | Lab 20 Shortest Paths II |
Lab 20 | Sol |
| 04/18 | Lab 21 Minimum spanning trees |
Lab 21 | Sol |
| 04/23 | Lab 22 Reductions |
Lab 22 | Sol |
| 04/25 | Lab 23 NP-complete problems and reductions I |
Lab 23 | Sol |
| 04/30 | Lab 24 NP-complete problems and reductions II |
Lab 24 | Sol |
| 05/02 | Rev 04 Midterm 4 review |
||
| 05/07 | Lab 25 Decidability |
Lab 25 | Sol |