Content Calendar

(6/27/24. This is still a draft. Subject to change. We will finalize all the decisions on the first day of class.)

Course Calendar

 

CSE 105 Summer session 1 2024

Theory of Computation

About the Course

Welcome to CSE105! 

In this course, we will explore what it means to be "computable". We begin with a very simple model of computation, and work our way to the most powerful, the Turing machine, named after Alan Turing, who formalized the notion of "algorithm" even before there were any physical computers. You'll also learn about the relationship of these models to some essential tools in a computer scientist's toolkit, such as regular expressions and context-free grammars. Finally, you'll develop your technical communication skills in writing formal arguments and proofs.

Prerequisites

Prerequisites are:

• CSE 12
• CSE 15L
• CSE 20 or MATH 109 or MATH 15A or MATH 31CH
• CSE 21 or MATH 100A or MATH 103A or MATH 154 or MATH 184 or MATH 184A

CSE 105 relies heavily on the theory of sets, in particular, languages (sets of strings), finite and infinite cardinalities, propositional logic and formal proofs. 

Learning Outcomes

Upon successful completion of this course, you will be able to:

• • Classify the computational complexity of a set of strings by determining whether it is regular, context-free, decidable, or undecidable.
  • Give examples of sets in each of these classes (and prove that they are in these classes).
  • Classify the computational complexity of a decision problem by translating it to a set of strings coding the problem.
  • Use and design automata both formally and informally, including DFA, NFA, PDA.
  • Deduce the language recognized by a machine or other formal description, including DFA, NFA, RegExp, PDA, CFG, TM.
  • Prove invariants of computational classes, e.g. the class of regular languages is closed under ....
  • Prove that certain models of computation are equivalent and translate between them algorithmically.
  • Apply classical techniques including pumping lemma, determinization, diagonalization, and reduction to analyze the complexity of languages and problems.

Course Logistics

Instructor and Course Staff

Name Role email Office hours Zoom link Miles Jones Instructor mej016@ucsd.edu Wednesday 11-1 Thursday 2:30-3:30 https://ucsd.zoom.us/j/99322083426

Office Hours and 1-1s

 

 

Course Resources

Textbooks:

Sipser, Michael   Introduction to the Theory of Computation, Third Edition (international)

This book is available at the Bookstore for under $20 and is also on reserve in the library. You will need the book to complete pre-class reading before each lecture period.

To brush up on proofs, use: Richard Hammack, Book of Proof, 2nd ed. (available for download here (Links to an external site.))

Software:

We recommend using JFLAP or flap.js (developed by UCSD students) to simulate DFAs, NFAs, PDAs, TMs,... Also, these are great ways to draw automata.

Refer to this page for more information:

Software Resources (JFLAP, flap.js)

 

Time and Location

Date	Day	Time	zoom link
Lecture	TU and TH	8:00-10:50 (A00 Miles Jones)    11:00-1:50 (B00 Miles Jones)	https://ucsd.zoom.us/j/99322083426
Discussion Section	Fridays	9-10:50 11-12:50
Final Exam	Final 8/3	Scheduled for 8:00am (A00) Scheduled for 11:00am (B00) Details TBD

Lectures:

•  via Zoom during the scheduled times 

  8:00-10:50 (A00 Miles Jones)   

  11:00-1:50 (B00 Miles Jones)

  (PT)

•  The lecture slides will be posted before class on the content calendar page of the canvas site.

•  You may interrupt lecture to ask questions, make comments or express doubts (you can use text or audio.)

•  All lectures will be recorded and posted for students to watch when they want.

•  You are not required to have a webcam, but microphones are encouraged, especially when we open the lecture to comments and discussion.

•  There will be a short review quiz given via canvas due on the following Monday at 11:59pm.

Coursework and Grades

Assignments/Coursework

Your grade will be based on the following:

• Homework
• 4 tests
• Review Quizzes
• Final Exam

Homeworks

Each week, homework assignments will help you work towards mastery of the course techniques

