At Southwestern, we are always striving to improve our commitment to diversity and inclusion, and that includes promoting the most inclusive learning environmennt possible. I view diversity as a resource and a strength of our community, and I want to make this course work for studeents of all identities. It is my intent to teach in a way that is as respectful and inclusive as possible with regard to: race, gender/gender identity, sexual orientation, socioeconomic status, age, cultural background, as well as any other identities that I have unintentionally missed. I am always open to your suggestions, comments, concerns, and constructive criticism on how I carry out this ethos.
At Southwestern we have stringent community standards for the treatment of others. I will not tolerate any hate speech, bullying, or harassment of any kind, and I will report any violations of our code of conduct to the Title IX office.
Please feel free to let me know what name and pronouns you prefer to go by, and/or how you want your name to be pronounced, and I will make sure to address you how you want to be addressed.
Southwestern University recognizes that it has students from a variety of religious and cultural traditions that have special days of observance or celebration that may take students out of their regular activities on certain days during the school year. Since the academic calendar does not always coincide with these days, the following policy is to be followed in order to facilitate student absences due to cultural and religious observances: As far in advance as possible, the student is expected to notify the professor(s) or instructor(s) of the class(es) to be missed. The student is expected to learn what assignments or exams are due or will be assigned on those dates and negotiate with the professor(s) or instructor(s) alternate times for fulfilling those requirements. Students should be prepared to fulfill the requirements prior to the class(es) to be missed.
The Center for Academic Success coordinates reasonable, individualized accommodations for students with documented disabilities (medical, learning and/or psychological). To receive formal accommodations, students must be registered with the Assistant Director of Academic Success, Prothro Suite 120, (512) 863-1536. If you have a disability for which you are or may be requesting an accommodation, the CAS will verify your disability and determine what reasonable accommodation(s) for this course are warranted, and then you should notify me of any required accommodations as soon as possible. Accommodations cannot be applied retroactively. It is the responsibility of any student seeking accommodation(s) for this course to present any necessary documentation to the instructor as early as possible.
Courses in the curriculum of the University are expressed in terms of credits. For courses that have a minimum class time of 150 minutes per week, students should expect to work outside of class a minimum of 2 and 1/2 hours per credit per week. For courses that have a minimum class time of 200 minutes per week, students should expect to work outside of class a minimum of 2 hours per credit per week. Class time and out-of-class work for courses yielding fewer than four credits will be expressed as some proportion of a four-credit course.
The official prerequisite for this courses is CSC 54-284 (Computer Science II), or equivalent. What this means is that I am assuming that have experience with computer programming, basic and intermediate algorithms, and runtime analysis. These concepts will make it easier for you to develop intuitions about the models of computation and the computability that we will cover in this course. Additionally, this course will include some programming assignments, but I won't devote lecture time towards teaching you computer programming. It is also advisable (but not required) to have taken CSC 54-384 (Discrete Mathematics), or any other math course that provides some exposure to proofs (especially proof by contradiction and induction), first order logic, sets, and graphs. If you are unsure about whether you have enough mathematical or programming background for this course, please feel free to reach out to me.
We will be using the following software in this course.
At Southwestern our learning management system is Moodle. You will submit all of your programming assignments on Moodle. I will use Moodle to keep track of grades, and you can use Moodle to see your current grade in the course. Finally, I will be using Moodle to make announcements. It is your responsibility to check your Southwestern email frequently and pay attention to announcements.
This course has three programming assignments. If you choose to complete them, I personally recommend using python3 - it will be easier to create the data structures that you need, and it will be easier for me to help you. But if you don't feel comfortable using python, you may write your code in java. No other programming languages will be allowed. You may use whatever programming environment you wish.
Top Hat is a platform that I will be using for for administering in-class practice questions. You should create an account on Top Hat and log into Top Hat at the start of every lecture. You may log in on a computer, on your phone (either in your phone's web browser, or using the Top Hat mobile app). When you create your Top Hat account, you may use any email of your choosing - either your Southwestern email or your personal email will work. Top Hat questions are not counted for a grade, meaning you can answer them freely without worrying about getting the question wrong.
Discord is an instant-messaging platform that we will be using for communication. I have created a Discord server dedicated to this class. You can use Discord to communicate and collaborate with your fellow classmates. If you ask a question on Discord, you may well get a response from one of your classmates faster than you would get a response if you were to email me. You can also message me privately on Discord if you like using Discord better than email. The Discord server can also serve as a space for informal communication and simply getting to know your classmates better. Note that there are some guidelines about asking for help through Discord - please review the academic integrity section carefully.
By default we will use the following grading cutoffs:
Part of your grade will be based on simply demonstrating that you are putting your best foot forward, and going above and beyond simply showing up for class. To measure this, I will use Moodle to track lecture attendance. At the start of every class, I will write an attendance code on the whiteboard. You will then to the attendance tab on Moodle, enter the code, and mark yourself present. If you show up to no later than five minutes afer the start of class, you will one (1) attendance point for that day. If you come to class five or more minutes late, you will receive 0.5 points. Othwerwise, you will receive 0 points. I do not excuse missed attendance points for any reason (even extenuating circumstances). If you need to miss class, you do not need to email me - simply remind yourself that because of the 110% scale, you can miss some classes without ruining your chance to get a high grade.
Additionally, as a part of your participation grade I ask that you complete a short syllabus quiz on Moodle, to help you be fully prepared for what to expect in this class. Finally, if we cover all of the required material fast enough, we may cover some special topics. Each of these will come with in-class assignments that contribute to your participation grade.
Every week you will complete an assignment based on material covered in the previous week's lecture. These assignments will involve designing different types of machines/expressions/grammars, describing algorithms, and writing proofs about what types of problems different machines can or can't solve. To succeed in this course, it will not be sufficient to simply get the correct answer on homeworks. You should aim to fully understand and digest the solution to each problem. A good rule of thumb is that you should aim to get to the point where you can reproduce the solution without referring to your writeup.
Each homework problem be graded as follows: you will get 50% for simply making a serious attempt, 80% for getting an answer that is mostly correct, and 100% for getting the answer fully correct. This means you have the freedom to make mistakes without getting severely penalized. If you are stuck on a problem, if you simply come to student hours I will give you enough help to get to that 80% threshold for free, and hints on how to finish off the problem.
Homework assignments are due on Tuesdays. I will grade them and return them in class the following Thursday. You will then have until the following Tuesday to re-work and re-submit your assignment. However, the catch is that when I grade reworks, each problem will be graded on a 0/50%/100% basis. This means that your grade may go down if you re-work an assignment insufficiently. This may seem harsh, but it is meant to ensure that you use re-works to learn from your mistakes and completely fill all of the cracks in your understanding. You will only be graded on the problems that you choose to re-work; you will retain your original grade for the problems that you don't re-work,
I reserve the right to take off points for any problem if your solution is too illegible for me to understand. For this reason I strongly encourage you to typeset your assignments.
All written assignments and reworks must be submitted in class at the start of lecture (10.00 am) on their due dates.
You will have three programming assignments in which you will put into practice some of concepts and techniques we learn about in class. Each part will build on the previous part, and by the end you will have written a regular expression parser that is not all that different from how the grep command line tool works. This is not a programming class, and as such you will not be graded on programming style. As long as your program is correct, you will get full points. That said, if you program with good style it will be easier for me to help you.
You may work on programming assignments alone, or with a partner. If you are working with a partner, you should both contribute equally to the project, and you should both fully understand all of the code that you submit. You are encouraged to use the pair-programming technique, in which one student will dictate code that the other student physically types.
When you write your code, external libraries are explicitly prohibited. You may NOT use any libraries or packages that are not part of the base languages. You may import packages or libraries that are part of the base language, however you may not import packages or libraries that are designed specifically for these problems (i.e., you should not import a regular expression parser even if it is part of the base language). If you are unsure, please contact the professor to get explicit permission for which libraries you may import. If you use libraries that I do not find acceptable, I reserve the right to ask you to resubmit the assignment without using that library.
I need some way to evaluate how well you yourself can understand the course material without the help of your peers and/or the instructional staff. That said, I won't make you take a timed exam. Instead, I will administer two take-home exams: a midterm, which will be available in the middle of the semester, and a final exam, which will be available during finals week. The exams will be untimed, open book, and open note. I am trusting all of you to complete the exam with integrity. The exams will not be cumulative; the mideterm will be based on the first six assignments, and the final will be based on the final six assignments (or whatever material we cover after the midterm).
The exams will test your conceptual understanding of the material. You should not expect to be able to simply regurgitate the solutions to problems we did class and on the homework. You will need to have a thorough understanding of the techniques we used to solve those problems.
You will complete a group project in which you explore an advanced topic in computability and complexity theory and draw connections with the other courses you take at Southwestern. The topic of the project is open-ended - I have provided some suggested directions, but you are ultimately free to pursue whatever direction you like. For the project, you will submit an initial proposal, and later a full report that details your explorations and the paideia connections that you made. On the last day of class, you will give a presentation on the topic you chose and a summary of your findings.
There will be some opportunities for extra credit. First, if and when time permits I will give students the chance to present solutions to homework problems in class. The first time you present a solution to a homework problem, you will get 5 extra credit points for that assignment. After that, you will get 1 point for each problem for which you present the solution. The catch is that you must be able to come up with a full solution without referring to your asssignment writeup. This is meant to incentivize you to not just complete the homework but understand the problems inside-out.
For each written assignmennt, you will receive 2 extra credit point for using LaTeX to typeset your solutions. This is a reward for putting extra effort into your assignments to make it easier for me to read, as well as an incentive to learn how to write documents like a professional mathematician. To typeset your work in LaTeX, and I strongly recommend using Overleaf (aka "Google docs for LaTeX") for typsetting your writeups. You can create a free account with your personal email, which will give you access to all the tools you need to write up assignments.
In this class you will have to draw several state diagrams. You have a few options for putting them into your LaTeX document. You can draw them by hand, take a picture or scan it, and insert the picture/scan into your document. You can also use software such as Flap.js or JFlap for drawing state diagrams. If you feel comfortable with python, you can use Dr. David Chiang's Theory of Computing Toolkit (tock). If you use these tools, please cite or acknowledge them in your writeup. Finally, you can actually draw diagrams from within Latex - this may seem intimidating at first but if you persevere you will see that this is actually the fastest and most convenient way to get state diagrams into your writeup. Here is a tutorial by Dr. David Chiang and Dr. Satyaki Sikdar on drawing state diagrams in Latex.
If you do not want to use LaTeX, you may typeset your assignments in some other software (such as MS Word or Google Docs). However, you will only receive 1 point of extra credit.
I always ask my students to give me feedback halfway through the term, and of course the university will have you fill out course evaluations at the end of the term. You will get extra credit for filling out these two feedback reports and helping me become a better teacher. Each of these surveys will be worth 0.5%, for a total of 1% extra credit.
We want you to succeed in this course, but we also want you to succeed with integrity. We want to make sure that you actually learn the material, so that the impact of the course doesn't disappear once the semester ends. We also want to make sure that every student has a fair chance to succeed, and isn't being taken advantage of by his or her peers. You worked very hard to get into a prestigious school like Southwestern, and without enforcing academic integrity that very prestige would quickly crumble.
In this course we expect students to adhere to Southwestern University's honor code. This means that you will complete your work honestly, with integrity, and support and environment of integrity within the class. While you may collaborate on homework, all work that you submit should reflect your own effort and understanding. A good rule of thumb is that you should be able to reproduce the solutions that you turn in without needing to refer to your writeup. Additionally, when you are solving reading or homework problems, you should not consult with students who are not in this class, nor should you consult any online resources other than the textbook or posted class materials. All honor code violations will be handled according to university guidelines. If it is your first violation, you and I will have the opportunity to come to a joint resolution. Otherwise, you will be referred to honor code hearing board for a hearing.
Note: When you are asking for help on Discord, you may ask general questions, but you should not post anything that essentially gives away the answer. I obviously don't have a hard and fast rule, but please use discretion.
I will accept late work; however, I will impose a late penalty of 10% for each day that an assignment is late. This means that while it is in your best interest to submit the assignment on time, you won't be penalized harshly if you take a extra time to get the assignment right. Note that I will round up to the next full day, so if you are just 5 minutes late, this will be rounded up to 1 full day and you will still lose 10%. This late penalty applies to all assigned work. There is, however, a way to avoid late penalties...
I understand that circumstances come up - family or medical situations, tough work in other classes, extracurricular commitments, your social life, etc. For this class, you have three (3) late tokens. A late token grants you the ability to turn in an assignment 24 hours late without incurring any penalties. Alternately, you may use a late token to reduce your late penalty - for example, if you turn in an assignment two days late, you may use a late token to reduce the penalty and lose 10% instead of 20%. You may use late tokens on any assignment (except for the paideia project or exams), and you may use multiple tokens on the same assignment. Late tokens are cannot be transferred from one student to another. Late tokens cannot be split into fractional tokens. When you want to use a late token, please send me an email - not a submission comment or a discord message; this helps me keep all of the late token requests in one place. In your email, tell me which assignment you want to use a late token on (and how many tokens you want to use). Note that I may not email you back, but you can verify that your late token request was accepted by going to Moodle and confirming that your due date for the assignment has been modified.
If you ever accidentally submit the wrong document, and you don't realize this until well after the deadline has passed, you can get a one-time "mulligan" to resubmit the assignment without penalty. However, you must use a late tokens to get a mulligan. Furthermore, you may only get one mulligan per semester. Please be careful and make sure you upload the right document when you submit an assignment! Some additional notes:
If you have a family or a medical emergency (including a mental health emergency), or if we encounter the literal apocalypse, I can grant you an extension without using a late token. In most circumstances, however, I will probably ask you to simply use a late token or take the late penalty. I reserve the right to request some sort of doctors or parent's note should you make such a request.
Grades can be appealed up to two weeks after they have been posted; no appeals will be considered after that time. Please note that the entire assignment will be regraded upon appeal.
To ensure the free and open discussion of ideas, students may not record classroom lectures, discussion and/or activities without the advance written permission of the instructor, and any such recording properly approved in advance can be used solely for the student's own private use.
All material provided through course websites is subject to copyright. This applies to class notes, slides, assignments, exams, solutions, project descriptions, etc. You are allowed (and expected!) to use all of the provided material for personal use. However, you are strictly prohibited from sharing the material with others in general and from posting the material on the web or other file sharing venues in particular.
At Southwestern, we are committed to providing instruction in the safest and most responsible manner possible. Beginning July 22, 2022, we will no longer require the use of face coverings in indoor spaces on campus, with the following exceptions: