Professor: Pablo Frank Bolton (pfrank at smith)
Research interests: Human-Robot Interaction, Robotic Perception, STEM education
Class Schedule:

• Monday, Wednesday, Friday 10:50 – 12:05 Ford 342

Contact for Class stuff: Use Slack (fastest), office hours (most detailed), or can also email me (slowest).

Office Hours:
Provisional: Wednesday and Friday, 1:30 to 2:30 PM (Ford 316 or Chemistry nook)
Office Hour Rules:
I like office hours! so please come and chat with me about how your doing and to clarify concepts from the class. That said, and since I have a limited amount of time for OHs, it is best if we're a bit organized:

• Try before asking: Try the problem or research the concept you have an issue with (at least a little) before asking about it. That let's you get a better view of the problem and often leads to finding the solution.



• Check Slack: Check the thread for the lecture/assignment in which you have an issue and see if someone already asked/answered what you need help with


• Bring questions prepared: Once you know what you need help with, it is best to write down the questions you want to ask and to have the materials ready (slides/assignment/...)


• Note: if you have a non-conceptual question and you wanna ask/chat about it, you are also welcome!... no need to "prep questions" in that case.

TAs:
Office Hours (Provisional):

• Mariem: Sunday 1-3; Location TBD
• Jingwen: Monday 7-9 and Tuesday 7-9; Location TBD

Objectives

This course provides a challenging introduction to some of the core theoretical ideas that underlie the computational sciences. The objective of this course is:

to develop an understanding of "computer science outside the box" -- to begin to think of CS not only as the science of computers, but as the science of what can be computed.

• Demonstrate familiarity with key concepts in logic, proofs, and the definitions of multiple computational paradigms.
• Explain core computer science topics, such as automata, grammars, Turing machines, complexity, and more
• Propose algorithms in order to transform and analyze problems using the tools and structures we will develop in class

Class Structure - What type of work do we do and when do we do it?

Content:
We'll begin with very simple computational machinery (automata and finite state machines, regular sets, context-free languages).

We'll then move on to Turing machines and computability, efficient algorithms and reducibility, NP-completeness, the P versus NP problem, the power of randomness.

We'll draw on real world examples from the domains of cryptography, machine learning, and more.

Finally, we'll talk about the present and future of computing theory, with potential topics including interactive proofs, quantum computing and the physical limits of computation.

Class mechanics:
We will discuss concepts using blackboard annotations as well as proyected presentations and animations;

Readings will be assigned and should be completed before each designated lecture.
This will help prepare you for the day's discussion.

Friday classes will be used to practice the techniques seen during the week by solving exercises and discussing subjects that remain confusing. Note: class participation is important, as the class will include discussion and debate about many of these topics.

Assignments - When and what are they about?

There will be 8 problem sets assigned during the semester.

These problem sets will often ask you to prove theorems, but it is more important to demonstrate understanding than to employ rigor for rigor's sake. For example: a brief description of an algorithm including an illustrative diagram is better than complicated spaghetti code. Additionally, a clear explanation of how you tried to solve a problem and were unsuccessful will receive partial credit.

Clarity, conciseness, and completeness are the qualities of the best answers

All assignment submissions must be in PDF format, and must be organized and legible (typed is preferable). A LaTeX template will be available for typesetting your assignments.

Prerequisites:

• CSC111 and MTH153. The latter may be taken concurrently with permission of the instructor. Most importantly, I will assume you have basic "mathematical maturity": i.e., that you are comfortable both reading and writing mathematical proofs.

Responsibilities - Students must

• Attendance: You should attend all classes unless you have a valid excuse (see "Covid-19 rules", under "Grading").
  I will use Google forms to take attendance/run quizzes at least once a week. Unexcused missed classes mean a loss of points in "Attendance and Participation".
• Interact, ask questions, and generally participate in class discussions.
• Complete the assigned preliminary readings and activities before each lecture.
• Complete problems individually unless working in a group as specified on the assignment in which case you can work only with those group members. We do plagiarism detection so don't throw the course away.
• When working with a group, it is essential that each group member pull their own weight, but also that other group members let them do so!

Course Philosophies

Throughout the class, students should focus on adhering to the following general tenets:

• Try it! -- A common question is "will this work?", or "what will happen in this case?". The only reasonable answer is "try it and see!".
• It is OK to make mistakes! -- an error is one learned lesson. After trying something, having that fail is as much a datapoint as a correct path.
  Note that we usually want correct paths after exploring and making a lot of errors so keep looking!
• Ask for help when stuck! -- if you have 1) tried multiple paths and 2) you have explored the problem and made many mistakes, and you are still stuck, please seek assistance! that's what were here for!
  Believe it or not, we actually like teaching and helping you make progress.
