Design and Analysis of Algorithms CptS 350 Floyd 133, MWF

Design and Analysis of Algorithms CptS 350 Floyd 133, MWF 12:10-1pm Instructor: John Miller [email protected] Office location: Floyd 134E Office hours: After class in person Zoom Monday-Friday by appointment TA: Suraiya Akhter [email protected] Office location: Floyd 145 Office hours: Monday and Wednesday 1-4pm by appointment Class web page can be found at http://www.tricity.wsu.edu/ jhmiller See information about summer internships at PNNL

Objectives: To present the mathematical basis for quantitative analysis of algorithms. To introduce students to various types of algorithms and analysis techniques Textbook: “Introduction to Algorithms” 3rd Edition by Corman, et al Course content: Chapters 1-2: Introduction Chapter 3: Growth of functions Chapter 4: Solving recurrences Chapter 5: Probabilistic analysis Selected topics from the following: Chapters 7-9: Sorting and selecting algorithms Chapters 22-23: Graph algorithms

Nuts and bolts Syllabus, lecture notes, and assignments will be posted on the class web page. No partial credit on homework assignments Unlimited attempts on assignments No assignments accepted after the last scheduled class period 20% penalty on assignments submitted after testing on the related material Quizzes are given in class with open book and lecture notes. No mid-term or final exam . Last quiz may be given at the final exam scheduled time. Midterm grades are advisory and will not appear on your transcript. Attendance will be taken as part of class participation. Makeup quizzes will be treated on a case-by-case basis Canvas will NOT be used for course management Grades available by request to instructor Help from instructor available after class and on zoom by request.

Numerical final grade will be the average of average quiz and average assignment scores. Table below will be used to convert numerical final grade to letter grade Numerical-Grade Range 91 Grade 88 Grade 91 Letter Grade A A- 84 Grade 88 B 81 Grade 84 B 78 Grade 81 B- 73 Grade 78 C 70 Grade 73 C 67 Grade 70 C- 63 Grade 67 D 60 Grade 63 Grade 60 D F

Approximate course schedule Week Topics Notes 1 Syllabus and Introduction, Insertion sort HW 1 2 Merge sort HW 2 3 Asymptotic notation, review for quiz 1 HW 3-5 4 Quiz1, evaluate and bound sums HW 6 5 Solving recurrence, review for quiz 2 HW 7-8 6 Quiz2, Tree analysis HW 9-10 7 Tree analysis, Master theorem HW 11-12 8 Review for quiz 3, Quiz3 HW 12 9 Partition, Quicksort HW 13 10 Spring break 11 Indicator random variables, average quicksort HW 14 12 Select by partition HW 15-16 13 Review for quiz4, Quiz4 14 Elementary graph algorithm HW 17-19 15 Minimum spanning trees HW 20-21 16 Review for quiz 5, Quiz5 17 Final exam week

Required statements 1. Reasonable Accommodation: Reasonable accommodations are available for students with documented disabilities or chronic medical conditions. If you have a disability and need accommodations to fully participate in this class, please contact the Access Center in Floyd 269 to follow published procedures to request accommodations. Students may also call or email the Access Center to schedule an appointment with Gretchen Hormel, the campus Access Advisor. Phone 509.372.7352 email: [email protected] https://tricities.wsu.edu/current-students/access/ All disability related accommodations are to be approved through the Access Center. It is a university expectation that students with approved accommodations visit with instructors (in person or via Zoom) within two weeks of requesting their accommodations to discuss logistics.