• Homework assignments may be done in groups of one to three CSE 105 students. You are encouraged to change groups between assignments. Problems should be solved together, not divided up between group members. These homeworks will be graded for correctness, including clear and precise explanations and justifications of all answers.

All homework submissions must be typed and turned in through Gradescope by 11:59pm on the day they are due. (For diagrams, please use JFLAP or flap.js) Illegible assignments will not be graded. We encourage you to use latex to typeset your homework.) Submit only one submission per group. One representative group member can upload the submission through their Gradescope account and then add the other group member(s) to the Gradescope submission: make sure to select their names when you "Add Group Members" to the submission; it's not enough to just list their names on the page. For step-by-step instructions on scanning and uploading your homework, see this handoutLinks to an external site..

Late homeworks will not be accepted. Submit early drafts well before the deadline to make sure partial work is graded.

For homework help, consult your textbook, class notes and lecture video, lecture slides, instructors, TAs, and tutors. Please follow these guidelines to avoid suspicion of academic integrity violation:

• It is forbidden to look or ask for answers to homework problems in other texts or sources, including the internet. If you are suspected of this then you will be reported to the academic integrity office.
• Students are encouraged to collaborate on homework assignments. You may work in groups of up to three students. Your group will submit one assignment and gradescope will give you the opportunity to add all of your group members to the assignment. Groups do not have to be the same people for every assignment. You can change group members any time.
• If you are discussing problems with students outside of your group, please only share hints and basic techniques. DO NOT share your answers or allow other students to copy your written work. The bottom line is to submit YOUR OWN work. If we find that your work is too similar to another group's then you may be suspected of an academic integrity violation.
• You may not collaborate with anyone outside of the class. (You are not permitted to ask homework questions to message boards or websites such as chegg.)

Only post about homework questions publicly on Piazza if you suspect a typo in the assignment, or if you don't understand what the question is asking you to do. Other questions are best addressed in office hours or via private piazza post.

Homework solutions will be posted on Piazza after the submission deadline.

Standards for evaluation

Your assignments in this class will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning (unless otherwise stated). Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound. This means that unless it says: "no justification necessary" then we expect a written justification.

 

Review Quizzes

There will be a review quiz due the following Monday.

This adds up to 5 total review quizzes.

You will have until the following Monday to complete the review quizzes of the preceding week.

You will have unlimited attempts on each quiz.

Each review quiz is worth 1 point. You will get whatever fraction of 1 based on how well you did on the review quiz.

In order to get the full 4% points for review quizzes, you must earn 4 points.

(If you do all 5 review quizzes, you still only get 4 points.)

Tests: 

•  four tests
•  They will all be canvas quizzes 
•  No make-up tests.
•  Each test window will be open for 24 hours (on Wednesday) 12:01am wednesday morning until 11:59pm wednesday night.
•  You will have 60 minutes to complete each test.
•  The tests are open books, open notes, open calculators, open jflap/flap-js. 
•  You may not share information about the exam with others, take the exam in someone else's name, or ask anyone for prior knowledge about the exam.
• Re-test:
  • You will have the opportunity to do a retest and earn back up to 1/3 of the points you missed on the test.

Final Exam

• Details TBD

Grading

Course Policies

Academic Integrity

In this course we expect students to adhere to the UC San Diego Integrity of Scholarship Policy.   This means that you will complete your work honestly, with integrity, and support and environment of integrity within the class for which you are tutoring.  Some examples of specific ways this policy applies to CSE 20 include:

• Do not discuss solutions to homework problems with people besides your homework partner (except during office hours, with the instructional team).
• Do not share written solutions with other groups.
• Do not collaborate or copy exams.
• Follow the golden rule for AI:  Always give credit for any outside help on any assignment, except for those whose job it is to help you (Instructors, TAs, tutors, the textbook, and class handouts)
• You should not attempt to search for homework solutions or exam solutions online or in sources outside of the course content. (Example: you should not consult content from CSE 105 of past quarters.) If you accidentally stumble upon a homework solution in such an outside source you should cite it in your homework solution. If your solution proves to be too similar to the cited one, you may lose credit on the problem, however failure to cite the other solution will be treated as academic dishonesty.
• Note on ChatGPT and other GenAI software: Inputting homework or exam questions into ChatGPT or any other GenAI software and turning in the answer that is given is considered an Academic integrity violation. As with any other resource, I expect your words and work to be your own.
• Please let me know if you have any questions about these guidelines and if you are unsure if something is considered a violation, you can always ask.

 

