Csc520 Foundations of Computer Science
Fall 2018

Dr. Robert Kline
Office: 25 Univ. Ave. (UNA), #138
Phone: 610-436-2181

Office Hours for Fall 2018

Mo,We: 4:15–5:45
Tu,Th: 10:45–12:00
Elements of the Theory of Computation (2nd Edition)
H. R. Lewis & C. H. Papadimitriou
ISBN-13: 978-0132624787
ISBN-10: 0-13-262478-8

I was able to download this textbook free as a PDF file. A google search for available sites may be successful with these keywords:
lewis and papadimitriou elements of the theory of computation download free
website (available through D2L)
This course offers an advanced treatment of many of the theoretical areas underlying other computer science subjects.
The course material is taken both from the textbook and the instructor's course website. The course outline is as follows:

Textbook Chapters 1, 2; Online Course Notes 1 - 8
  • Regular languages, finite automata, deterministic (DFA) and nondeterministic (NFA).
  • Equivalence of finite automata and regular languages.
  • Existence of non-regular languages
  • DFA State minimization.
Textbook Chapters 3; Online Course Notes 9 - 13
  • Context-free Languages, Normal Forms
  • Pushdown automata and Context Free Language equivalence
  • Existence of non-context free languages
Textbook Chapters 4, 5; Online Course Notes 14 - 18
  • Turing Machine model and equivalences
  • Recursively enumerable and recursive languages
  • Undecidability, unsolvability & the Halting Problem
Your grade is based on these factors:
  • 3 Tests: 60% (20% each)
  • 4 homework assignments: 40%

Course Grades Evaluation results are normally returned within 2 class periods after a test or due date of homework/program. It is your responsibility to ask me for them if you miss the class when they are returned.

I do not post grades on D2L. You should be able to keep track of your own grades and compute your overall average. See Csc520 Course Grade.

The correspondence of a percentage to a letter grade is based on a standard formula:
PercentageLetter Grade Quality Pts.
93 – 100A 4.00
90 – 92A- 3.67
87 – 89B+ 3.33
83 – 86B 3.00
80 – 82B- 2.67
77 – 79C+ 2.33
73 – 76C 2.00
70 – 72C- 1.67
0 – 69F 0.00
It is the responsibility of each student to adhere to the WCU's standards for academic integrity. Violations of academic integrity include any act that violates the rights of another student in academic work, that involves misrepresentation of your own work, or that disrupts the instruction of the course. Other violations include cheating on assignments or examinations; plagiarizing, which means copying any part of another's work and/or using ideas of another and presenting them as one's own without giving proper credit to the source; selling, purchasing, or exchanging of term papers; falsifying of information; and using your own work from one class to fulfill the assignment for another class without significant modification. Proof of academic misconduct can result in the automatic failure and removal from the course. For questions regarding Academic Integrity, or the Student Code of Conduct, students are encouraged to refer to the Computer Science web page, the Undergraduate Catalog, the Ram's Eye View, and the WCU website.
It is expected that faculty, staff, and students activate and maintain regular access to University-provided email accounts. Official university communications will be sent through this email account and you are responsible for obtaining such official communications. Failure to access this email account will not exempt individuals from the responsibilities associated with this course.
West Chester University will make accommodations for persons with disabilities. To know more about WCU's Services for Students with Disabilities (OSSD), contact the OSSD located at 223 Lawrence Center. See the website OSSD website. If you have a disability that requires accommodations under the Americans with Disabilities Act (ADA), please present your letter of accommodations to OSSD as soon as possible so that OSSD can support your success in an informed manner. Accommodations cannot be granted retroactively.
West Chester University and its faculty are committed to assuring a safe and productive educational environment for all students. In order to meet this commitment and to comply with Title IX of the Education Amendments of 1972 and guidance from the Office for Civil Rights, the University requires faculty members to report incidents of sexual violence shared by students to WCU's Title IX Coordinator. The only exceptions to the reporting obligation are when incidents of sexual violence are communicated by a student during a classroom discussion, in a writing assignment for a class, or as part of a University-approved research project. Faculty members are obligated to report sexual violence or any other abuse of a student who was, or is, a person under 18 years of age when the abuse allegedly occurred to the official designated in the University protection of minors policy. Information regarding the reporting of sexual violence and the resources that are available to victims of sexual violence is set forth in the Social Equity website.
Students are encouraged to sign up for the University's free WCU ALERT service, which delivers official WCU emergency text messages directly to your cell phone. For more information, visit To report an emergency, call the Department of Public Safety at 610-436-3311.
Students are advised to read and comply with the excused absences policy for university-sanctioned events in the WCU Undergraduate Catalog. Please note that the responsibility for meeting academic requirements rests with the student. This policy does not excuse students from completing required academic work, and that professors can require a fair alternative to attendance on those days that students must be absent from class in order to participate in a university-sanctioned event.
The following are clear, measurable and observable outcomes from taking this course:
  • The student will learn: how to take a regular language and turn it into a finite automaton, and vice versa; how to decide if a given language is regular or not; how to construct a minimal automaton for a given regular language.
  • The student will learn: how to write and analyze grammars for context free languages (CFLs); how to create PDA for CFLs; how to understand whether a language is context free or not.
  • The student will learn: how to write Turing machines for given languages, how to determine that languages are or are not computable in various senses.

Measuring and assessing student learning outcomes

  • Homeworks 1, 2 and Test 1 will measure and assess the competencies in student learning outcomes listed in part (a).
  • Homeworks 3 and Test 2 will measure and assess the competencies in student learning outcomes listed in part (b).
  • Homeworks 4 and Test 3 will measure and assess the competencies in student learning outcomes listed in part (c).

Graduate programmatic student learning outcomes

  • Students demonstrate an ability to understand the theoretical basis of Computer Science concepts.