## CSci 3501: Algorithms and Computability

[Home] [Syllabus] [Assignments] [Resources]

Course description: Models of computation (deterministic and non-deterministic machines, Turing machines); approaches to the design of algorithms, determining correctness and efficiency of algorithms; complexity classes, NP-completeness, approximation algorithms. Prerequisites: CSci 2101, CSci 1302.
5 credits.

Course learning objectives:

• The ability to determine time and space requirements for an algorithm.
• Understanding different models of computation and the associated grammars.
• Understanding capabilities and limitations of computers.
• To be able to classify and analyze a problem according to its complexity and computability on a computational model.
• To learn design techniques, strategies, and tools for solving computational problems.

On this page you will find information about:

### Class meetings

 Lecture: M,W,F 1 - 2:05pm Sci 2185 Lab: Th 12-1:50pm Sci 2610

### Instructor

Instructor: Elena Machkasova
Office: Sci 2325, Phone: 6308
Office hours: M,F 10:30-11:30am, M,W,F 2:15-3:15pm, or arrange by e-mail. My weekly schedule is on google calendar.
elenam at morris.umn.edu

### Textbooks and other resources

(available at the University bookstore).

In addition to the book I may occasionally assign extra reading material. Such materials will be available on the resources page. Problem sets will be posted on the assignments page.

You must check your UMM e-mail frequently (at least once a day). I may send clarifications for problem sets by e-mail.

### Grading

The grade for this course will be based on the following:

 Problem sets and labs 45% In-class quizzes 5% Midterm I 15% Midterm II 15% Final 20%

Minor (up to 5%) adjustments may be made to this grade distribution based on how the course progresses. Such adjustments (if any) will be announced in class.

### Grading policies

Basic Grading Scheme: (100-90)% A; (90-80)% B; (80-70)% C; (70-60)% D; below 60% F. Small adjustments may be made for particularly good final exams, class average and other signs of individual effort.

#### Official Grading Policies:

 A achievement that is outstanding relative to the level necessary to meet course requirements. B achievement that is significantly above the level necessary to meet course requirements. C achievement that meets the course requirements in every respect. D achievement that is worthy of credit even though it fails to meet fully the course requirements. S achievement that is satisfactory, which is equivalent to a C- or better (achievement required for an S is at the discretion of the instructor but may be no lower than a C-). F (or N) Represents failure (or no credit) and signifies that the work was either (1) completed but at a level of achievement that is not worthy of credit or (2) was not completed and there was no agreement between the instructor and the student that the student would be awarded an I (see also I) I Incomplete. Assigned at the discretion of the instructor when, due to extraordinary circumstances, e.g., hospitalization, a student is prevented from completing the work of the course on time. Requires a written agreement between instructor and student.

### Other class policies

For policy on late and missed work please see the syllabus.

#### Credits:

One credit is defined as equivalent to an average of three hours of learning effort per week (over a full semester) necessary for an average student to achieve an average grade in the course. For example, a student taking a four credit course that meets for three hours a week should expect to spend an additional nine hours a week on coursework outside the classroom.

#### Academic assistance

The Academic Assistance office on campus provides free tutoring for a variety of introductory courses, and well as general assistance in a host of areas (e.g., study skills, careful reading, and time management).

#### Accessibility and institutional support

The University of Minnesota views disability as an important aspect of diversity, and is committed to providing equitable access to learning opportunities for all students. The Disability Resource Center (DRC) is the campus office that collaborates with students who have disabilities to provide and/or arrange reasonable accommodations.

• If you have, or think you have, a disability in any area such as, mental health, attention, learning, chronic health, sensory, or physical, please contact the DRC office on your campus (UM Morris 320.589.6178) to arrange a confidential discussion regarding equitable access and reasonable accommodations.
• Students with short-term disabilities, such as a broken arm, should be able to work with instructors to remove classroom barriers. In situations where additional assistance is needed, students should contact the DRC as noted above.
• If you are registered with the DRC and have a disability accommodation letter dated for this semester or this year, please contact your instructor early in the semester to review how the accommodations will be applied in the course.
• If you are registered with the DRC and have questions or concerns about your accommodations please contact the Coordinator of the Disability Resource Center.

Additional information is available on the DRC website: http://www.morris.umn.edu/academicsuccess/disability/, or e-mail hoekstra at morris dot umn dot edu.

#### Harassment

University policy prohibits sexual harassment as defined by the University of Minnesota Regents' policy. In general, harassment or intimidation of others in the class for whatever reason is unacceptable (and hardly conducive to a successful learning environment).

#### Equity, diversity, equal opportunity, and affirmative action

The University provides equal access to and opportunity in its programs and facilities, without regard to race, color, creed, religion, national origin, gender, age, marital status, disability, public assistance status, veteran status, sexual orientation, gender identity, or gender expression. For more information, please consult Board of Regents Policy.

#### Regarding academic integrity

From the preface of UMM's Student Academic Integrity Policy:

Scholastic honesty is of fundamental importance to the functioning of any community of scholars. Although the pursuit of knowledge is always a communal project, individual academic achievement must be the result of a person's own efforts and abilities. Members of an academic community are responsible for their own personal and academic development and for fostering an academic climate in which all members draw from and give back to the community. The University is charged with implementing those policies which will help bring about such an academic climate. However, the ultimate responsibility for creating a community of scholars, in which mutual self-respect flourishes, lies with the individual members of the community. Each member must, therefore, act according to the highest standards of academic honesty.

Academic integrity is essential to a positive teaching and learning environment. All students enrolled in University courses are expected to complete coursework responsibilities with fairness and honesty. Failure to do so by seeking unfair advantage over others or misrepresenting someone else's work as your own, can result in disciplinary action. The University Student Conduct Code defines scholastic dishonesty as follows:

Scholastic Dishonesty: submission of false records of academic achievement; cheating on assignments or examinations; plagiarizing; altering, forging, or misusing a University academic record; taking, acquiring, or using test materials without faculty permission; acting alone or in cooperation with another to falsify records or to obtain dishonestly grades, honors, awards, or professional endorsement.

Within this course, a student responsible for scholastic dishonesty can be assigned a penalty up to and including an "F" or "N" for the course. If you have any questions regarding the expectations for a specific assignment or exam, ask.

For more information see:

#### Regarding classroom conduct

Students are expected to interact with the instructor and other students with respect and courtesy. Students should attend every class session prepared to learn and work. Participation in class is expected, which includes both speaking up and listening. Give class your full attention while here. Complete all assignments, including the reading, in a timely fashion. Turn off cell phones and other electronic distractions during class so we may all better focus on the material. Students whose behavior is disruptive either to the instructor or to other students will be asked to leave. Students whose behavior suggests the need for counseling or other assistance may be referred to counseling services. Students whose behavior violates the University Student Conduct Code will be subject to disciplinary action.

#### Some relevant University Senate statements and policies

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.