CMPU-241-01 Analysis of Algorithms - Fall 2018 syllabus

Course description

An algorithm is the specification of a method to solve a given problem. This course covers fundamental algorithm design and analysis techniques. These techniques shall provide students with a solid knowledge base, which will allow them to develop correct and efficient algorithms to solve whatever practical computer science problems they may encounter in the future.

Topics covered include:

  • Algorithm analysis
    • Correctness proofs
    • Temporal and spatial complexity
    • NP-completeness
  • Algorithm design techniques
    • Divide-and-Conquer
    • Greedy algorithms
    • Dynamic programming
  • Important algorithms for:
    • Sorting
    • Heaps
    • Priority queues
    • Binary search trees
    • Graphs

Prerequisites

  • CMPU-102
  • CMPU-145

Professor

Rui Meireles

Website: www.cs.vassar.edu/~rpachecomeireles

Email: firstname.lastname@vassar.edu (expected response time: 24 business-day hours, i.e. no response on weekends)

Office: Sanders Physics 304

Office hours: Tuesdays and Thursdays, 4-6 PM. Other times by appointment.

Textbook

Introduction to Algorithms, Third Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.

Grading

  • Participation: 5%
  • Homework: 45%
  • Midterm: 25%
  • Final exam: 25%

Class attendance

Class attendance is not mandatory but strongly encouraged. Students are responsible for ALL information given in class, whether or not it is presented in any other form.

If a student misses a class he/she should consult with classmates to find out about any information—academic, administrative, or other—that he/she may have missed.

Use of electronic devices during class

Use of electronic devices for note taking is permitted. However, devices must be in silent mode at all times so as to not disturb the class. The use of electronic devices for non-class related purposes is prohibited.

Homework

Homework shall be used to consolidate and expand upon concepts introduced in class.

There shall be, on average, a homework assignment every other week.

Homework assignments are due by the beginning of lecture on the specified due date. They should handed in directly to the professor. Assignments received after the beginning of lecture may be considered late. Late assignments will not be graded.

Submitted homework should be clearly legible. Preferably, typed.

As with all policies, homework policies are intended to be fair to everyone involved in the course. Please feel free to ask any questions about special cases that may emerge over the semester.

Policy on collaboration and academic integrity

Students are allowed to collaborate on homework. Students may discuss approaches to solving problems in groups but not supply ready answers to one another. Potential collaborations should be disclosed in the submitted homework.

Collaboration will not be allowed on exams.

Copying solutions to homework or exams is strictly forbidden.

Useful student resources

  • The Quantitative Reasoning Center (ltrc.vassar.edu/qrc/) helps students improve their analytical skills pertaining to quantitative subjects.
  • The Writing Center (ltrc.vassar.edu/writing-center/) helps students improve the clarity and cogency of their writing.

Accessibility and educational opportunity

Academic accommodations are available for students registered with the Office for Accessibility and Educational Opportunity. Students in need of ADA/504 accommodations should schedule an appointment with the professor early in the semester to arrange for said accommodations.

Learning environment

Vassar College is committed to providing a safe and respectful learning environment for all students. An environment free of all forms of discrimination and harassment, including sexual assault, domestic violence, dating violence, and stalking. Vassar College has staff members trained to support students in navigating campus life, accessing health and counseling services, providing academic and housing accommodations, helping with legal protective orders, and more:

  • Counseling Service (counselingservice.vassar.edu, 845-437-5700)
  • Health Service (healthservice.vassar.edu, 845-437-5800)
  • Charlotte Strauss-Swanson, SAVP (Sexual Assault and Violence Prevention) director (savp.vassar.edu, 845-437-7863)
  • SART (Sexual Assault Response Team) advocate, available 24/7 by calling the CRC at 845-437-7333

    • The SAVP website and the Title IX section of the EOAA website (eoaa.vassar.edu/title-ix/) have more information, as well as links to both on- and off-campus resources.