Course webpage: https://meckmann.domains.skidmore.edu/2024Spring/cs305/

Text (Required)

Introduction to Algorithms, 4th Edition
by Cormen, Leiserson, Rivest, and Stein (CLRS)
Publisher: The MIT Press

Other readings as handouts/links.

=====================================================

Assignments

Assignments and class handouts will be available on the World Wide Web at URL https://meckmann.domains.skidmore.edu/2024Spring/cs305/
Please type all assignments and submit pdfs.

=====================================================

Grading Policy

I will first compute the following:

20 % Homework
35 % Midterm Exam
45 % Final Exam


Each exam will have both an in class portion as well as a take home portion. More information on this will be given at the appropriate time.

However, your final grade will be influenced either positively or negatively by how I, the instructor, evaluate you on the following:
a) class participation
b) good attendance (not just physical)
c) increase of performance throughout the semester,
d) quality/effort of your program/homework submissions (aside from just
   correctness)
e) lateness of your program/homework submissions


Class participation includes answering questions in class, asking questions in class, visiting me during office hours, or by appointment and asking questions through email. Class participation is based on my assessment of the student's voluntary contribution, plus their responses to questions I ask them.
If assignments are habitually submitted late or one is more than a couple of days late, then this can negatively effect your overall course grade.
Each exam may be graded on a curve (with exams not turned in not affecting the curve).

In general each curve will have a mean between B- (2.7) and B (3.0), depending on my assessment of the overall performance.

=====================================================

Academic Integrity

I list here the policies by which the students of this class are expected to abide.
1. Skidmore Honor Code and Academic Integrity.
2. The Ethics of Scholarship.

Failure to abide by these policies results in a negative learning environment and you should expect to be held accountable.

=====================================================

Attendance

Please be on time as class will start promptly at the scheduled time.

Attendance is mandatory.

Any exams given cannot be made up. Those students who are absent when an exam is given are given a zero for that exam.
If you must miss class for a valid reason, please inform me ahead of time, via email preferably.
=====================================================

