To calculate your 'normalized score', you take your score, subtract the mean, and divide by the standard deviation.
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 [09-26/09-29]
- First Class on Thursday, September 26, 12:30--13:45
- Class topics: formalities; [R, pp. 1--16]: introduction to CS138, proof techniques, set theory, formal languages, defining problems as the decision problem of recognizing the words of a formal language
- Friday: announcement HW1 "Formal Languages"
Week I [09-30/10-06]
- Class topics, Tuesday: [R, pp. 16--20] concatenation, operations on languages, reducing general problems to decision problems
- Class topics, Thursday: [R, pp. 22--30] finite automata, formal definition of FA, regular languages, regular operations, closure properties of RLs
- First Discussions on Tuesday, October 1, 16:00--16:50 and 17:00-17:50
- Discussion topics [EK]: HW1 "Formal Languages"
- Friday: HW1 due; announcement of HW2 "Deterministic Finite Automata"
Week II [10-07/10-13]
- Class topics: [R, pp. 30--38]: nondeterminism, nondeterministic FA, proof that every NFA is equivalent to a DFA, closure of RLs under union, concatenation, and star; [R, pp. 38--45]: regular expressions, RE≤RL, generalized NFA, RE=R
- Discussion topics: HW2
- Friday: HW2 due; announcement of HW3 "NFA and Regular Languages"
Week III [10-14/10-20]
- Class topics: [R, pp. 45-48]: non-regular languages, pumping lemma for RLs, proving non-regularity using the pumping lemma
- Discussion topics: HW3, return of HW1
- Friday: HW3 due; announcement of HW4 "Nonregular Languages"
Week IV [10-21/10-27]
- Class topics: [R, pp. 58--70]: Context free grammars, derivation trees, parsing, ambiguity, CFGs and programming languages; [R, pp. 72-76]: transforming grammars, removing useless productions
- Discussion topics: HW4, return of HW2
- Friday: HW4 due
Week V [10-28/11-03]
- Class topics: [R, pp. 72-78]: transforming grammars, removing lambda-reductions, removing unit-productions; [R, pp. 80--84]: Chomsky Normal Form, (Greibach Normal Form), CYK algorithm for membership for CFGs
- Discussion topics: Return of HW3; Midterm
- Thursday October 31: Halloween Midterm on formal languages, finite automata, regular languages, and context free grammars
- Material: Reader pp. 1--70; Slides: Formal Languages, Finite Automata, Regular Expressions, Non Regular Languages, CFLs; HWs 1--4.
- The location and time of MT are those of a regular class: Psych 1902, between 12:30 and 13:45 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 Tuesday's class you can ask questions about this midterm
Week VI [11-04/11-10]
- WvD's office hour on Tuesday 2013-11-06 is between 11:00 and 12:00
- Class topics: [R, pp. 80--84]: Chomsky Normal Form, (Greibach Normal Form), CYK algorithm for membership for CFGs; [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
- No Discussion
- Friday: announcement of HW5 "Parsing, Non CFLs, PAs"
Week VII [11-11/11-17]
- Monday, November 11: Veteran's Day
- Class topics: [R, 88-102] Pushdown Automata, PA and CFLs, deterministic PAs and deterministic CFLs; [R, pp. 112--116]: Turing Machines, Church-Turing Thesis, computability, universality and self-reference of TMs;
- Discussion topics: HW5; return of Midterm
- Friday: HW5 due; announcement of HW6 "PAs, TMs"
Week VIII [11-18/11-24]
- Class topics: [R, pp. 112--116]: [R, pp. 116-122]: decidable problems, Universal TM, undecidability of the Halting Problem, proof by diagonalization, semi-decidable problems
- Discussion topics: HW6
- Friday: HW6 due
Week IX [11-25/12-01]
- Class topics: [R, pp. 123--128]: recursive and recursively enumerable properties, more decidable and undecidable problems, computability theory
- Discussion topics: return of HW5, answers to HW6
- Thursday November 28: No class
- Thursday and Friday, November 28 and 29: Thanksgiving
Week X [12-02/12-06]
- Class topics: wrap-up "How do the topics of CS138 fit into computer science?", preview of Final, "You and your grade", course evaluation; Q&A on Final
- Discussion topics: return of HW6; Final
- No office hours of EK on Wednesday. Instead, EK will have his office hours on Friday, 13:00--15:00 (Graduate Student Lab, Rm 698)
Finals Week [12-07/12-13]
- Final Examination: Monday November 9, 12:00--15:00