• Know your sources, and use them! -- We'll use Sipser's book and you can look for other online courses to support your learning. Be careful with online materials (like tutorials or articles): they are not necessarily correct! Learn to use your sources productively to help to make progress.
• Be proud of your submissions! -- Clarity above all. Use proper styling, simplify it where you can to make it more understandable, and comment it where appropriate. You're taking part in an art that most often is shared, and it matters if others can understand your work!
• Planning is the best problem-solving tool! -- You should not jump into writing solutions or writing code before thinking about it thoroughly. Design your solutions by breaking them into logical parts that make sense independently and when put together to make an argument.
• Practice methodical analysis! -- Spend time "stepping though" your proofs and solutions, statement by statement to understand the logic behind them, and why it is logically sound (or why it was marked as incorrect). Do not submit a solution that you don't fully understand with the hope of flying under the radar. We look deeply at your submissions to gauge your level of understanding.

There is no required textbook for the course. However, there are several recommended books that some students may find helpful:

• Sipser, Michael. Introduction to the Theory of Computation. Course Technology, 2006. ISBN: 9780534950972. (Note: there is a newer edition available, but it is not necessary - the 2nd edition will suffice.)
• Moore, Cristopher and Stephan Mertens. The Nature of Computation. Oxford University Press, 2011. ISBN: 9780199233212.
• Arora, Sanjeev and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. ISBN: 9780521424264.
• Critchlow, Carol and David Eck. Foundations of Computation. Available free online.

• Webpage for the course (here) Class Info
• Moodle: Course full name "CSC250: Theory of Computation"
  Course Short name "CSC250-01_202203"; Category: Spring 2022
• Slack: You'll receive an invitation to the workspace: smith-s22-csc250-01
• For a detailed view of the Lectures and Activities, go to Schedule

Grade Calculation:

• Attendance and Participation : 10%
• Homework Assignments (problem sets): 60%
• Test 1/Assignment: 15%
• Test 2/Assignment: 15%

Late Submissions:

• If you have a justification (like a medical one), you get an extension depending on what makes most sense.


• If you are simply overwhelmed and simply need more time:
  1. Each student gets 1 free 2-day extension, no questions asked. but you must let me know at least 24 hours before the due date/time
  2. After that, you may request 1-day extensions on a by-case basis; Do not take these for granted, they will be awarded sparingly.
  
  

Note: Submitting 1 second late is the same as a full day late. Plan ahead and submit early.

Points-back policies:

We will have two ways of alleviating grade pressure:

1. Discarding the bad: the worst in the first few homework assignments (all but the last 2) will be discarded.


2. HW points back: Students that want to obtain (half of he lost) points back for a given HW assignment, can choose to do the following:
   
   1. Correct the errors on a new pdf using the feedback/OHs/TAs-help, etc
   2. Make an appointment with me to show me the updates, which you (the whole team) must explain
   3. Note: you must do this within 4 days of obtaining your grade/feedback

Collaborations:

Students are strongly encouraged to form study groups and to collaborate on problem sets, though each student will be required to write up and submit their solutions independently. The following information is required for all submitted work:

1. The names of all collaborating students be listed at the top of the submission (I do not recommend groups larger than 3). If you worked alone, please state: "I did not collaborate with anyone on this assignment."
2. A "References" section, with in-line citations to any resources you used. Citations should include page numbers (if a printed resource) or a direct URL (if an online resource). If you did not use any resources in completing the assignment, please state: "I did not utilize any external resources in completing this assignment."

Accommodations:

As individuals, we learn in different ways. I try to vary the activities used during the course to suit a variety of learning patterns, and I am always open for suggestions. Please come talk to me if you have an idea that will make the course more accessible to you and/or other students. If you need special accommodation, like extended exam time, please submit requests for accommodations in writing with proof of College support from the Office of Disabilities Service within the first two weeks of class. Let me know if you need help with this process.

Team assignments require collaboration amidst each team, but no collaboration between teams is permitted. If you did not work in a team then you are not allowed to collaborate on the homework assignments. We use software to compare submissions, so please don't risk it. If you're having significant trouble with an assignment, please contact me.

Please check the Student Handbook to see the rules for Academic Integrity.

Just as you can do a google search for code online, it is trivial for us to do the same. If you feel pressured about an assignment, please come see me instead of cheating.

The following are resources available to you that may provide assistance and support during the semester.
They provide help for learning, mental health, and wellness.

Learning resources:

• Spinelli Center for Quantitative Learning
• Jacobson Center for Writing, Teaching, and Learning
• Teaching, Learning and Research Librarians

Mental Health and Wellness resources:

• Crisis Resources
• Counseling Services
• Wellness

Additional support resources:

• Gender Identity and Expression Resources
• Report sexual misconduct and other forms of discrimination

We will add a link inside Moodle to an anonymous feedback form so you can let us know if there is anything getting in the way of your learning.