CIT 596 Course Overview (Spring 2014)


Course Objectives

The Spring 2015 version of this course has 3 parts to it.

The general plan is to split this course into 3 sections

  • Graph Algorithms. Shortest paths, MST, Network flows.
  • Formal languages. Regular Expressions. Turing machines
  • P vs NP (what is tough for a computer). Decidability (what is impossible for a computer).
There will a midterm (or final) associated with each of the 3 sections.
The final will be not be cumulative. It is scheduled by the registrar.

After successfully completing this course, you also should have gained a greater appreciation for some of the fundamental questions of computer science:

  • What problems can be solved by a computation?
  • How hard is it to compute solutions?
  • How can we express computation?
You will also be aware of some concrete answers to these and related great questions of computer science, the reasons why some questions in this area will remain unanswered forever, and that some answers are still being sought.

 

Class Meeting Times

M/W 1:30-3:00pm, TBD

Recitation on Friday 11 am - noon, TBD

Back to Top

Textbooks

The one required textbook for this class is Sipser. You should also be able to find copies of at least the second edition online as a pdf. This is a very well written book on the topic and I do recommend purchasing a copy.

It's also a good idea to have a copy of a discrete mathematics book handy, since prior knowledge of topics like induction will be assumed.

For the algorithms part of the course, we will use Algorithms Unlocked by Thomas Cormen.


Back to Top

Piazza

Please use the following link to sign up for the piazza discussion for this class piazza

Grading

Note that these are only guidelines, but final course grades will likely be based on the following:

  • Midterm exam 1 (20%)
    • This will be scheduled for sometime at the end of the first month. Exact date TBD
  • Midterm exam 2 (20%)
    • This will be scheduled for sometime at the end of the second month. Exact date TBD.
  • Final exam (20%)
    • This is scheduled by the university registrar.
    • The exam will NOT be comprehensive. The focus will be on the last part of the semester. However, the NP completeness section does rely on other parts of the course.
  • Homework and programming assignments (40%)
    • Expect homeworks every week. You are allowed to sit and work in study groups, but a) write the final answers yourself and b) please put down the name of your collaborators.
    • There will also be some programming assignments (max 4) in the course. The number is still to be decided. You can choose to work in pairs for those assignments.
    • Homework submissions have to be done electronically in the form of a pdf. You are free to use word/latex/anything to produce a pdf

Academic Integrity

Do not cheat.

Note: When in doubt always ask the instructor or TA first, to avoid any potential collabration that can lead to academic dishonesty.

You can further read Penn's Code of Academic Integrity page on this subject matter, as well as the SEAS Graduate Student guidelines on the code of ethics.


Back to Top

Homework turn-in procedure

Submit homeworks in the form of a pdf that you upload on canvas

Submissions after the deadline are subject to a 10% per day penalty, up to seven days, after which the submission will not be accepted. Deadlines will be strictly enforced. If an assignment is due at midnight, please plan on submitting it at 11:30 pm.

Back to Top