[Home] [Syllabus] [Assignments] [Resources]

*The syllabus will be updated throughout the semester.* Dates,
topics, assigned reading, and
problem set due dates will be added or might change. All changes in
assigned reading and due dates will be
announced in class (and occasionally by e-mail). While I will do my
best to update the web site
accordingly, it is a student's responsibility to keep track of the
problem set due dates and reading assignments. If you are not sure
about due dates, please don't hesitate to ask.

Reading assignments are listed for the day when the material is first explained in class. You may read the material ahead of the lecture or after, either way is fine.

The midterms, the final, and quizzes are open book, open notes.

The dates for the midterm exams are set and **will not**
change. If you have a conflict with these dates, please let me know
**right away**. No makeup exams will be given unless there are
circumstances beyond your control AND the makeup time is arranged in
advance.

In addition to exams there will be 8-10 short in-class quizzes throughout the semester. Quizzes will not be announced in advance. The lowest quiz grade will be dropped (i.e. not counted towards the quiz total).

*Problem sets and labs* are individual work, unless otherwise
stated. While it's perfectly
OK (and is encouraged) to discuss the problem sets in general terms
with others in the class, your solution **must
be** your own work. Copying any part of another person's
solution (even if you modify the code) is considered academic
dishonesty and will be dealt with according to the university's
policy.

Reading assignments use the following abbreviations:

- Sipser -
*Introduction to the Theory of Computation*by Michael Sipser - CLRS -
*Introduction to Algorithms*by Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein

**Late problem sets policy:**
Problem sets are due in the beginning of the class on the due
date. If a problem set is submitted at (or before) the next class meeting
after the due date, it is graded out of 3/4 credit. If it is submitted any
time after the next meeting (until the last class meeting), then it is graded
out of 1/2 credit.

Problem sets submitted more than 5 minutes after beginning of the class
may be considered late.

Hand in one assignment from the entire group with names of both students on the first page. If submitting by e-mail, you must CC it to your partner(s). In a programming assignments make sure to keep track (on CVS, in comments or in some other electronic form) of each partner's contribution to the project.

Generally all group members get the same grade for the submitted
group work. If you feel that your group members are not contributing
the way they should or if there are any circumstances that prevent you
or you partner from contributing a fair share, please talk to your
partners to work out an arrangement (if possible) and in either case
**let me know right
away**. If after the assignment is finished you feel that the group
members have contributed unevenly, please talk to me and I'll try to
come up with a fair grading strategy.

Discussion with students other than those in your group (or anyone not
in this class) should be limited to general approaches to the
problem. All such discussions as well as use of sources other than the
textbook and the handouts given in class **must be acknowledged**
in the beginning of the problem solution.

Studying in groups is strongly encouraged. You may study for tests, go over textbook materials or lecture notes, and discuss problem sets in general terms (i.e. without actually writing the formulas or giving out the answers).

Monday | Tuesday - Lab | Wednesday | Friday |
---|---|---|---|

Week 1: August 27 - 29 | |||

Summer break, no class | Summer break, no class |
Introduction; algorithms; review of Big-O notation. Reading: CLRS Ch. 1, 3. |
More on Asymptotic function growth notations. Problem set 1: Big-O notation. Due Fri., Sept. 5. |

Week 2: September 2 - 5 | |||

Labor day, no class. | Experimenting with function growth rates. |
Pseudocode notations, complexity of algorithms. Correctness of an algorithm, loop invariants. Reading: CLRS Ch. 2. |
Approaches to complexity analysis of algorithms. Reading: CLRS Ch. 4. Problem set 1 due. Problem set 2: algorithm analysis. Due Fri., Sept. 12. |

Week 3: September 8 - 12 | |||

Recurrences. Reading: CLRS Ch. 4. |
Algorithm development and analysis. |
Recurrences (cont.), the master theorem. |
Sorting algorithms. Reading: CLRS Ch. 6, 7 (up to 7.2). Problem set 2 due. Problem set 3: recurrences. Due Fri., Sept. 19. |

Week 4: September 15 - 19 | |||

Sorting algorithms (cont.). Randomized algorithms. Reading: CLRS Ch. 5, 7.3, 7.4. |
Algorithm development and analysis. |
Non-comparison sorting algorithms. Reading: CLRS Ch. 8. |
Non-comparison sorting algorithms (cont.). Problem set 3 due. Problem set 4: analysis of sorting algorithms. Due Fri., Sept. 26. |

