[Home] [Syllabus] [Assignments and Labs] [Resources]
Both the midterm and the final exams are open book, open notes.
Note that 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.
Reading assignments use the following abbreviations:
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.
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 me 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.
Monday  Tuesday  Lab  Wednesday  Friday 

Week 1: August 28  Sept 1  
Introduction; algorithms; review of BigO notation. Reading: CLRS Ch. 1, 3. 
Experimenting with function growth. 
More on Asymptotic function growth notations. Problem set 1: BigO notation, algorithm analysis. (due Fri., Sept. 8) 
Pseudocode notations, complexity of algorithms. Correctness of an algorithm, loop invariants. Reading: CLRS Ch. 2. 
Week 2: Sept. 4  8  
Labor day, no classes 
Algorithm development and analysis. 
More on complexity of algorithms and bigO approximation. Reading: CLRS Ch. 4. 
Recurrences. Reading: CLRS Ch. 4. Problem set 1 due Problem set 2: algorithm analysis, recurrences. Due Fri., Sept 15. 
Week 3: Sept. 11  15  
Recurrences (cont.), the master theorem. 
Algorithm development and analysis. 
Sorting algorithms. Reading: CLRS Ch. 6, 7 (up to 7.2). 
Sorting algorithms (cont.). Randomizing algorithms. Reading: CLRS Ch. 5, 7.3, 7.4. Problem set 2 due Problem set 3: analysis of sorting algorithms. Due Fri., Sept 22. 
Week 4: Sept. 18  22  
Noncomparison sorting algorithms. Reading: CLRS Ch. 8. 
Matching problem. 
Noncomparison sorting algorithms (cont.). 
Strings, graphs, sets, proofs. Reading: Sipser Ch. 0 (especially sections on graphs, strings, sets, and proofs). Problem set 3 due Problem set 4: background for computability theory; finite automata. Due Fri., Sept 29. 
Week 5: Sept. 25  29  
Finite automata. Reading: Sipser Ch. 1.1 
Practice finite automata.  Finite automata (cont.) 
Nondeterministic finite automata. Reading: Sipser Ch. 1.2 Problem set 4 due Problem set 5: NFA, regular expressions. Due Fri., Oct. 6. 
Week 6: October 2  6  
Regular expressions. Reading: Sipser Ch. 1.3. 
Practice with DFA, regular expressions. 
The pumping lemma. Reading: Sipser 1.4. 
The pumping lemma (cont.). Problem set 5 due Problem set 6: contextfree grammars. Due Fri., Oct. 20. 
Week 7: October 9  13  
Contextfree grammars; Q&A session for the midterm.. Reading: Sipser 2.1 
Practice with NFA.  Midterm I (covers material up to Friday, Oct. 6). 
Contextfree grammars (cont.). 
Week 8: October 16  20  
Fall break, no class.  Fall break, no class. 
Pushdown automata. Reading: Sipser 2.2. 
Pushdown automata (cont.). Problem set 6 due Problem set 7: pushdown automata. Due Fri., Oct. 27. 
Week 9: October 23  27  
Turing machines. Reading: Sipser 3.1. 
Turing machines. 
More on Turing machines, ChurchTuring thesis. Reading: Sipser 3.2, 3.3. 
Decidability. Reading: Sipser 4.1. Problem set 7 due Problem set 8: Turing machines, decidability. Due Fri., Nov. 3. 
Week 10: October 30  November 3  
The halting problem. Reading: Sipser 4.2. 
Start working on programming algorithms for the robot competition. 
Time complexity: class P problems vs class NP problems. Reading: Sipser 7.1, 7.2, 7.3. 
Time complexity: examples of class NP problems; P vs. NP question.
Reading: Sipser 7.3. Problem set 8 due Problem set 9: P vs. NP. Due Fri., Nov. 10. 
Week 11: November 6  10  
NPcompleteness. Reading: Sipser 7.4, parts of 7.5. 
Continue working on the robot competition. 
Overview of space complexity. Reading: Sipser parts of 8 (details TBA). 
Applications to cryptography. Reading: Sipser 10.6. Problem set 9 due Problem set 10: Space complexity. Due Fri., Nov. 17. 
Week 12: November 13  17  
Dynamic programming. Reading: CLRS Ch. 15. 
First competition day. 
Dynamic programming (cont.). 
Greedy algorithms. Reading: CLRS Ch. 16. Problem set 10 due Problem set 11: dynamic programming, greedy algorithms. Due Fri., Dec. 1. 
Week 13: November 20  24  
Greedy algorithms (cont.). 
Improving your robot algorithms. 
Graphs, graph algorithms. Reading: Ch. 22, 23, 24. 
Thanksgiving Holidays, no class. 
Week 14: November 27  December 1  
Graph algorithms (cont.). 
Final robotic competition! 
Graph algorithms (cont.). 
Graph algorithms (cont.). Problem set 11 due Problem set 12: graph algorithms. Due Mon., Dec. 11. 
Week 15: December 4  8  
Review for the midterm.  Midterm II (1 hour 50 minutes, covers material up to Friday Dec. 1).  A topic of your choice from CLRS.  A topic of your choice from CLRS. 
Week 16: December 11  14  
A topic of your choice from CLRS. Problem set 12 due 
TBA 
Last day of classes Review and wrap up. Last day to submit any late work. 

Final exam: 11am1pm Thur, Dec 21., 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.