CMSC 28100 Introduction to Complexity Theory

Course Mechanics

Algorithms has an unusually high enrollment this quarter. In order to use most of instructor and TA time to help you learn, we will keep rigid schedules and procedures. Please read the rules below carefully.

Homework

Weekly homework is an important part of the course. If you do not do it, you will not be able to answer questions on the midterms and on the final.

Homework will be posted on Wednesdays on the course homepapge. It will be due the following Wednesday in class. Late homework will be accepted until noon Thursday, with a 30% loss of points.

There will be a problem-solving session, which will review last week's problems.

Students may think together on homework sets, but homework must be written up individually. Do not try to use the internet to find solutions. In general, academic honesty requires that you acknowledge all your sources. Other than the lectures, textbook (and assigned extra reading), and interactions with the TAs and with the instructor, you should explicitly list any help you had. For example:
I discussed this problem with ....
I got the idea to use Dynamic Programming from the book "....."
In any case, you should be able to reproduce the answer on your own.

What you hand in should be your work. It is OK (and can be helpful in learning and understanding the material) to brainstorm with other studdents in the course, but once you have a solution you should mention whom you talked to and write up your own solution.

Violations of the academic honesty policy will be treated according to University policies , and would typically lead at least to a failing grade.

Please write legibly. Staple pages together, and put your name on the homework. Do not send solutions by email.

Homework will have three kinds of questions:

Do exercises. These will be corrected, if you wish us to do so, but will not earn points. If you are sure you know how to do them, don't do them. They are a check for yourself that you know the material.
Normal problems.
Extra credit problems. You should try (and sometimes succeed) solving some of these in order to get an A in the course. They will also be used to decide borderline grades.

Communication

We will be using Piazza to answer questions quickly. CLICK here TO SIGN UP NOW! Brief Piazza etiquette:

Do not post answers to homework problems, or give strong hints to solutions.
It is good to ask questions. It may save hours of confusion or useless work.
Feel free to answer questions on Piazza (but remember 1.)
One of us will try to answer (or confirm a student's answer) ASAP
Before asking a question, check whether it has been asked/answered.

We appreciate clarity, and demand civility.

Teaching Staff

Instructor:
Janos Simon
165 Ryerson
email: simon (at) cs.uchicago.edu

Office Hours: TBA and by appointment

TA:
David Kim. Office hours TBA Ryerson 165

Grading

Approximate weights: 20% homework, 15% 1st midterm, 20% 2nd midterm 40% final.
Even though homewrok has relatively low weight, it is very important. This is reflected in two additional grading policies:

In order to get an A you will have to solve some of the extra credit problems
You final grade cannot be higher than your homework grade. (Homework grades will be curved).