2. Academic Integrity: Washington State University, a community dedicated to the advancement of knowledge, expects all students to adhere to high expectations of scholarship and the Standards of Conduct for Students. Potential violations of the Standards of Conduct for Students should be referred to the Center for Community Standards. The Center for Community Standards supports students, upholds their rights and responsibilities, and holds them accountable for behavior that doesn’t meet our community expectations. Academic integrity will be strongly enforced in this course. Students who violate WSU’s Academic Integrity Policy (identified in Washington Administrative Code (WAC) 504-26- 010(4) will receive a failing grade on the assessment in question, will not have the option to withdraw from the course pending an appeal, and will be reported to the Center for Community Standards. Cheating includes, but is not limited to, plagiarism and unauthorized collaboration as defined in the Standards of Conduct for Students, WAC 504-26-010(3). If you have any questions about what is and is not allowed in this course, you should ask course instructors before proceeding. If you wish to appeal a faculty member's decision relating to academic integrity, please use the form available at communitystandards.wsu.edu. Contact the Center for Community Standards. If you would like more specific information about the process please contact Jordyn Creighton, Director for Student Services in Floyd 269. Phone 509.372.7433 [email protected]

3. Discrimination and Harassment Policy: WSU is commitment to maintaining an environment free from discrimination, including sexual harassment. This policy applies to all students, faculty, staff, or others having an association with the University. If you feel you have experienced or have witnessed discriminatory conduct, you can contact the WSU Office of Compliance and Civil Rights (CCR) and/or the WSU Title IX Coordinator at 509-335-8288 to discuss resources, including confidential resources, and reporting options. (Visit https://ccr.wsu.edu/ for more information). Most WSU employees, including faculty, who have information regarding sexual harassment or sexual misconduct are required to report the information to CCR or a designated Title IX Coordinator or Liaison. Visit https://ccr.wsu.edu/file-acomplaint/ for more information

4. Class Attendance and Absences: Per Academic Regulation 72, students are responsible for ensuring that they attend all class meetings and complete all in-class and out-of-class work as assigned by the instructor. Students are also responsible for communicating with the instructor should they need to be absent. Students should make all reasonable efforts to attend all class meetings. However, in the event a student is unable to attend a class, it is the responsibility of the student to inform the instructor as soon as possible, explain the reason for the absence (and provide documentation, if appropriate), and make up class work missed within a reasonable amount of time, if allowed. Missing class meetings may result in reducing the overall grade in the class. Special provisions are in effect for (1) university sponsored events, (2) military service, (3) flexible attendance as an access accommodation, (4) observance of religious holidays, and (5) adverse weather conditions. When appropriate campus authorities declare a “Yellow / Delayed or Limited Operations” or “Red / Closed” campus condition (BPPM 50.40‐46), or travel to instructional locations is unsafe, classes may be cancelled or delayed. When a student does not attend due to adverse conditions, the instructor will not penalize the student. See https://tricities.wsu.edu/alerts/weather/ Students who wish to raise a concern about the instructor’s arrangement regarding missed work may follow the Academic Complaint Procedure, Rule 104.

5. Accommodation for religious observances: Washington State University reasonably accommodates absences allowing for students to take holidays for reasons of faith or conscience or organized activities conducted under the auspices of a religious denomination, church, or religious organization. Reasonable accommodation requires the student to coordinate with the instructor on scheduling examinations or other activities necessary for course completion. Students requesting accommodation must provide written notification within the first two weeks of the beginning of the course and include specific dates for absences. Approved accommodations for absences will not adversely impact student grades. Absence from classes or examinations for religious reasons does not relieve students from responsibility for any part of the course work required during the period of absence. Students who feel they have been treated unfairly in terms of this accommodation may refer to Academic Regulation 104 - Academic Complaint Procedures.

6. Lauren’s Promise –I will listen and believe you if someone is threatening you. Lauren McCluskey, a 21-year-old honors student athlete, was murdered on October 22, 2018, on the University of Utah campus by a man she briefly dated. We must all take actions to ensure that this never happens again. University Support and Response for Discrimination and Harassment Discrimination, discriminatory harassment, sexual harassment, and sexual misconduct (including stalking, intimate partner violence, and sexual violence) are prohibited at WSU (see Executive Policy 15 - WSU Policy Prohibiting Discrimination and Harassment, the WSU Standards of Conduct for Students, and relevant employee manuals). WSU has instituted procedures to respond to violations of these laws and standards, programs aimed at the prevention of such conduct, and intervention on behalf of victims. If you are in immediate danger, call 911. If you are experiencing sexual assault, domestic violence, stalking, discrimination or harassment, you have support and options. If you share information with me, please know that I am required to reach out to the Title IX Coordinator in WSU Compliance and Civil Rights (CCR), and CCR will reach out to you with information about on and off campus reporting options and resources. CCR is a system-wide resource (all campuses) which is available for intake consultations for you to learn more about available support. You can reach them directly at 509-335-8288, [email protected], or report online (anonymous reports accepted).

Lauren’s Promise continued You can also speak to a victim advocate, a medical provider, or counselor confidentially about your concerns. Advocates help survivors of crime determine their own needs in regards to their physical and emotional health, reporting options, and academic concerns. At no cost, advocates connect survivors to campus and community services, and provide accompaniment to important appointments Key Policies Reminder July 25, 2022 Page 9 (court, hospital, and police) and support throughout the process. For a list of confidential victim advocates and medical providers, please visit CCR Resources. WSU Police Department (WSU PD) officers and campus security will treat victims of sexual assault, domestic violence, stalking, hate crimes, and other crimes with respect and dignity. WSU PD, campus security departments, CCR, and victim advocates can also help you with safety planning.

Safety and Emergency Notification: Please sign up for emergency alerts on your account at MyWSU to receive notification regarding campus emergencies (including campus closures). Click Update Now! Under “Tri-Cities Emergency Info” to register for notification by text message, e-mail, telephone, or any combination of the three. Providing multiple contact methods will help ensure you receive notifications in a timely manner, and your information will NOT be used for any other purpose. The following video is available to learn about WSU Tri-Cities’ safety and emergency protocols: https://www.youtube.com/watch?v WClaZzSvao4&feature youtu.be. For more information on this subject, campus safety and related topics please view the WSU safety portal

Student Support Services: Academic success can be challenging if you have trouble meeting basic needs like safe shelter, sleep, and nutrition. If you have difficulty affording groceries or accessing sufficient food to eat every day, lack a safe and stable place to live, have an emergency, or just need support, I urge you to contact Student Support Services at 509-372-7433 and review the list of services available on the Student Support Services website. If you have a friend who needs support, consider filling out a Cougar Cares form. The Student Care Network serves the entire WSU system to provide individualized student support, access to resources, and general student assistance. A list of services available on the Student Support Services website. If you have a friend who needs support, consider filling out a Cougar Cares. You may also make a Student Care Network referral at https://studentcare.wsu.edu/ or contact the Tri-Cities campus Student Care Co-Chairs in Floyd 269,Vice Chancellor Anna Plemons, [email protected] and Director Jordyn Creighton, [email protected]

7. Safety and Emergency Notifications: Classroom and campus safety are of paramount importance at Washington State University and are the shared responsibility of the entire campus population. WSU urges students to follow the “Alert, Assess, Act,” protocol for all types of emergencies and the “Run, Hide, Fight” response for an active shooter incident. Remain ALERT (through direct observation or emergency notification), ASSESS your specific situation, and ACT in the most appropriate way to assure your own safety (and the safety of others if you are able). Please sign up for emergency alerts on your account at MyWSU. For more information on this subject, campus safety, and related topics, please view the FBI’s Run, Hide, Fight video and visit the WSU safety portal. Full details can be found at https://provost.wsu.edu/classroom-safety/.

Safety and Emergency Notifications continued: Emergency Evacuations: If the alarm sounds, everyone must leave the building. Try to stay together. Your instructor will be the last one to exit the room, close the door(s), and direct you to the assembly areas. If any student is unable to evacuate, please notify immediately the evacuation coordinator (who will be wearing a green vest. The assembly areas are: 1. East/Floyd/BSEL: the blue emergency pole located directly south of the BSEL sidewalk, parking row 6. 2. CIC and Collaboration Hall: blue emergency pole in row 1, directly down the diagonal sidewalk from the main entrance. 3. Wine Science Center: the WSU sign at the corner of University & George Washington Way 4. ICB: south edge of parking lot 5. Nursing: southeast corner of parking lot, near Chapala Express 6. Student Union Building: Rotary Stage

8. Student Support Services: Academic success can be challenging if you have trouble meeting basic needs like safe shelter, sleep, and nutrition. If you have difficulty affording groceries or accessing sufficient food to eat every day, lack a safe and stable place to live, have an emergency, or just need support, I urge you to contact Student Support Services at 509-372-7433 and review the list of services available on the Student Support Services website. If you have a friend who needs support, consider filling out a Cougar Cares The Student Care Network serves the entire WSU system to provide individualized student support, access to resources, and general student assistance . A list of services available on the Student Support Services website. If you have a friend who needs support, consider filling out a Cougar Cares. You may also make a Student Care Network referral at https://studentcare.wsu.edu/ or contact the TriCities campus Student Care Co-Chairs in Floyd 269,Vice Chancellor Anna Plemons, [email protected] and Director Jordyn Creighton, [email protected]

STUDENTS IN CRISIS – WSU TRI-CITIES RESOURCES If you or someone you know is in immediate danger, DIAL 911 FIRST! Student Care Network: https://tricities.wsu.edu/current-students/cougarcares/ 509372-7433 WSU Tri-Cities Student Emergency Hardship Fund: https://tricities.wsu.edu/current-students/student-emergency-hardship-fund/ WSU Tri-Cities Mental Health Counseling: 509-372-7153 Suicide Prevention Hotline: 800 273-8255 Crisis Text Line: Text HOME to 741741 WSU Tri-Cities Campus Security: 509-372-7698 WSU Tri-Cities Campus Emergency: 509-372-7234 WSU Tri-Cities Deputy Title IX Director: 509-372-7381 Support, Advocacy, and Resource Center (SARC): 888-846-7273 WSU Health Sciences 24/7 Crisis Line: 509-368-6500