CS 360

Analysis of Algorithms

Spring 2024

Instructor:

101 (9:00am) - Dr. David Babcock, dbabcock@ycp.edu
102 (8:00am) - Prof. Dean Zeller, dzeller@ycp.edu

Section(s) Instructor Office hours

101 (9:00-9:50AM KEC119) David Babcock dbabcock@ycp.edu KEC 117 M 1-3pm, T 2-3pm, W 1-2pm, R 9:30-11am, or by appointment

102 (8:00-8:50AM KEC119) Dean Zeller, dzeller@ycp.edu KEC136 or by appointment

Section(s)	Instructor	Office hours
101 (9:00-9:50AM KEC119)	David Babcock dbabcock@ycp.edu KEC 117	M 1-3pm, T 2-3pm, W 1-2pm, R 9:30-11am, or by appointment
102 (8:00-8:50AM KEC119)	Dean Zeller, dzeller@ycp.edu KEC136	or by appointment

Course Description

This course studies fundamental algorithms, strategies for designing algorithms and mathematical tools for analyzing algorithms. Fundamental algorithms studied in this course include graph algorithms; algorithms for sorting and searching; hashing; integer arithmetic; and selected combinatorial tasks. Mathematical tools include asymptotic notations and methods for solving recurrences. Algorithm design strategies include the greedy method, divide-and-conquer, dynamic programming, and randomization.

Prerequisites

CS201 – Fundamentals of Computer Science II - with a grade of 2 or higher

CS350 – Data Structures - with a grade of 2 or higher

MAT235 - Discrete Math OR ECE335 - Computations in Discrete Mathematics OR MAT280 - Mathematical Structures - with a grade of 2 or higher

Textbook

Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms: 4th Edition , MIT Press, 2022.

Supplemental Reference

Knuth. The Art of Computer Programming: Vol 1-3 .

Course Structure and Expectations

Class meetings will be primarily a discussion of various algorithmic analysis concepts illustrated through pseudocode implementations. It is important to come to class prepared to ask questions related to the topic and/or work on practice exercises which are designed to reinforce the concepts from the lecture notes. There will be a series of written homework assignments to be completed individually.

All the programming assignments are cross platform using C/C++ with the CLion IDE (using the included CMake build system), see the Resources page for installation instructions.

There will be written homework assignments, a midterm empirical comparison report, four midterm exams, and a final project.

We will be covering a significant amount of material in the course at a rapid pace, so it is imperative that you keep up by participating in the class meetings.

Learning Outcomes

By the end of this course, you will be able to:

To apply asymptotic notation for the analysis of algorithms
To derive the efficiency of insertion, merge, heap, and quicksort sorting algorithms
To solve problems using the techniques of dynamic programming and greedy algorithms
To implement graph algorithms for solving BFS, DFS, MST, shortest path, and maximal flow problems
To gain a basic understanding of the concept of NP-completeness and several approximation algorithms applied to NP-complete problems

Policies

Grades

Your overall grade for the course will be determined as follows:

Homework assignments: 10%
Midterm empirical comparison report: 5%
Midterm exams: 75%
Final project: 10%

Grades are assigned on a 100-point scale:

Numeric Range Letter Grade

90-100 A (4.0)

87-90 B+ (3.5)

80-87 B (3.0)

77-80 C+ (2.5)

70-77 C (2.0)

60-70 D (1.0)

0-60 F (0.0)

Numeric Range	Letter Grade
90-100	A (4.0)
87-90	B+ (3.5)
80-87	B (3.0)
77-80	C+ (2.5)
70-77	C (2.0)
60-70	D (1.0)
0-60	F (0.0)

Course website

Please check the course web page, http://ycpcs.github.io/cs360-spring2024/, regularly for important announcements.

Reading Assignments

Reading assignments are posted on the course schedule. I expect you to do the reading before class. Class time will be for asking questions about parts of the reading you did not understand to your satisfaction.

Homework assignments

Programming assignments will consist of written questions along with occasional implementation of pseudocode algorithmic solutions to the problems. Collaboration on homework assignments is encouraged, but each student must submit their own solutions that demonstrate their understanding of the material.

Each student will self-assess their assignment solutions using the posted solutions making corrections in red ink.

All homework assignments will be submitted as a single .pdf to Canvas. If you have handwritten solutions, PLEASE USE A SCANNER APP to generate the .pdf. You are responsible for ensuring your submission is legible.

Late assignments will be marked down 20% per day late. No credit will be given for assignments that are more than three (3) days late.

Empirical Comparison Report

Several homework assignments will include implementation of various sorting algorithms to generate empirical data for different size inputs. The comparison report will require students to examine the fit of the empirical data to asymptotic bounds, and then provide a detailed discussion of how the different sorting algorithms compare with each other. Further details will be provided later in the semester.

Exams

No make-up exams will be given without approval of the instructor prior to class unless proof of extreme emergency or illness is provided.

You must receive a score of 70+ on AT LEAST ONE exam to earn a passing grade for the course.

Exams will include an in-class portion along with a take-home portion. The in-class portion will be closed book, but you will be allowed to use all the resources from the course including the textbook, lecture notes, example problems/solutions, and homework solutions for the take-home portion. All exams will be submitted as a single .pdf to Canvas. If you have handwritten solutions, PLEASE USE A SCANNER APP to generate the .pdf. You are responsible for ensuring your submission is legible.

No credit will be given for late or illegible exams.

Final Project

