CSCE 355 -- Spring 2020

Foundations of Computation

Duncan A. Buell
Professor
Department of Computer Science and Engineering
University of South Carolina
Columbia, SC 29208
2263 Innovation Center
"buell" in any of several domains
803-777-7848(voice)
803-777-3767(fax)
grizzlefarb

Comment

This is the boilerplate page for the section of 355 that I am teaching this spring.

Caveat

THIS WEB PAGE IS STILL UNDER DEVELOPMENT. DON'T TAKE ANYTHING AS CAST IN STONE UNTIL THE FIRST DAY OF CLASS EXCEPT FOR THE CLASS TIMES AND LOCATIONS AND THE DATES/TIMES OF THE MIDTERM AND FINAL EXAMS.

The contents of this page and of the Moodle site are subject to change throughout the semester without previous notice. You are responsible for looking at this page and the Moodle site on a regular basis, which means at least as often as once per class, which means at least twice a week.

Basics

  • Section 1 Lecture (Duncan Buell): 5:30-6:45 M-W, Room B201 Main Street building

  • Buell Office hours: 1:15-3:15pm M-W and by appointment. Also usually reachable by email.
  • Teaching Assistant: Nawras Alkassab, 1215 Innovation Center, office hours 2:30-4:00pm T-Th

  • This URL
  • Buell's home page
  • The official syllabus for this course.
  • The Moodle site for this course. There will be a lot of information put up on the Moodle site, which will be used instead of Blackboard. Unlike this web page, which is available to all and sundry around the world, the Moodle website will be password limited to students in this class.
  • The text for this course is Hopcroft, Motwani, and Ullman, Automata Theory, Languages, and Computation, (3rd Edition). Addison-Wesley-Pearson 2007.
  • Department and College Links:

Learning Outcomes

Students will be able to:
  • Prove theorems in discrete math by induction, contradiction, or cases.
  • Analyze, design, and manipulate finite state acceptors.
  • Design and manipulate regular expressions.
  • Prove languages not regular or context-free.
  • Design and analyze context-free grammars and push-down automata.
  • Analyze and simulate a Turing machine.
  • Prove problems undecidable via reduction.

Course Topics

  • Proof techniques, numbers, sets, relations
  • Deterministic and nondeterministic finite automata
  • Regular expressions and regular languages
  • Grammars, push-down automata, and context-free languages
  • Turing machines and undecidability

Copyright

The material presented on this page and on the Moodle site is copyrighted material. Although you own, under USC rules, your homework and program submissions, the copyright for the source text for the homeworks, programs, and other material remains either with the textbook author or with the instructor of this course. It is a violation of copyright to upload this material to any of the various homework-sharing websites. Uploading to an external site may also be a violation of USC academic integrity rules.

Further information on copyright can be found at the official website, which you are encourage to consult both to help you ensure that you are in compliance with existing law as well as to know how to protect your own intellectual property.

Tests and Assignments

There will be two midterm exams, each worth 20% of your grade. Graded homework problems will be another 20%. Another 15% of your grade will consist of a programming assignment. The remaining 25% of your grade is a final exam. All midterm exams are closed book, closed notes, and no electronic devices allowed, except for legitimate use by students with documented special needs. Each midterm will be a number of questions or problems sampled from the preceding homework assignments, possibly modified somewhat.

The first midterm exam will almost certainly be on Wednesday, 12 February 2020.

The second midterm exam will probably be on Monday, 23 March 2020.

The last day to drop without a WF grade is Saturday, 28 March 2020.

No make-up exams will be given except under extreme circumstances with a valid excuse, in which case you must give me notice well before the exam if at all possible. Valid excuses include grave illness or death in the immediate family, or other similarly dire emergency. They do not include car problems or non-emergency events (weddings, trips, sports meets, etc.). Before proceeding with the course make sure that you can attend all the exams.

The final exam will be cumulative, although there will be some weighting of the material presented after the second midterm.

The final exam for Section 1 is scheduled for Monday, 4 May, at 4:00pm.

All assignments will be on the Moodle site.

(Probable) Grading Scheme

Midterm Exams (2) 40% (two at 100 points each)
Graded Homework 20% (total of 100 points)
Programming Project 15% (total of 75 points)
Final 25% (one at 125 points)

Attendance and Grades

