Notice the strong correlation between HW2 and MT2, and the absence of a correlation between MT1 and HW5, as well as between HW1 and MT1.
Academic Honesty
The following applies to every course you attend at UC Santa Barbara (from UCSB Campus Regulations, Chapter VII: "Student Conduct and Discipline"):
It is expected that students attending the University of California understand and subscribe to the ideal of academic integrity, and are willing to bear individual responsibility for their work. Any work (written or otherwise) submitted to fulfill an academic requirement must represent a student’s original work. Any act of academic dishonesty, such as cheating or plagiarism, will subject a person to University disciplinary action. Using or attempting to use materials, information, study aids, or commercial “research” services not authorized by the instructor of the course constitutes cheating. Representing the words, ideas, or concepts of another person without appropriate attribution is plagiarism. Whenever another person’s written work is utilized, whether it be a single phrase or longer, quotation marks must be used and sources cited. Paraphrasing another’s work, i.e., borrowing the ideas or concepts and putting them into one’s “own” words, must also be acknowledged. Although a person’s state of mind and intention will be considered in determining the University response to an act of academic dishonesty, this in no way lessens the responsibility of the student.
Specifically for the current CS138 course this means that
- You are not allowed to copy or transcribe answers to homework assignments from others or other sources.
- Although you are allowed to discuss homework assignments with others, you should write down your answers independently. You should always be able to argue and explain your answers when asked for clarifications.
- During the Midterm and Final Examination no electronics are allowed, additional notes are only allowed to the extent described prior to the test.
- When you will be unable to hand in the homework in time you should report this to WvD as soon as possible, but always before the deadline. No matter the reason, you will always be asked to present documentation.
- When in doubt, ask.
- Students violating the rules of Academic Honesty will receive an "F" for the course and will be reported to the Dean of Students Office.
Schedule of Topics, Homeworks, Midterms, and Final
Week nulla [September 22-25]
Week I [September 26 - October 2]
- First Class on Monday, September 26, 14:00; first Discussion on Tuesday, September 27, 17:00
- Class topics: formalities; [R, pp. 1-20]: introduction to CS138, proof techniques, set theory, formal languages, defining problems as the decision problem of recognizing the words of a formal language, concatenation, reducing general problems to decision problems
- Homework 1 on topics of Week I will be posted on Friday, September 30
Week II [October 3-9]
- Class topics: [R, pp. 21-30]: finite automata, formal definition of FA, regular languages, regular operations, closure properties of RLs; [R, pp. 30-38]: nondeterminism, nondeterministic FA, proof that every NFA is equivalent to a DFA, closure of RLs under union, concatenation, and star
- Wednesday, October 5 WvD will be away from campus and he will have no office hours that day. Wednesday's class will be taught by prof. Amr El Abbadi.
- Homework 1 is due Friday, October 7 at 3:00 pm
- Homework 2 on topics of Week II will be posted on Friday, October 7
Week III [October 10-16]
- Class topics: [R, pp. 38-45]: regular expressions, RE≤RL, generalized NFA, RE=RL; [R, pp. 45-48]: non-regular languages, pumping lemma for RLs, proving non-regularity using the pumping lemma
- WvD's office hours will be between 11:00 and 13:00 on Wednesday, 12 October 2011
- Homework 2 is due Friday, October 14 at 3:00 pm
- Homework 3 on topics of Week II will be posted on Friday, October 14
Week IV [October 17-23]
- Class topics: [R, pp. 58-70]: Context free grammars, derivation trees, parsing, ambiguity, CFGs and programming languages; [R, pp. 72-78]: transforming grammars, removing lambda-reductions, removing unit-productions, removing useless productions
- The TA's office hours will be on Tuesday October 18, 2:00 - 4:30 pm; the TA will not have office hours on Thursday, October 20
- Homework 3 is due Friday, October 21 at 3:00 pm
Week V [October 24-30]
- Monday Class topics: [R, pp. 80-84]: Chomsky Normal Form, (Greibach Normal Form), CYK algorithm for membership for CFGs
- Midterm 1 on all topics of Weeks I-IV is on Wednesday, October 26
- The location and time of MT1 are those of a regular class: Psych 1902, between 2:00 and 3:15 pm
- You are allowed to bring one, letter-sized, double-sided page of notes.
- You are not allowed to bring any other notes like the reader, nor are you allowed to use electronic devices like iPhones, calculators, etc.
- Remember that one Midterm counts as much as one Homework
- During Monday's class you can ask questions about this midterm
- Homework 4 on topics of Weeks IV and V will be posted on Friday, October 28
Week VI [October 31 - November 6]
- Monday October 31 is Halloween; yes, WvD is aware of this
- Class topics: [R, pp. 104-106]: non-CFLS, pumping lemma for CFLs, proving languages to be non CFLs using the pumping lemma; [R, 88-102] Pushdown Automata, PA and CFLs, deterministic PAs and deterministic CFLs
- Homework 4 is due Friday, November 4 at 3:00 pm
Week VII [November 7-13]
- Monday Class topics: review for MT2, Q&A, answers to MT1
- Midterm 2 on all topics of Weeks I-VI is on Wednesday, November 9
- The location and time of MT2 are those of a regular class: Psych 1902, between 2:00 and 3:15 pm
- You are allowed to bring one, letter-sized, double-sided page of notes.
- You are not allowed to bring any other notes like the reader, nor are you allowed to use electronic devices like iPhones, calculators, etc.
- Remember that one Midterm counts as much as one Homework
- During Monday's class you can ask questions about this midterm
- Friday November 11 is Veteran's Day
Week VIII [November 14-20]
- Class topics: [R, pp. 112-116]: Turing Machines, Church-Turing Thesis, computability, universality and self-reference of TMs; [R, pp. 116-122]: decidable/semi-decidable sets, recursive and recursively enumerable properties, (equivalent models)
- Homework 5 on topics of Week VIII will be announced on Wednesday, November 16
Week IX [November 21-27]
- Monday Class topics: [R, pp. 123-128]: (Universal TM), undecidability of the Halting Problem, proof by diagonalization, other decidable and undecidable problems
- Monday November 21, WvD will have an extra office hour between noon and 1 pm
- Homework 5 is due on Wednesday, November 23, at 3:00 pm
- Because of Thanksgiving there will be no Class, Discussion or Office Hours on Wednesday, Thursday or Friday, November 23-25
Week X [November 28-December 2]
- Monday and Wednesday class topics: wrap-up "How do the topics of CS138 fit into computer science?", preview of Final, "You and your grade", course evaluation
- Wednesday class topics: Q&A on Final
Finals Week [December 3-9]
- The Final on all topics of Weeks I-IX is on Monday, 5 December 2011, between 4:00 pm and 7:00 pm in the regular class room Psych 1902
- You are allowed to bring one, letter-sized, double-sided page of notes.
- You are not allowed to bring any other notes like the reader, nor are you allowed to use electronic devices like iPhones, calculators, etc.
- During Wednesday's class in Week X you can ask questions about this midterm