Math 577-2, A look inside "The Nature of Computation", Spring 2020

Information TypeData
Meeting TimeTuTh 9:30—10:45;
Meeting Room MATH 514
InstructorProfessor Marek Rychlik
OfficeMathematics 605
Homepage (Mirror)

Office Hours

PersonnelDay(s) of the WeekHourRoomComment
Marek RychlikTu10:50—11:50Mathematics 605 Regular Office Hours in my office
Marek RychlikTu11:50—12:50Mathematics 605 Regular Office Hours in my office
Marek RychlikTu12:50—1:50Mathematics 605 Regular Office Hours in my office

Required Texts

The Nature of Computation, Edition: first, Author: Cristopher Moore, ISBN: 978-0199233212, e-ISBN: ???, Publisher: Cambridge University Press, Date published: October 6, 2003, Pages: 640, required.

Required Examinations And Other Grade Components

  • Five homework assignments, worth 16% of the course grade each, for a total of 80%. (This requirement was modified: there will be 4 homework assignments, worth 25% of the course grade each.)
  • A take-home Final worth 30%. (This requirement was modified: there is no final exam, take-home or otherwise.)

Homework, and take-home final, shall be submitted as a typed paper, with the exception of these graphs and figures which cannot be easily drawn with software. The work shall be submitted electronically, as a PDF document, through D2L, using the Dropbox feature of D2L.

The student is expected to be comfortable with scientific computing. Most of the homework will involve writingt small programs in a programming language chosen by the student.


  1. Basic programming skills are required. Familiarity with MATLAB is useful, as the instructor will use it as means of illustrating fundamental ideas.
  2. General background expected of a graduate student pursuing a science degree.


Homework is assigned throughout the semester.

Extra Credit Assignments

Overall Course Objectives and Expected Learning Outcome

  1. Be able to correctly assess computational complexity of computational problems.
  2. Be able to apply different computing paradigms to tasks at hand.
  3. Be able to understand the computational cost of various types of algorithms.
  4. Be able to use physical intuition and heuristics in problem solving.
  5. Be able to formulate parallel algorithms and carry out parallel computations.
  6. Be able to understand basic notions fundamental to quantum computations.

Course Outline

Week Dates Topics Sections Covered
1Jan 15—Jan 17 Measuring complexity.
2Jan 20—Jan 24 Dynamic programming and greedy algorithms. Discrete vs. continuous optimization. Chapter 1
3Jan 27—Jan 31 Review of graphs and NP-hard problems, e.g. finding Hamiltonian paths, cliques, etc. Chapter 1
4Feb 3—Feb 7 Review of graphs and NP-hard problems, e.g. finding Hamiltonian paths, cliques, etc. Chapter 2, 3
5Feb 10—Feb 14 Solving problems by message passing. Belief propagation.
6Feb 17—Feb 21 Solving problems by message passing. Belief propagation.
7Feb 24—Feb 28 Ising-type models. Sampling. Partition function.
8Mar 2—Mar 6 Ising-type models. Sampling. Partition function.
Mar 9—Mar 13Spring Recess.
9Mar 16—Mar 20 Graphical models.
10Mar 23—Mar 27 Graphical models.
11Mar 30—Apr 3 Counting.
12Apr 6—Apr 10 Phase transitions in computing.
13Apr 13—Apr 17 Phase transitions in computing.
14Apr 20—Apr 24 Basics of quantum computing.
16Apr 27—May 1 Basics of quantum computing.
17May 4—May 6 Review. All.
17May 7 Reading Day - no classes or finals
Finals WeekMay 14 (Thursday) Final Exam, 8:00 am - 10:00 am (regular room). NOTE: This class has no final exam.

Course Policies

Attendance Policy

Students are expected to attend every scheduled class and to be familiar with the University Class Attendance policy as it appears in the General Catalog. It is the student's responsibility to keep informed of any announcements, syllabus adjustments or policy changes made during scheduled classes.

Expected Classroom Behavior

Students are expected to behave in accordance with the Student Code of Conduct and the Code of Academic Integrity. The guiding principle of academic integrity is that a student's submitted work must be the student's own. University policies can be found at

Threatening Behavior

See No prohibited behavior will be tolerated.

Administrative Drop

Students who miss the first two class meetings will be administratively dropped unless they have made other arrangements with the instructor.

Missed Exams

Students are expected to be present for all exams. If a verifiable emergency arises which prevents you from taking an in-class exam at the regularly scheduled time, the instructor must be notified as soon as possible, and in any case, prior to the next regularly scheduled class. Make-up exams and quizzes will be administered only at the discretion of the instructor and only under extreme circumstances. If a student is allowed to make up a missed exam, (s)he must take it at a mutually arranged time. No further opportunities will be extended. Failure to contact your instructor as stated above or inability to produce sufficient evidence of a real emergency will result in a grade of zero on the exam. Other remedies, such as adjusting credit for other exams, may be considered.

Accessibility and Accommodations

Disabled students must register with Disability Resources and be identified to the course instructor through the University's online process in order to use reasonable accommodations.

It is the University's goal that learning experiences be as accessible as possible. If you anticipate or experience physical or academic barriers based on disability, please let me know immediately so that we can discuss options. You are also welcome to contact Disability Resources 520-621-3268 to establish reasonable accommodations.

Please be aware that the accessible table and chairs in this room should remain available for students who find that standard classroom seating is not usable.

Policy on the grade of "I" (incomplete)

The grade of "I" will be awarded if all of the following conditions are met:

  • The student has completed all but a small portion of the required work.
  • The student has scored at least 50% on the work completed.
  • The student has a valid reason for not completing the course on time.
  • The student agrees to make up the material in a short period of time.
  • The student asks for the incomplete before grades are due, 48 hours after the final exam.


Changes to the Syllabus

The information contained in the course syllabus, other than the grade and absence policies, is subject to change with reasonable advance notice, as deemed appropriate by the instructor.