Algorithm Analysis (Fall 2009)

This class is taught by Jay McCarthy.

We meet in TMCB 120 at 9am MWF.

Jay McCarthy’s office hours are 1pm to 4:45pm in 3328 TMCB.

There is a mailing list hosted at Google Groups. Use it to ask non-revealing questions and receive answers, as well as general course announcements.

1 Meetings

Jay McCarthy will not be present for meetings marked *.

This schedule may change.

2 Projects

This schedule may change.

3 Homework Policy

Each meeting has a list of exercises. You must work on these exercises before the meeting.

Exercise sets must be turned in by 6 PM (Provo time) on the work day prior to the meeting. (A Monday meeting’s exercise set are due on Saturday; a Wednesday meeting’s exercise set are due on Tuesday; a Friday meeting’s exercise set are due on Thursday.) (Why? No, really.)

Exercise sets that are late by a second will receive no credit.

Exercise sets are to be emailed to jay@cs.byu.edu.

The subject line must be: "BYU - Fall 2009 - CS 312 - x" where x is the date the exercises are listed next to.

Only one email should be sent. If two or more are sent, I will grade the oldest one.

Exercise sets must be in the PDF file format such that I can open them in Apple’s "Preview.app". The PDF file must be named "es-2009MMDD.pdf" where MM is the two digit numeric month and DD is the two digit numeric day of the month of the date the exercuses are listed next to.

Each exercise must be annotated with the names of the individuals (such as your supporters or supportees) that helped you on the exercise.

Exercise sets that do not have the correct file format, file name, or email format will receive no credit.

3.1 Projects

Projects are turned in slightly differently from exercise sets:

• Projects are due on the date listed in the Project table.

• The subject line must be: "BYU - Fall 2009 - CS 312 - code" where code is the "Code" of the project (listed in the Project table.)

• You must turn in your assignment in a Zip archive that expands to a directory named code. This directory should contain two directories: "src" where you will put your source code and "bin" where you will put executables. Moreover the code directory should contain a file named "README" with instructions for use and sample timing reports.

The policy on team work is described in Team Work.

4 Participation

Each meeting will be structured as a seminar on the section of the book listed. We will start by looking at the key ideas of the section and conclude by working through the exercises. Since you will have already read the section and attempted the exercises, we will be able to quickly go through what you can understand on your own, but we will spend the neccessary time on what you find difficult.

The majority of the class will not be a "sage on the stage", but rather a collaboration among the students. This will require you, the student, to be an active, responsible participant in class.

For each topic (key idea or exercise), we will choose a student to present the topic to the class. This may mean explaining the key idea well or demonstrating how to complete the exercise correctly, but it may also mean explaining why you don’t understand the key idea or what is difficult about it or going as far as you can in an exercise then explaining why you must stop. For the purposes of this course, this is participation and it warrants a participation point. I repeat: you do not need to understand the topic perfectly to participate well. If you cannot participate on a topic, the next student will be called.

Participation will start on the second day of class with the first student in the alphabetized roll. Our position on the roll will be remembered from day to day and we will loop from the back to front on overflow. This will give everyone roughly an equal opportunity to participate.

5 Support

Each student in the class is assigned two supportees. Each student is the class is assigned two supporters.

This responsibility is broadly defined and is enforced through the support grade component of your final grade.

In rare circumstances, if your supporter is horrible, we can assign you a new one. Similarly, in rare circumstances, if your supportee is horrible, we can avoid the penalty on your final grade.

6 Textbook

We will use the textbook Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. It is available for free online and in print. The online version is the definitive version for the purposes of this course.

7 Grading

This section walks through the computation of your final grade.

7.1 Participation Total

Each time you participate in class (as discussed in Participation), you will get 1 participation point. At the end of the course, your points will be divided by the largest number of points any one student has accrued. (There will be something done to accommodate the disadvantage in the last cycle.) (This not exactly Bell curve grading, but it is similar.)

This is a number between 0 and 1.

7.2 Exercise Total

Each exercise in each exercise set is graded with a number between 0 and 1. You receive 0 if do not try diligently to solve the problem. You receive 1 if you do.

Each exercise set is graded with a number between 0 and 1. This is the unweighted average of each of the constituent exercises.

The 37 exercise sets are averaged to compute your exercise total, which is a number between 0 and 1.

7.3 Exam Grades

The three exams are graded as if they were exercise sets.

These three grades, the quarterm grade, midterm grade, and finterm grade, are used in the final grade computation.

7.4 Support Grade

Your support grade is the average of your supportees’ exercise total, participation total, quarterm grade, midterm grade, and finterm grade.

7.5 Project Total

Each of the five projects is graded with a number between 0 and 1, based on how well you completed the project requirements.

These five grades are averaged to compute your project total, which is a number between 0 and 1.

7.6 Final Numeric Grade

Your final numeric grade is a number between 0 and 1.

Your final numeric grade is computed by the following function when it is called with your exercise total, participation total, support grade, quarterm grade, midterm grade, finterm grade, and project total.

7.7 Final Grade

8 Team Work

The projects for this class will be done in teams (pairs, with a single triple if enrollment is an odd number). This will give you the opportunity to fully discuss a solution with another person. You will work with five different people over the course of the semester.

Programming in teams does not mean each person writes part of the code and the team simply pastes together these contributions. Each person is responsible for every line of code, documentation, etc. turned in. It includes getting or losing points for quality, being able to explain the work, and also incurring penalties in case of plagiarism or other violations. That said, we will sometimes ask you questions individually and, if you are unable to answer them, we may give you less credit than your teammates. In short, working in teams is meant to help you learn material better, not to enable you to do less work than you would have if the project had to be done individually.

For team projects, you may not discuss the project with a student not on your team.

We recommend that teams develop the software together using pair-programming techniques (of the form preached by Extreme Programming) though this is a suggestion, not a requirement. Pair-programming in a nutshell:

• Both programmers share a single computer, monitor, and keyboard.

• One person is the typist, the other watches what is being typed and critiques it.

• Programmers switch roles at regular intervals. (Note that this is also good for preventing RSI!)

• Both programmers jointly own every single line of code, no matter who typed it.

While this does require that you schedule times to work with your team, we think that pair-programming will increase your productivity and aid you in taking responsibility for all of your code.

You may not work with the same partner on multiple projects.

Once you have selected a partner please inform the course staff. If you are having difficulty finding someone to be your partner, please contact us and we will attempt to match you with another student.