## Instructor:

Dr. Marc Rubin## When and Where:

Monday, Wednesday: 8:00 - 9:50 AM9.20.17 - 12.01.17

GRC 124

## Contact:

marc.rubin <at> osucascades <dot> eduTYKH 302H

## Office hours:

M/W: 10-4:30T/Th: 12 - 4:30

## Prerequisites

CS 261, MTH 231 or CS 225## Course Description

Recurrence relations, combinatorics, recursive algorithms, proofs of correctness.## Course Content:

- Big Oh notation
- Recursion and recurrence relations
- Algorithm runtime analysis
- Fundamental sort algorithms
- Graph theory and search algorithms
- Basics of formal languages and automata
- Turing machine decidability
- Time complexity
- Advanced algorithms

## Learning Outcomes

- Use O, Omega, Theta and simple recurrences to analyze the time complexity of iterative and recursive algorithms
- Porve correctness of algorithms
- Implement recursive, iterative, and heuristic algorithms
- Prove that a problem is NP-complete using reductions

## Grading:

Homework | 40% |

Test I | 15% |

Test II | 15% |

Final Project | 15% |

Weekly Quizzes | 15% |

A: >= 92%; A-: 90-91;

B+: 87-89; B: 82-86; B-: 80-81

C+: 77-79; C: 72-76; C-: 70-71

D+: 67-69; D: 62-66; D-: 60-61

F: <= 59

## Learning Resources

Analysis of Algorithms (2nd Edition) by McConnell## Other resources

- Introduction to Algorithms (3rd Edition) by Cormen et al.
- Algorithms by Dasgupta et al (2006)

## Statement Regarding Students with Disabilities:

Accommodations for students with disabilities are determined and approved by Disability Access Services (DAS). If you, as a student, believe you are eligible for accommodations but have not obtained approval please contact DAS immediately at 541-737-4098 or at http://ds.oregonstate.edu. DAS notifies students and faculty members of approved academic accommodations and coordinates implementation of those accommodations. While not required, students and faculty members are encouraged to discuss details of the implementation of individual accommodations.

## Rules in a nutshell

"no hands." When viewing the work of others, your hands should not be doing anything, and you should leave the discussion empty-handed.## On Collaboration & Academic Integrity

Students are encouraged to discuss and collaborate as much as possible. However, it is obviously not acceptable to copy another student’s solution. Your work must be your own. In addition, simply copying solutions found online is not acceptable. Be aware that homework assignments, projects and exams will not just focus on producing correct code, but explaining how things work.

Being enrolled in this course means that you pledge to uphold the high standards of academic ethics and integrity expressed by the Oregon State University Student Conduct and Community Standards by which you are bound. In particular, you will not misrepresent the work of others as my own, nor will you give or receive unauthorized assistance in the performance of academic coursework. You should understand that your instructor would report any infraction of academic integrity to the Office of the Dean and that any such matter would be investigated and prosecuted fully. Typically, the penalty is a grade of F in the course.

## Examples of Academic Misconduct

Please note the following examples of what is considered inappropriate.- Viewing another student’s quiz, test, paper, or code while working on your own.
- Directly providing another student a copy, electronic or otherwise, of your work.
- Accepting a copy, electronic or otherwise, of another student’s work.
- Copying and pasting any component of another student’s work into your own.
- Copying solutions found online or otherwise, pasting it into your own work without proper citation.

**These scenarios will be considered as academic misconduct except when involving an assigned project partner.**