Jeanne Ferrante | |
Office Hours | |
When: | Wednesday 9:30 to 11:30 am (updates will be posted on the Google calendar above) |
Where: | EBU3b (CSE) 3102 |
Contact | |
To contact the CSE 105 instructional team with any non-confidential question, please post your question on Piazza. |
TAs | |
Dhivya Anandakrishnan | |
Radheshyam Balasundaram | |
Juliana Curtis | |
Nathan Speidel | |
Sandy Wiraatmadja (Head TA) |
Tutors | |
Madhu Krishnan | |
Ben Levin | |
Maya Nyayapati | |
Asha Camper Singh | |
Edward Wong | |
Alex Zhu |
Contact | |
To contact the CSE 105 instructional team, please post any non-confidential question on Piazza. | |
Office hours will be posted on Google calendar above. |
Welcome to CSE 105!
This course addresses fundamental questions about computing:
It's a lot of fun to look at these basic questions, and you will be picking up some of the essential skills of a computer scientist, such as writing mathematically sound and clear arguments, from formal proofs to more informal explanations.
This website, Ted, and our Piazza site accessible through Ted, will provide you with the information you need to thrive in the class, so please check all of them often for important information, announcements, and course materials.
In this course, we will undertake an exploration of 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" in this last model. 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.
Please click here for a course description as given in the undergraduate course listing.
Course grades will be computed using the following weights.
Grading | |
Midterm Exams and Final Exam | 70% |
Homework | 20% |
Class Participation | 5% |
Reading quizzes | 5% |
There will be two specially scheduled midterm exams outside of the usual lecture time and the usual lecture room. No makeup tests will be given. You should go to the examination room for your class section. No electronic devices, books, or written notes are allowed for these examinations. These exams will include all material covered up to the day of the exam, unless otherwise noted.
The final exam will cover all material from the whole quarter, though more emphasis will be given to material covered after the second exam.
It is highly recommended that you start preparing for an exam at least a week beforehand by reviewing class notes, the relevant textbook chapters, and most importantly, doing homework and similar problems. Each exam will include one problem taken directly from, and a second, additional problem similar to, the homework problems from the two most recent assignments to the exam.
There will be no make-up exams. The weighting of the exam scores will be
You must have a passing score (60%) on the final exam to pass the course.
There will be one online review self-test assignment (which counts as part of your participation), and six graded homework assignments. Homework assignments and solutions will be available on Ted. Depending on staff support, one or more of the homework problems on a graded assignment may be graded only for completeness and fair effort. When computing the homework portion of the course grade, the lowest of your six graded homework scores will be dropped and the average computed using the remaining five assignments.
Many students find it challenging to discern what the proper level of detail to be included is (i.e., how to be "concise but not lacking critical details"). The best way to acquire this skill is through repeated iterations of practice and feedback on your work, as well as being exposed to others' proofs to sharpen your proof reading skills.
In order to get peer feedback, students are allowed to solve and write up all homework assignments in groups of size one to three . Your homework partners can be in either class section. All names of the group should appear on the assignment, and all will get the same score on the assignment.
Members of a group are responsible for all parts of any assignment with their names on it. Problems should be solved by the group, and not divided up between group members. It is highly recommended that each member of the group try solving the problems individually on their own, before meeting as a group. Each member of a group should participate in discussions about each problem. Even proof-reading a solution of another student in your group counts as participation.
To succeed in this class, it is important that each student in a group be able to write and not just understand the solutions. Understanding a proof is very different from being able to write a proof yourself. To encourage full homework participation by all members, each exam will include one problem taken directly from, and a second, additional problem similar to, the homework problems from the two most recent assignments prior to the exam.
Students should not look for answers to homework problems in other texts (i.e., other than the course text and class notes) or other sources (e.g. wikipedia, Internet, discussion groups). Not giving an acknowledgment of any other source you use is academic dishonesty, and will be treated as such. We'll be using TurnItIn via Ted for homework submission, which also checks for potential plagiarism. As well, students should not share answers to homework problems with others or on the internet.
There will be frequent opportunities for structured active participation during during lecture, discussion section, and online (solving problems, responding with clickers, critiquing proofs, Piazza participation, surveys, and group discussion), in which everyone is expected to participate. Additionally, alerting the instructor, TAs, and tutors when you are confused, lost, didn't hear something, or otherwise in need of additional explanation is strongly encouraged. For this reason, you will be required to have an iClicker for this course, and to bring it to lecture each day. For the same reason, do not use electronic media in class without explicit permission.
Reading the textbook selectively in advance to get an overview of the definitions and theorems before they are discussed in class is an important tool for learning. To encourage you to do this, there will be 10 short online reading quizzes on Ted that will be graded on the correctness of your answers. If you do the suggested preparation, the reading quiz will be easy, and you will get an excellent grade nearly every time.
To receive credit for each quiz, you should read the relevant sections of the textbook and then complete and submit the quiz by the due time on the due date. Reading quizzes are open book, and you have as much time as you want, as long as you submit by the due date and time. Reading quizzes should be completed individually . We will drop your lowest score and take the average score for the remaining reading quizzes. Please note that reading quizzes are not scheduled before every class; you are responsible for checking the schedule for reading quiz due dates. There will be no makeups for missed reading quizzes.
You are required to have an iClicker for this course, and to bring it to lecture each day. You must register your iClickers on Ted.
Clicker discussion questions in lecture will be graded for participation only and not correctness of the response, unless otherwise noted. Full credit for clicker points for a given day will be awarded for clicking in at least 80/% of the time that day. Your four lowest lecture participation days will be automatically dropped. Forgetting your clicker counts as missing a class, so please remember to bring it!
After your weighted average is calculated, final letter grades will be assigned no stricter than the following grading scale, except that you must get a passing grade (60 % ) on the final exam in order to pass the course (regardless of total percentage):
A | B | C | D | F |
90 - 100 | 80 - 89.9 | 70 - 79.9 | 60 - 69.9 | < 60 |
We may adjust the above scale to be more lenient (depending on the overall class performance), but we guarantee that we will not adjust the scale to make it harder to get a better grade. We emphasize that you must pass the final exam in order to pass the course.
The guidelines for this class may be different from other courses and professors, and may ban things that you personally don't think of as "cheating." If you have any questions about what is acceptable or not under this class' guidelines, please ask before it is too late. UCSD's policy is that "I didn't know" is not an excuse.
CSE 105 Academic Integrity policy:
The Jacobs School of Engineering code of Academic Integrity, the UCSD Policy on Integrity of Scholarship (put in link) and this syllabus list some of the standards by which you are expected to complete your academic work, but your good ethical judgment (or asking us for advice) is also expected as we cannot list every behavior that is unethical or not in the spirit of academic integrity. You should make yourself aware of what is and is not acceptable by reading these documents. Ignorance of the rules will not excuse you from any violations. If you have any doubt as to whether a conversation you wish to have with someone or other activity might cross the line, please stop and go to the discussion forum on Piazza, wher, e we will be happy to help you, and where the integrity of the discussion can be monitored for everyone's protection.
Academic integrity violations will be taken seriously and reported immediately. If you are suspected of not following the guidelines, your case will be referred to the Dean of your college. Consequences may include an F in the course, no matter how small the affected assignment or exam question. Be aware that TritonLink will block you from dropping the course if your case is in process with the Dean, so you will not be able to avoid consequences by dropping.
The textbook for this course is
There is a later third edition of Sipser's book, but we are using the second edition because it has everything we need, and is less expensive. A "second international edition" is available at the bookstore, and is fine for our use as well.
An iClicker is also required, and is available at the bookstore. You should register your iclicker on Ted, if you have not done so already, and make sure you bring it to every class.
If you want more background on writing proofs, the following textbook is recommended: Richard Hammack, Book of Proof, 2nd ed. (available for download here , as well as print version through Amazon)
LaTeX is a very commonly used typesetting language for computer science and mathematics. We use it to typeset the homework assignments, and we encourage you to use it for typing your solutions. We will provide the .tex source files of homework assignments, and a class file to use to get you started. If you have never used LaTeX, we recommend the Cloud resources below.
Both are reasonably easy to use and require registration.
Basic installation and configuration (for those who already have Java Virtual Machine installed)
NOTE: you should be able to install JFLAP on systems with JVM even if you don't have install/Administrator rights):
If you don't already have JVM (Java Virtual Machine) installed on your computer, you'll need to get it in order to run JFLAP. You will need install/Administrator rights to do this. To install:
Date | Time | Location | |
Lecture A00 | TuTh | 9:30am - 10:50am | PCYNH 106 |
Midterm Exam 1(section A) | Wed April 22, 2015 | 6:30pm - 7:50pm | CENTR 119 |
Midterm Exam 2(section A) | Wed May 13, 2015 | 6:30pm - 7:50pm | CENTR 119 |
Final Exam (section A) | Sat Jun 6, 2015 | 11:30am - 2:29pm | TBA |
Lecture B00 | TuTh | 12:30pm - 1:50pm | PCYNH 106 |
Midterm Exam 1(section B) | Wed April 22, 2015 | 6:30pm - 7:50pm | CENTR 101 |
Midterm Exam 2(section B) | Wed May 13, 2015 | 6:30pm - 7:50pm | CENTR 101 |
Final Exam (section B) | Sat Jun 6, 2015 | 11:30am - 2:29pm | TBA |
Discussion 1 (open to all) | Wed | 2:00pm - 2:50pm | HSS 1330 |
Discussion 2 (open to all) | Wed | 3:00pm - 3:50pm | HSS 1330 |
Discussion 3 (open to all) | Fri | 8:00am - 8:50am | Center 119 |
Discussion 4 (open to all) | Fri | 9:00am - 9:50am | Center 119 |
There are 2 sections of the class, with joint homework, discussion sections, and examinations. You should go to the classroom and exam room for your section. You may go to any discussion section(s),as long as we do not exceed room capacity (first come, first served).
Homework is due via Ted by 11:59 pm on the due date (Friday or Wednesday). The weekly reading quizzes are due by 11:59 pm on the due date (usually Wednesday or Monday).
NOTE: Subject to change throughout the quarter.
>Date | Day | Subject | Reference | Notes |
3/31/15 | Tues | Introduction, Deterministic Finite Automata (DFA's) | Sipser 0, 1.1 | Review class web site info |
4/1/15 | Wed 5 pm | Sipser 1.1 | Reading Quiz 1 | |
4/3/15 | Fri | Designing DFA's, Regular Languages, Closure of Regular Languages | Online Self Test HW 0 (Ch 0) Due by 5pm | |
4/7/15 | Tues | More on Closure of Regular Languages, Introduction to Nondeterministic FA (NFA's) | Sipser 1.2 | |
4/8/15 | Wed 5 pm | Sipser 1.2 | Reading Quiz 2 | |
4/9/15 | Thurs | Designing NFA's, NFA-DFA Equivalence, Another Closure Proof | Sipser 1.2 | |
4/10/15 | Fri 5 pm | HW 1 Due | ||
4/13/15 | Mon 5 pm | Sipser 1.3 | Reading Quiz 3 | |
4/14/15 | Tues | Regular Expressions; An Introduction to Non-Regular Languages | Sipser 1.3 | |
4/15/15 | Wed 11:59 pm | Sipser 1.4, pp. 176-179 | Reading Quiz 4 | |
4/16/15 | Thurs | Non-Regular Languages | Sipser 1.4, pp. 176-179 | |
4/18/15 | Sat 11:59 pm | HW 2 Due | ||
4/21/15 | Tues | Using the Pumping Lemma | Sipser 1.4 | |
4/22/15 | Wed 6:30 - 7:50 pm | Exam 1 | ||
4/23/15 | Thurs | Context-Free Grammars, Ambiguity | Sipser 2.1 | |
4/27/15 | Mon 11:59 pm | Sipser 2.1, 2.2 | Reading Quiz 5 | |
4/28/15 | Tues | Push-Down Automata (PDA's) | Sipser 2.2 | |
4/30/15 | Thurs | Review of CFG and PDA's; Introduction to Turing Machines | ||
5/1/15 | Fri 11:59 pm | HW 3 Due | ||
5/4/15 | Mon 11:59 pm | Sipser 3.1 - 3.3 | Reading Quiz 6 | |
5/5/15 | Tues | Turing Machines (TM's) | Sipser 3.1 | |
5/7/15 | Thurs | More TM's (Variants, Algorithms, Church-Turing Thesis) | Sipser 3.2, 3.3 | |
5/8/15 | Fri 11:59 pm | HW 4 Due | ||
5/11/15 | Mon 11:59 pm | Sipser 4.1 | Reading Quiz 7 | |
5/12/15 | Tues | Decidability | Sipser 4.1 | |
5/13/15 | Wed 6:30 - 7:50 pm | Exam 2 | ||
5/14/15 | Thurs | Counting Infinite Sets, Paradoxes and Diagonalization; Undecidability: The Acceptance Problem for TM's | Sipser 4.2 | |
5/18/15 | Mon 11:59 pm | Sipser 4.2 | Reading Quiz 8 | |
5/19/15 | Tues | The Halting Problem for TM's and Other Undecidable Problems | Sipser 4.2 | |
5/20/15 | Wed 11:59 pm | Sipser 5.1 (no computation histories) and 5.3 | Reading Quiz 9 | |
5/21/15 | Thurs | More Undecidable Problems | Sipser 5.1 | |
5/23/15 | Sat 11:59 pm | HW 5 Due | ||
5/26/15 | Tues | Computable Functions, Mapping Reducibility | Sipser 5.3 | |
5/28/15 | Thurs | Time Complexity | Sipser 7.1 | |
5/31/15 | Sun 11:59 pm | HW 6 Due | ||
6/1/15 | Mon 11:59 pm | Sipser 7.1 - 7.3 | Reading Quiz 10 | |
6/2/15 | Tues | P, NP, and NP Completeness | Sipser 7.2, 7.3 | |
6/4/15 | Thurs | Final Exam Review | ||
6/6/15 | Saturday | Final Exam | 11:30 am - 2:29 pm, Location: Section A: WLH 2001 Section B, Last name A - M: WLH 2005 Section B, Last name - Z: PCNYN 106 |
Homework Assignments will be due by the date and time indicated in the schedule above. A PDF of the assignment will be posted on Ted
. Homework solutions will also be posted there.
Lecture Notes will be posted on Ted after each class. Lecture podcast will be available at podcast.ucsd.edu