General Health and Safety
The College expects all members of the community to adhere to the College’s COVID-19 health and safety guidelines at all times. Please be aware of the COVID-19 guidelines posted on the College’s website (https://www.skidmore.edu/campus-planning/status-levels.php) and note the differences between Yellow Alert Status (substantial/high transmission levels), and Green Alert Status (low to moderate transmission levels).
If You Are Exhibiting COVID-19 Symptoms
If you think you are exhibiting symptoms of COVID-19, isolate and contact Health Services immediately (health@skidmore.edu, x5550). Please follow Health Services’ recommendations regarding testing and when to safely return to class and public spaces. As with any health-related illness, we ask that you contact Health Services as soon as you can.
Proper Mask Wearing
When mask wearing is required based on the College’s COVID-19 health and safety guidelines, you must wear a mask covering your mouth and nose fully at all times in the classroom. If your mask is not providing sufficient protection because it has slipped in some way, you are responsible for adjusting the fit. If I ask you to wear your mask properly, you must comply, or you can choose to leave the classroom. Academic Integrity Students are expected to follow the Skidmore College Honor Code and code of conduct to the fullest extent. A recommendation of a maximum penalty will be recommended for all violations of the Honor Code.
=====================================================

Honor Code
I hereby accept membership in the Skidmore College community and, with full realization of the responsibilities inherent in membership, do agree to adhere to honesty and integrity in all relationships, to be considerate of the rights of others, and to abide by the college regulations.
Honor Code Statement for Examinations
While taking this examination, I have not witnessed any wrongdoing, nor have I personally violated any conditions of the Skidmore College honor code.
=====================================================

Accommodating Students with Disabilities and Providing Accessibility
If you are a student with a disability and believe you will need academic accommodation, you must formally request accommodation from Meg Hegener, Coordinator of Student Access Services (mhegener@skidmore.edu). You will also need to provide documentation which verifies the existence of a disability and supports your request. For further information, please call 580-8150 to contact Student Academic Services in Starbuck Center.  
=====================================================

Conscientious Religious Observance Policy
If religious observances cause absence from class, campus employment, athletic practice, and/or game days or necessitates accommodations, students should notify their faculty, coaches, or supervisors prior to the date(s) of their absence. New York State policy and Skidmore College policy mandates that students be allowed to make up academic work and/or campus employment requirements without penalty. These accommodations should not reduce the overall expectations of a course nor unduly burden the student requesting accommodation. Faculty must permit students to take a makeup examination without any penalty if they have to miss an examination due to religious observances. Similarly, faculty must permit students to submit missed assignments by an agreed upon due date, without penalty. Although not required, the College highly recommends that students submit written notification of the pending religious observances at the start of the semester or at least one week before the date. As an option, students may use this form. Distributing the written notification during the first week of classes, campus employment, or the start of the athletic season gives students, faculty, coaches, or supervisors time to prepare for the absence. If a student, supervisor, coach, or faculty member feels the policy is being violated, they should contact the Dean of Faculty Office at 518-580-5705 (Palamountain 416), the Dean of Students Office at 518-580-5760 (Case Center 313), or Human Resources at 518-580-5800 (Barrett Center first floor).
=====================================================

Diversity and Inclusion
Skidmore College is committed to fostering a diverse and inclusive community in which members develop their abilities to live in a complex and interconnected world. Consistent with our educational mission, we recognize ourselves as a community that respects individual identities based on varying sociocultural characteristics such as race, ethnicity, gender identity and expression, sexual orientation, national origin, first language, religious and spiritual tradition, age, ability, socioeconomic status and learning style. We strive to create a socially just world that honors the dignity and worth of each individual, and we seek to build a community centered on mutual respect and openness to ideas—one in which individuals value cultural and intellectual diversity and share the responsibility for creating a welcoming, safe and inclusive environment. We recognize that our community is most inclusive when all members participate to their full capacity in the spirited and sometimes challenging conversations that are at the center of the college's educational mission.
=====================================================

Sexual and Gender-Based Misconduct: Title IX Statement
Skidmore College considers sexual and gender-based misconduct to be one of the most serious violations of the values and standards of the College. Unwelcome sexual contact of any form is a violation of students’ personal integrity and their right to a safe environment and therefore violates Skidmore’s values. Sexual and gender-based misconduct is also prohibited by federal and state regulations. Skidmore College faculty are committed to supporting our students and upholding gender equity laws as outlined by Title IX. If a student chooses to confide in a member of Skidmore’s faculty or staff regarding an issue of sexual or gender-based misconduct, that faculty or staff member is obligated to tell Skidmore’s Title IX Coordinator or Title IX Deputy Coordinator. The Title IX Coordinator or Deputy Coordinator will assist the student in connecting with all possible resources for support and options for reporting both on and off campus. Identities and details will be shared only with those who need to know to support the student and to address the situation through the college’s processes. If the student wishes to confide in a confidential resource, the Counseling Center Staff, Health Services, and Victim Advocates (anonymous) are all options available. More information can be found at the Sexual and Gender-Based Misconduct website or by contacting the Title IX Coordinator, Joel Aure (jaure@skidmore.edu), 580-5708, or Deputy Coordinator for Student Affairs, Gabriela Melillo (gmelillo@skidmore.edu), 580-5022.  
=====================================================

Topics

What is an algorithm? What is a computational problem?

Asymptotics (Big O, Big Omega, Big Theta, little o, little omega)

Analyze Insertion Sort, Selection Sort, Merge Sort

Recursion Trees, Recurrence Relations

Logarithms and properties

Master Method

Quicksort / Partition

Probability (Random Variables, Expected Value)

Analysis of Comparison Sorts

Decision Trees

Counting Sort, idea of a Stable Sort, Radix Sort

Greedy Algorithms

Memoization

Dynamic Programming - Optimization problem, Optimal Substructure, Overlapping Subproblems

Global Alignment Problem

Longest Common Subsequence (LCS) Problem

0-1 Knapsack

Min Heaps, Heapsort

Graphs

Amortized Analysis, Potential Method

Connected Components, Disjoint Set Data Structure

slow growth function similar to Inverse Ackermann function

Breadth First Search (BFS), Depth First Search (DFS), Dijkstra's Algorithm

Strongly Connected Components

Minimum Spanning Tree

Prim's Algorithm

Kruskal's Algorithm

Shortest Path

All pairs shortest path

Floyd-Warshall

Repeated Squaring, Repeated Dijkstra's, Repeated Bellman-Ford

Johnson's Algorithm

Network Flow

Ford-Fulkerson

Maximum Flow Mininimum Cut

Edmonds-Karp

Maximum Bipartite Matching

=====================================================