Collaboration Policy

For homework collaboration policy, see the paragraph above.

For the exams, you are not permitted to collaborate with anyone else (including people from outside of the class like message boards or chegg.)  We will give you the opportunity to ask questions via private piazza post to the teaching staff during exams.

For quizzes, you are not permitted to share solutions but you are permitted to help each other with hints and strategies.

Regrade Policy

Please be prompt (three days) in reporting any errors in the grading of your work, or in the recording of your grade. All grades become permanent three days after they are recorded. Regrade requests for homework assignments must be made on Gradescope. Please note that by requesting a regrade for a problem, it will be completely regraded and your grade may go up or down.

Late or Missed Assignments/Missed Exam Policy

Late Homework:
You may hand in your homework up to 24 hours late with a penalty of 1 point.

Exams:
Other than extenuating circumstances, there is no credit for late or missed exams.

Technology Policy

For homework assignments and for exams, you are permitted to use calculators, online calculators such as wolfram alpha, programming languages and JFLAP or flap.js to help you with your answers.

Outside Tutoring

Individuals are not permitted to approach students to offer services of any kind in exchange for pay,  including tutoring services.  This is considered solicitation for business and is strictly prohibited by University policy.

Resources for Students

Getting Help

We provide many office hours and 1-1 sessions. Please use them. This class can be challenging if you don't engage with the teaching staff. The office hours are TBD.

 

The IDEA Engineering Student Center, located just off the lobby of Jacobs Hall, is a hub for student engagement, academic enrichment, personal/professional development, leadership, community involvement, and a respectful learning environment for all.  The Center offers a variety of programs, listed in the IDEA Center Facebook page at http://www.facebook.com/ucsdidea/ (you are welcome to Like this page!) and the Center web site at http://idea.ucsd.edu/.  The IDEA Center programs support both undergraduate students and graduate students.

Diversity and Inclusion

We are committed to fostering a learning environment for this course that supports a diversity of thoughts, perspectives and experiences, and respects your identities (including race, ethnicity, heritage, gender, sex, class, sexuality, religion, ability, age, educational background, etc.).  Our goal is to create a diverse and inclusive learning environment where all students feel comfortable and can thrive. 

 

Our instructional staff will make a concerted effort to be welcoming and inclusive to the wide diversity of students in this course.  If there is a way we can make you feel more included please let one of the course staff know, either in person, via email/discussion board, or even in a note under the door.  Our learning about diverse perspectives and identities is an ongoing process, and we welcome your perspectives and input. 

 

We also expect that you, as a student in this course, will honor and respect your classmates, abiding by the UCSD Principles of Community (https://ucsd.edu/about/principles.html).  Please understand that others’ backgrounds, perspectives and experiences may be different than your own, and help us to build an environment where everyone is respected and feels comfortable.

If you experience any sort of harassment or discrimination, please contact the instructor as soon as possible.   If you prefer to speak with someone outside of the course, please contact the Office of Prevention of Harassment and Discrimination: https://ophd.ucsd.edu/.  

Students with Disabilities

We aim to create an environment in which all students can succeed in this course.  If you have a disability, please contact the Office for Students with Disability (OSD), which is located in University Center 202 behind Center Hall, to discuss appropriate accommodations right away.  We will work to provide you with the accommodations you need, but you must first provide a current Authorization for Accommodation (AFA) letter issued by the OSD.  You are required to present their AFA letters to Faculty (please make arrangements to contact me privately) and to the OSD Liaison in the department in advance so that accommodations may be arranged.

Basic Needs/Food Insecurities

If you are experiencing any basic needs insecurities (food, housing, financial resources), there are resources available on campus to help, including The Hub and the Triton Food Pantry.  Please visit http://thehub.ucsd.edu/ for more information.