It has been found, and should come as no surprise to anyone, that attendance at class correlates positively with your GPA. We will be taking attendance. For every three (3) unexcused absences, your grade will be lowered by one full letter. The judgement as to accepting the excuse is ours. Illness, family emergencies, and such are excusable. Returning home late from Myrtle Beach to avoid the traffic jam is not an excusable absence.

Unless otherwise indicated, there are no bonus points and there is no extra credit that can be earned in this class. If you want to total up points so as to get a good grade, then do the homeworks and do well on the exams.

Deadlines

Assignments will have due dates. Unless otherwise specified, the usual deadline will be that assignments will be collected in class on the day when they are due.

Rules, Expectations, etc.

  • You are responsible for reading this website and the Moodle site regularly and carefully. You are responsible for the material in this website, including rules and scheduling information.
  • You are responsible for knowing who we are, how to get in touch with us by email, and how to find offices in person. (See the first point above.) If you google "duncan buell" then Buell's USC web page is what comes up first on the list, so there is no excuse for someone in a computer science class not being savvy enough to find contact information.
  • You are responsible for reading your university email at jrandomhacker@email.sc.edu or whatever email address you have inserted into the Moodle site. If we send out a mass email to the class, it will be using the Moodle email address for you, not to some other address. My emails to the class at large will come from Moodle, so you can check what address is set up for you there; this is your responsibility.
  • You are responsible for reading the material before coming to class. If we have covered all of a particular section or chapter, you must take the initiative on your own to read the next section or chapter.
  • If for some reason the Moodle dropbox is not functioning, you should immediately send us an email with your assignment attached. This email must have a timestamp before the dropbox deadline. Late assignments will be penalized. (See the first two points above.)
  • You are responsible for attending class. Attendance will be taken, and it will affect your grade. The Student Success Center has found (to no one's great surprise) that your GPA is likely to improve by a full one-half point simply if you attend class.
  • This course has prerequisites of CSCE 211, CSCE 212, and CSCE 350.

Disability Accommodation

Any student with a documented disability should contact the Student Disability Resource Center at 777-6142 to make arrangements for appropriate accommodations.

Academic Honesty

Assignments and examination work are expected to be the sole effort of the student submitting the work. Students are expected to follow the University of South Carolina Honor Code and should expect that every instance of a suspected violation will be reported. Students found responsible for violations of the Code will be subject to academic penalities under the Code in addition to whatever disciplinary sanctions are applied.

We will be submitting programming assignments in bulk to the MOSS (Method of Software Similarity) website. This service will compare every student's code against every other student's code and will display the common sections found in any pair of submissions. Should it be the case that your code has a significant match with the code of some other student, you can expect that we will submit an incident report with the Office of Academic Integrity.

There seems to be a widespread misunderstanding of the concept of "your own work." In addition to the USC Code, some good sources of text for what is or is not acceptable behavior are the academic honesty policy statement from Harvey Mudd College, the policy statement from Professor Steven Huss-Lederman at Beloit College, and the text of part of the collaboration policy statement from MIT. You can expect your programming assignments to be checked against those turned in by other members of the class as well as code that I can find on the web. We expect the correlations between your work and that of others to be minimal.

We can also offer an operational definition of what you can do and of how you can distinguish "learning from a group discussion" and "turning in someone else's work." If, after having participated in a group activity, you can walk away, put the books down, have lunch, and then come back afterwards to re-create from your own head, without consulting any notes you have written or stored electronically, the material and techniques you discussed as a group, then you can legitimately say that you have learned from the group but the work you turn in is your own.

If your work is identical or nearly identical to that turned in by some other student, then we will assume a priori that your work has been plagiarized either to or from that student, and under USC rules you are both equally responsible if you are aware of this duplication. You are not permitted to copy the text of code from someone else and use it as your own unless that text comes from the textbook or from the material on the Moodle site, and any such text copied in must be attributed to its source.

You are permitted to use code from the text, from the examples in cplusplus.com, or from the Moodle site (examples and solutions to earlier homeworks). If you use entire blocks of code, or if you use a block of code and make major modifications, you must document from where you got the basic code. If you use only one line (perhaps to get exactly the right syntax for the needed kind of iterator, say), then you need not document this.

On the Proper Use of Computing Resources

Students are expected to be aware of the university policy on use of computing resources, including the Student Guidelines for Responsible Computing found here, as well as the college and departmental policies on proper use of computing resources. Every instance of a suspected violation will be reported. Students should be aware that neither the instructor nor the department are responsible for making alternative arrangements should improper use leading to revocation of access to departmental or college resources make it impossible for you to complete the programming assignments on time.