Spring 2019: Call no 40574 (MWF 12 noon in LC C3) and 17422 (MWF 2pm in LC F3)
Instructor:
Ajay Kshemkalyani Email:
first name @ uic.edu Class meeting times: MWF 12:00 - 12:50pm in LC C3 and MWF 2:00-2:50pm in LC F3 Office Hours (in 915 SEO): M,W 1:00 - 1:45pm
TAs:
Nazanin Azarhooshang, Email: nazarh2@uic.edu
Office Hours (in TBH 190): T 9:00 - 11:00am
Deblina Roy, Email: droy7@uic.edu
Office Hours (in TBH 190): W 10:00am - 12pm
David Shumway, Email: dshumw2@uic.edu
Office Hours (in TBH 190): M 10:00 - 11:30am
Trishla Shah ( undergrad TA), Email: tshah28@uic.edu
Office Hours (in CS Lounge): R 8:00 - 11:00am
Recitation section time: W 8:00-8:50am in TBH 180A; TA: Debalina Roy Recitation section time: W 9:00-9:50am in TBH 180A; TA: Debalina Roy Recitation section time: W 9:00-9:50am in TBH 180B; TA: David Shumway Recitation section time: W 8:00-8:50am in TBH 180E; TA: Nazanin Azarhooshang Recitation section time: W 9:00-9:50am in TBH 180D; TA: Nazanin Azarhooshang
The recitation section meetings will begin from the third week (W, Jan 30).
We may occasionally skip it in some week.
CANCELLED: Jan 30 (Wed recitation) for students registered for room TBH 180A at 9:00am: please join the sections in room TBH 180B or TBH 180D
This course focuses on theoretical principles.
You will not be programming in this course.
This course presents some of the most fundamental results in
theoretical Computer Science.
These results attempt to answer, in a precise mathematical sense, the
following two questions, which are of practical as well as
philosophical interest:
Can a given problem be solved by computation?
How efficiently can a given problem be solved by computation?
We focus on problems rather than on specific
algorithms for solving problems.
To answer both questions mathematically, we need to start by formalizing the
notion of "computer" or "machine".
So the course outline breaks naturally into three parts:
Models of computation (Automata Theory) (Sipser: Chapters 1, 2, 3)
Finite automata
Push-down automata
Turing machines
What can we compute? (Computability Theory) (Sipser: Chapters 4, 5)
How efficient can we compute? (Complexity Theory) (Sipser: Chapters 7, 8)
The specific contents we plan to cover are as follows.
Chapter 7 (we will try to cover some sections from this chapter): Time-complexity, polynomial time (P), languages in P, Strong Church-Turing thesis; Nondeterministic polynomial time (NP), SAT; Polynomial time reductions, NP-completeness, 3SAT versus CLIQUE, Cook-Levin Theorem; Proof Cook-Levin theorem, NP-completeness of SAT and 3SAT, proving NP-completeness; NP-completeness of HAMPATH, SUBSET SUM
Chapter 8 (we may not have time for this chapter):
Space complexity, Savitch's theorem, PSPACE, PSPACE completeness, TQBF.
You are expected to be familiar with all the material covered in the lectures
and in the relevant sections of the textbook.
Attending lectures is highly advisable, because some of the lectures and
homework problems will be drawn from material not in the text, and you will
be responsible for this material.
There will be several (say, 6 to 8) homework problem sets, two midterm tests, and a
final exam.
Your final grade will be based on the sum of your problem set, midterms, and
final exam scores.
The following is only a TENTATIVE breakup of the evaluation scheme and is
subject to changes as the course progresses.
Test 1 (20%).
Test 2 (20%).
Final (40%).
Homeworks(20%):
The full scale of grades ("A" - "F") will be used.
In general there will be no specific reading assignments.
However, the relevant sections from the textbook will be pointed out in
class.
It is recommended that you make yourself familiar with the material prior to
class, and it is a good strategy to read the pertinent sections again right
after class to make sure you understand them.
It is crucial that you continuously stay on top of the material,
because every new topic and every new homework builds on previous results.
If you don't understand the material at the beginning, it will be difficult
to catch up later.
Please do not wait until the last moment to do your homework -- start thinking
about the problems on the day they are handed out!
Homeworks will usually be assigned on Mondays, and the solutions
are due on the Monday of the next week, at 8:00am.
You are welcome to turn in your homework
earlier.
I anticipate we will use Gradescope to turn in homeworks. Late homeworks will not be accepted, unless there is a valid serious reason, and that will incur a late penalty.
In any case, late beyond 2 days, even if you have a valid excuse, is not acceptable and I expect the TAs may discuss the solutions in the recitation section on Wednesdays.
The solutions to each homework should preferably be typed, (I encourage you to use Latex).
Figures (automaton, etc.) can be drawn using JFLAP. You are on your own to learn/use this software.
E-Mail submissions of homeworks are not acceptable.
Messy and illegible solutions may not be graded.
If a problem can be interpreted in more than one way, clearly state the
assumptions under which you solve the problem.
In writing your homework, you are allowed to consult any book or
published material. If you do so, please cite the bibliographical data of
your source(s). Simply copying a proof is not sufficient;
you are expected to write it up in your own words, and you must be able to
explain it if you are asked to do so.
Your proofs may refer to course material covered earlier,
and to previous homeworks.
Except for this, all results you use must be proved explicitly.
The graded homeworks will be returned within two weeks by the TA,
and the solutions will be discussed during the discussion sections.
If you have questions about the grading, please contact the TA.
The work you submit in this course must be the result of your individual
effort.
You may discuss homework problems and general proof strategies or algorithms
with other students in the course, but you must not collaborate in the
detailed development or actual writing of problem sets.
This implies that one student should never have in his or her possession a
copy of all or part of another student's homework.
It is your responsibility to protect your work from unauthorized access.
In writing up your homework you are allowed to use any book, paper, or
published material.
However, you are not allowed to ask others for specific solutions, either in
person or by using electronic forums such as newsgroups.
Of course, during the administration of exams any form of cooperation or help
is forbidden.
Any dishonest behavior will be severely penalized and may lead to failure in
the course.
Academic dishonesty has no place in a university;
it is unfair to the majority of the students. Besides, a proper grounding in
firm ethical behavior is essential to being a good citizen, and
the university is probably the last institution that can instill these
values before you step in to the real world as an independent contributor.
