UMM CSci 3501 Syllabus, Fall 2006

CSci 3501 Algorithms and Computability

[Home] [Syllabus] [Assignments and Labs] [Resources]

Syllabus

The timeline below is somewhat approximate. Dates, topics, assigned reading, and problem set due dates are subject to 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.

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.

Electronic submission guidelines

If submitting your assignment electronically, please follow these rules:

Text problems: please attach the file as a .pdf, .doc, or .rtf file; do not send a URL.
Programming assignments: you may either attach the files (make sure to attach ALL of them) or send me the file locations. In the latter case do not modify any files after the submission (make a separate copy if you continue working on the program for one reason or another). Make sure to submit documentation for your program, including instructions on how to run it.

Failure to follow the guidelines may result in loosing all or a part of credit for the submitted work.

Groups for labs and problem sets

Labs and some of the problem sets must be done in groups (usually in pairs). Hand in one assignment from the entire group with names of both students on the first page. If submitting a problem set 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 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.

Studying in groups

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 28 - Sept 1

Introduction; algorithms; review of Big-O notation.
Reading: CLRS Ch. 1, 3. Experimenting with function growth. More on Asymptotic function growth notations.
Problem set 1: Big-O 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 big-O 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

Non-comparison sorting algorithms.
Reading: CLRS Ch. 8. Matching problem. Non-comparison 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: context-free grammars. Due Fri., Oct. 20.

Week 7: October 9 - 13

Context-free grammars; Q&A session for the midterm..
Reading: Sipser 2.1 Practice with NFA. Midterm I (covers material up to Friday, Oct. 6). Context-free 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, Church-Turing 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

NP-completeness.
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: 11am-1pm Thur, Dec 21., Sci 2185

Monday	Tuesday - Lab	Wednesday	Friday
Week 1: August 28 - Sept 1
Introduction; algorithms; review of Big-O notation. Reading: CLRS Ch. 1, 3.	Experimenting with function growth.	More on Asymptotic function growth notations. Problem set 1: Big-O 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 big-O 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
Non-comparison sorting algorithms. Reading: CLRS Ch. 8.	Matching problem.	Non-comparison 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: context-free grammars. Due Fri., Oct. 20.
Week 7: October 9 - 13
Context-free grammars; Q&A session for the midterm.. Reading: Sipser 2.1	Practice with NFA.	Midterm I (covers material up to Friday, Oct. 6).	Context-free 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, Church-Turing 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
NP-completeness. 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: 11am-1pm Thur, Dec 21., Sci 2185