CS138, UCSB, 2011-09/12

Recent Announcements

  • 2011-12-13: The CS138 grades of Fall 2011 have been submitted; if you want you can pick up your Final in Winter 2012. Happy Festivus everyone

General CS138 Information

  • Course no.: CS 138
  • Course title: Automata and Formal Languages
  • Total credits: 4
  • Description: Formal languages; finite automata and regular expressions; properties of regular languages; pushdown automata and context-free grammars; properties of context-free languages; introduction to computability and unsolvability (Turing machines) and computational complexity.
  • Prerequisites: Computer Science 40; open to computer science and computer engineering majors only.
  • CS138 is not open for credit to students who have completed Computer Science 136.

Fall 2011 CS138 Information

  • Professor: Wim van Dam; vandam@cs.____.___; Harold Frank Hall, Room 2151
  • Teaching assistant: Çetin Şahin; cetin@cs.____.___

Weekly Schedule, Typical

  • Monday
    • 14:00-15:15: Class (PSYCH 1902)
  • Tuesday
  • 14:00-15:00: Office hour TA (PHELP 1413)
    • 17:00-17:50: Discussion (BSIF 1217)
  • Wednesday
    • 10:00-12:00: Office hours WvD (HFH 2151)
    • 14:00-15:15: Class (PSYCH 1902)
  • Thursday
  • 15:00-16:00: Office hour TA (PHELP 1413)
    • 17:00-17:50: Discussion (PHELP 1260)
  • Friday
  • Announcement of Homework
    • 15:00: Homework due

Grading

Assignments will be graded using the following scale:

  • 3 points: Exemplary; student applies knowledge with virtually no conceptual or procedural errors
  • 2 points: Adequate; student applies knowledge with no significant conceptual errors and only minor procedural errors.
  • 1 point: Minimal; student applies knowledge with occasional conceptual errors and only minor procedural errors.
  • 0 points: Unsatisfactory; student makes significant conceptual and/or procedural errors when applying knowledge.

The course grade is determined as follows.

The 5 Homeworks and 2 Midterms all count for an equal amount; the final counts for 2 Midterms. This means that your total grade will be determined according to: 5 Homeworks + 2 Midterms + 1 Final = 5/9 + 2/9 + 2/9. In other words, each homework and midterms counts for 1/9th, the final counts for 2/9th. However, during the final you are allowed to decide whether you want to drop your lowest score among your homeworks and midterms and let your final count for 1/3rd, in which case the equality becomes: 4 Homeworks + 2 Midterms + 1 Final = 4/9 + 2/9 + 3/9 or 5 Homeworks + 1 Midterm + 1 Final = 5/9 + 1/9 + 1/3.

Means and Standard Deviations of HWs, MTs, and F

To calculate your 'normalized score', you take your score, subtract the mean, and divide by the standard deviation. For example, if you scored 7 points on HW3, your normalized score for HW3 is (7-5.47)/1.65 = 0.927.

The correlation coefficients between the HWs and MTs are as given in the table below. To interpret these coefficients to you can use the following guideline: a coefficient between -0.1 and +0.1 indicates no correlation, a coefficient between 0.1 and 0.3 indicates a small correlation, a coefficient between 0.3 and 0.5 indicates a medium correlation, and a coefficient between 0.5 and 1.0 indicates a strong correlation.

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]

  • No Class or Discussion

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