The project will be on a topic of interest not covered in class. The intent is to provide an opportunity for the student to investigate current research. The project will consist of a short written report and an oral presentation. Further details will be provided later in the semester.

Attendance

Students are expected to attend all scheduled classes and read the appropriate text material prior to class. If you must miss a class, it is your responsibility to notify the professor prior to class. Students are responsible for all material covered in class.

You may work ahead and submit any assignments early, but you must not fall behind. Class time is intended to be used for answering questions about the reading, labs, and assignments. You are responsible for keeping up with the reading assignments as described in the schedule.

Professionalism

I expect you to conduct yourself as a professional in this course. Professionalism includes:

Respect for and courteous interaction with peers, faculty and facilities;
Integrity, which includes at its core honesty, responsibility and accountability for one’s own actions;
Sensitivity and appreciation for diverse cultures, backgrounds, and life experiences;
Constructive evaluation, which means that criticism is offered and accepted in a productive manner;
Self-reflection and identification of one’s own strengths and weaknesses;
Responsibility for one’s own education and learning;
An attitude that fosters professional behavior in colleagues and peers;
Punctuality at meetings and class sessions;
Attentive behavior during class sessions, avoiding personal or social use of cell phones, laptops, or other electronic devices;
Acknowledgement of the Kinsley Engineering Center as a professional workplace, and treatment of this facility as a business or office space, not as an informal space.

I reserve the right to enforce this code through the York College Code of Student Conduct.

Academic Integrity Policy (Philosophy Statement)

For the full policy, go the the Academic Standards section of the current Course Catalog https://www.ycp.edu/about-us/offices-and-departments/registrar/catalogs/.

York College of Pennsylvania, as an institution of higher education, serves to promote and sustain the creation, acquisition, and dissemination of knowledge. In order to fulfill this purpose, an environment of integrity, dependability and honesty must be maintained by all members of the York College community. Without a foundation based on intellectual honesty and integrity, the very ability to uphold the academic endeavors that York College strives to pursue is inhibited.

Academic integrity involves two fundamental expectations:

Anything you turn in as your own work is, in fact, your own work and your own words, completed without assistance, unless your instructor has given explicit permission otherwise.
Anything you turn in is truthful. Lab data were generated in the lab (and not made up), hours worked for an internship or coop were actually worked, etc.

YCP’s academic integrity policy includes a non-exhaustive list of activities that are prohibited. Some of the commonly encountered prohibited activities include:

Plagiarism (passing someone else’s words or ideas off as one’s own without proper attribution).
Getting assistance from other students on non-collaborative assignments. You are permitted (and encouraged) to get assistance from your instructor and the Academic Success Center.
Sharing papers, exams, homework assignments, etc. with other students (even if it wasn’t your intent to cheat).
Ghostwriting (getting someone else to write a paper/assignment, whether it is a friend, an essay mill, or a generative AI tool).
Using unauthorized assistance on exams (e.g., cheat sheets, websites, publisher test banks, other students).
Buying/sourcing assignment answers from other people (whether it is other students, a website like Chegg, or other online sources).
Turning in papers/assignments completed in other classes.

This is not a complete list of prohibited activities. Check out the policy in the catalog for a more comprehensive list. The onus is on you, the student, to verify that any exceptions are allowed in this class by your instructor.

Instructors have full discretion to assign a sanction up to and including a grade of 0 in the class for violations of the policy. Violations will be reported to the Associate Provost of Student Success as outlined in the policy. You cannot withdraw from a class if you have been charged with an academic integrity violation.

If at any point you are unsure whether something is allowed under the academic integrity policy, please ask your instructor!

Instructor’s policy

The following policy pertains specifically to all graded work in this course:

All graded (individual) assignments are to be completed individually. I encourage you to discuss high level concepts with other students, but any work you submit must be yours alone.
Direct copying of solutions or work from other students, web sites, or other sources is absolutely forbidden under any circumstances.
Any sources (books, websites, articles, fellow students, etc.), except for the course textbook and lecture notes, that you consult in completing an assignment must be properly acknowledged. In general, I strongly discourage you from using any resource not explicitly listed in the course syllabus or on the course web page but rather asking the instructor for assistance.
Exams must be completed individually using only the resources from the course.

Use of Personal Technology in the Classroom

While York College recognizes students’ need for educational and emergency-related technological devices such as laptops, PDA’s, cellular phones, etc., using them unethically or recreationally during class time is never appropriate. The college recognizes and supports faculty members’ authority to regulate in their classrooms student use of all electronic devices.

Communication Standards

York College recognizes the importance of effective communication in all disciplines and careers. Therefore, students are expected to competently analyze, synthesize, organize, and articulate course material in papers, examinations and presentations. In addition, students should know and use communication skills current to their field of study, recognize the need for revision as part of their writing process, and employ standard conventions of English usage in both writing and speaking. Students may be asked to further revise assignments that do not demonstrate effective use of these communication skills.

Student Accessibility Services

York College of Pennsylvania offers a variety of academic accommodations to students with documented disabilities to ensure their success. To request accommodations, please contact Student Accessibility Services at (717)-815-1717 or sas@ycp.edu. Student Accessibility Services will discuss the confidential process of requesting accessibility services and establish the accommodations for which the student is eligible.

There is a possibility that during this course, classroom lectures may be recorded in accordance with York College of Pennsylvania policies for Student Accessibility Services.

Disclaimer

This syllabus is subject to change by the instructor.