Week 5: September 22 - 26 | |||

Strings, graphs, sets, proofs. Reading: Sipser Ch. 0 (especially sections on graphs, strings, sets, and proofs). |
Algorithm development and analysis. |
Finite automata. Reading: Sipser Ch. 1.1 |
Finite automata (cont.) Problem set 4 due. Problem set 5: background for computability theory; finite automata. Due Fri., Oct. 3. |

Week 6: September 29 - October 3 | |||

Nondeterministic finite automata. Reading: Sipser Ch. 1.2 |
Algorithm development and analysis. |
Regular expressions. Reading: Sipser Ch. 1.3. |
The pumping lemma. Reading: Sipser 1.4. Problem set 5 due. Problem set 6: NFA, regular expressions. Due Fri., Oct. 10. |

Week 7: October 6 - 10 | |||

The pumping lemma (cont.). |
Practice with DFA using JFLAP. |
Context-free grammars. Reading: Sipser 2.1 |
Context-free grammars (cont.). Q&A session for the midterm. Problem set 6 due. Problem set 7: context-free grammars. Due Fri., Oct. 18. |

Week 8: October 13 - 18 | |||

Midterm I (covers material up to Friday, Oct. 3). | Practice with NFA, regular expressions using JFLAP. |
Pushdown automata. Reading: Sipser 2.2. |
Pushdown automata (cont.). Problem set 7 due. Problem set 8: pushdown automata. Due Fri., Oct. 24. |

Week 9: October 20 - 24 | |||

Fall break, no class | Fall break, no class |
Turing machines. Reading: Sipser 3.1. |
More on Turing machines, Church-Turing thesis. Reading: Sipser 3.2, 3.3. Problem set 8 due. Problem set 9: Turing machines. Due Fri., Oct. 31. |

Week 10: October 27 - 31 | |||

More on Turing machines, Church-Turing thesis. Reading: Sipser 3.2, 3.3. |
Start working on programming algorithms for the robot competition. |
Decidability. Reading: Sipser 4.1. |
The halting problem. Reading: Sipser 4.2. Problem set 9 due. Problem set 10: Turing machines, decidability. Due Fri., Nov 7. |

Week 11: November 3 - 7 | |||

Time complexity: class P problems vs class NP problems. Reading: Sipser 7.1, 7.2, 7.3. |
Continue working on the robot competition. |
Time complexity: examples of class NP problems; P vs. NP question.
Reading: Sipser 7.3. |
NP-completeness. Reading: Sipser 7.4, parts of 7.5. Problem set 10 due. Problem set 11: Turing machines, decidability. Due Fri., Nov. 14. |

Week 12: November 10 - 14 | |||

Overview of space complexity. Reading: Sipser parts of 8 (details TBA). |
First competition day. |
Applications to cryptography. Reading: Sipser 10.6. |
Dynamic programming. Reading: CLRS Ch. 15. Problem set 11 due. Problem set 12: Space complexity, applications. Due Wedn., Nov. 26. |

Week 13: November 17 - 21 | |||

Dynamic programming (cont.). Q&A session for the midterm. |
Midterm II. Covers material up to Wedn. November 12th. |
Greedy algorithms. Reading: CLRS Ch. 16. |
Greedy algorithms (cont.). |

Week 14: November 24 - 28 | |||

Graphs, graph algorithms. Reading: Ch. 22, 23, 24. |
Improving your robot algorithms. |
Graph algorithms (cont.). Problem set 12 due. Problem set 13: greedy algorithms. Due Fri., Dec. 5 |
Thanksgiving holiday - no class |

Week 15: December 1 - 5 | |||

Graph algorithms (cont.). |
Final robotic competition! |
Graph algorithms (cont.). |
A topic from CLRS. Problem set 13 due. Problem set 14: graph algorithms. Due Fri., Dec. 12 |

Week 16: December 8 - 12 | |||

A topic from CLRS. | TBA |
A topic from CLRS. |
Last day of classes Review and wrap up. Problem set 14 due. Last day to submit any late work. |

Final exam: Wed, Dec 17 1:30-3:30pm in Sci 2185 |

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.