[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 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 5-8 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). A missed quiz will receive a grade of zero and thus will be counted as the lowest grade, unless it was missed due to an illness or other circumstances beyond your control. If you missed a quiz or a lab because of an illness or similar circumstances, it is your responsibility to communicate these reasons to me as soon as possible and arrange for a make-up work.

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

*Problem sets and labs* are individual work, unless otherwise
stated. While it's perfectly
OK (and is encouraged) to discuss problem sets in general terms
with others in the class, your solution **must
be** your own work (i.e. written or coded by you without using
anybody else's materials). 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.

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 all your partner(s).
In a programming
assignments make sure to keep track (in comments or in some other
electronic form) of each partner's contribution to the work.

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
partner(s) 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. Use of **any**
materials from previous
runs of this class is **not allowed**.

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).

Use of laptops for class-related activities is usually allowed, except for test time and other specific assignments. Laptops and other devices may not be used for activities unrelated to the class work (checking e-mail, text messaging, etc.). The instructor reserves a right to ask a student to leave the class if the student uses electronic devices inappropriate in a class. No communication devices can be used during a test, including quizzes. If you are taking notes on your laptop, you are not allowed to access anything other than your notes during a test.

Reading assignments use the following abbreviations:

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

Monday | Wednesday | Thursday - Lab | Friday |
---|---|---|---|

Week 1: August 24 - 26 | |||

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

Week 2: August 29 - September 2 | |||

Pseudocode notations, complexity of algorithms. Reading: CLRS Ch. 2. |
Correctness of an algorithm, loop invariants. |
Algorithm development and analysis: sorting. |
Approaches to complexity analysis of algorithms. Reading: CLRS Ch. 4. Problem set 1 due. Problem set 2: algorithm analysis. Due Fri., Sept. 9. |

Week 3: September 5 - 9 | |||

Labor day, no class. |
Recurrences. Reading: CLRS Ch. 4. |
Algorithm development and analysis: sorting (cont.) |
Recurrences (cont.), the master theorem. Problem set 2 due. Problem set 3: recurrences. Due Fri., Sept. 16. |

Week 4: September 12 - 16 | |||

The master theorem (cont.) |
Sorting algorithms. Reading: CLRS Ch. 6, 7 (up to 7.2). |
Algorithm development and analysis: bin packing problem. |
Sorting algorithms (cont.). Reading: CLRS Ch. 5, 7.3, 7.4. Problem set 3 due. Problem set 4: analysis of sorting algorithms. Due Fri., Sept. 23. |

Week 5: September 19 - 23 | |||

Sorting algorithms (cont.). |
Non-comparison sorting algorithms. Reading: CLRS Ch. 8. |
Algorithm development and analysis: matching problem. |
Non-comparison sorting algorithms (cont.). Problem set 4 due. Problem set 5: non-comparison sorting. Due Fri., Sept 30. |

Week 6: September 26 - 30 | |||

Strings, graphs, sets, proofs. Reading: Sipser Ch. 0 (especially sections on graphs, strings, sets, and proofs). |
Finite automata. Reading: Sipser Ch. 1.1 |
Sorting competition, day 1. |
Finite automata (cont.) Problem set 5 due. Problem set 6: computability background, finite automata. Due Fri., Oct 7. . |

Week 7: October 3 - 7 | |||

Finite automata (cont.) |
Nondeterministic finite automata. Reading: Sipser Ch. 1.2 |
Practice with DFA: introduction to JFLAP. Sorting competition, day 2. |
Nondeterministic finite automata (cont). Problem set 6 due. Problem set 7: finite automata Due Fri., Oct. 16. |

Week 8: October 10 - 14 | |||

Q&A review session for the midterm. |
Midterm I. |
Sorting competition: the competition! Practice with NFA. |
Regular expressions. Reading: Sipser Ch. 1.3. Problem set 7 due. Problem set 8: NFAs. Due Fri., Oct. 21. |

Week 9: October 17 - 21 | |||

Fall break, no class |
Regular expressions (cont.). |
Regular expressions using JFLAP and in Java. |
The pumping lemma. Reading: Sipser 1.4. Problem set 8 due. Problem set 9: regular expressions, the pumping lemma. Due Fri., Oct. 28. |

Week 10: October 24 - 28 | |||

Context-free grammars. Reading: Sipser 2.1 |
Context-free grammars (cont.). |
Sorting competition: presentations. |
Pushdown automata. Reading: Sipser 2.2. Problem set 9 due. Problem set 10: CFGs, pushdown automata. Due Fri., Nov 4. |

Week 11: October 31 - November 4 | |||

Pushdown automata (cont.). |
Pumping lemma for context-free languages. Reading: Sipser 2.3. |
The pumping lemma, context-free grammars, and pushdown automata with JFLAP. |
Overview of deterministic context-free languages. Reading: Sipser 2.4. Problem set 10 due. Problem set 11: pumping lemma for context-free languages. Due Fri., Nov. 11. |

Week 12: November 7 - 11 | |||

Turing machines. Reading: Sipser 3.1. |
More on Turing machines, Church-Turing thesis. Reading: Sipser 3.2, 3.3. |
Turing machines with JFLAP. |
Decidability. Reading: Sipser 4.1. Problem set 11 due. Problem set 12: Turing machines, decidability. Due Wedn., Nov. 23. |

Week 13: November 14 - 18 | |||

The halting problem. Reading: Sipser 4.2. |
Review for the midterm. | Midterm II. |
Time complexity: class P problems vs class NP problems. Reading: Sipser 7.1, 7.2, 7.3. |

Week 14: November 21 - 25 | |||

NP-completeness. Reading: Sipser 7.4, parts of 7.5. |
Dynamic programming. Reading: CLRS Ch. 15. Problem set 12 due. Problem set 13: time complexity, decidability, NP-completeness. Due Fri., Dec. 3 |
Thanksgiving holiday - no class | Thanksgiving holiday - no class |

Week 15: November 28 - December 2 | |||

Dynamic programming (cont.). |
Greedy algorithms. Reading: CLRS Ch. 16. |
Greedy algorithms (cont.). |
Graphs, graph algorithms. Reading: Ch. 22, 23, 24. Problem set 13 due. Problem set 14: dynamic programming, greedy algorithms, graph algorithms. Due Fri., Dec. 9 |

Week 16: December 5 - 9 | |||

Graph algorithms (cont.). |
A topic from CLRS. |
Dynamic programming. |
Last day of classes Review and wrap up. Problem set 14 due. Last day to submit any late work. |

Final exam: Thu., Dec 15 2016 11am - 1pm 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.