Home Teaching Research Blog + News

CS 5200 Analysis Of Algorithms (Fall 2023, Sec 102 & 103)

Time: Tu-Th 9:30-10:45 AM
Location: Computer Science 00121 (annex)

Instructor: Avah Banerjee
Office Hours (zoom or in-person in CS 309): Tu-Th 10:55-11:55 AM (or by appointment)
Email: banerjeeav [at] mst [dot] edu
Course website: https://www.avahbanerjee.com/cs5200-f23.html
Zoom link: Zoom link for the class and office hours will be avilable on Canvas

Course description:
This course introduces fundamental techniques and analytical tools for design and analysis of algorithms. It is aimed at advanced undergraduates and new graduate students.

Course Outcomes:
Understand basic techniques for developing algorithms, including divide and conquer, dynamic programming, greedy algorithms, the use of randomness, amortization, complexity classes, and quantum algorithms. Learn to formally analyze algorithms and prove their correctness. Apply algorithmic problem-solving techniques to problems inspired by real-world situations.

A "C" or better grade in Comp Sci 2500 (the undergradute version of this course at MS&T) or equivalent.

Required Textbook
Dasgupta, S., Papadimitriou, C. H., & Vazirani, U. V. (2008). Algorithms (p. 336). New York: McGraw-Hill Higher Education. ISBN: 978-0073523408
[There are some other edition(s) of this book which are available online, even though they have the same content, their end of chapter problem sets has some differences and as such their numberings may not match from version to version. Be mindful of this fact when using other versions and always check with your classmates.]
Recomended Textbook
1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms. MIT press.
2. Kleinberg, J., & Tardos, E. (2006). Algorithm design. Pearson Education India.

1. Introduction to Algorithms
2. Divide-and-conquer algorithms
3. Decompositions of graphs
4. Shortest paths
5. Minimum spanning tree
6. Fast Fourier Transformation and applications
7. Dynamic Programing
8. Linear Programming an Network Flow
9. Approximation algorithms
10.Quantum algorithms
11.Computational Complexity

Problem Sets
There will be 6 homework assignments, each worth 5 points. Assignment details will be available on the course website, but submissions must be made via Canvas. Only digital submissions will be accepted. Homework must reflect individual effort. Late Submissions Policy: For each 24-hour period past the deadline, a 10% penalty will be imposed. For example, if you submit your homework 34 hours after the deadline and receive a score of \(X\), your adjusted score, considering the late penalty, will be \(0.9 \times X\).

Problem Set 1 (Due September 8, 11:59PM CST)[PDF]
Problem Set 2 (Due September 30, 11:59PM CST)[PDF]
Problem Set 3 (Due October 31, 11:59PM CST)[PDF]
Problem Set 4 (Due November 15, 11:59PM CST)[PDF]
Problem Set 5 (Due December 1, 11:59PM CST)[PDF]
Practice Final Exam [PDF]

Grading Policy:
1. Homework: 30 points (6 assignments, 5 points each)
2. Midterm: 20 points (Exam date: October 3 2023, 9:30-10:45 AM CS 121)
3. Final Exam: 40 points (Exam date: December 15 2023, 12:30-2:30 PM CS 121)
4. Class Participation: 10 points
[ Exam Modality: All exams must be taken in-person unless you are a distance student. Please note that registering for the online section of the course does not automatically qualify you as a distance student. Therefore, all distance students must send me official confirmation (either through the registrar or your advisor) before the midterm exam to receive a waiver for the in-person exam requirement. Lastly, even if you are a distance student, you must take the exam synchronously with in-person students.]
[ Makeup Exam Policy: If a student is unable to attend a scheduled exam, they may be granted the opportunity to take a makeup exam under specific conditions. Makeup exams are only permitted for students who miss an exam due to unavoidable circumstances, such as a health issue or a family emergency. Documentation or verification may be required. It's essential to note that poor planning, forgetfulness, or other similar reasons are not considered valid grounds for a makeup exam. If you believe you have a legitimate reason to request a makeup exam, please reach out as soon as possible to discuss potential accommodations.]

Academic Integrity
Please review S&T's Honor Code at https://stuco.mst.edu/. Policy regarding student conduct, plagiarism etc. can be found at https://registrar.mst.edu/academicregs/
Honor code violations, including the misuse of AI tools, are grave concerns in this course. If you are uncertain about whether your planned actions, such as utilizing AI for solving assignments, missing citations, or referencing online solutions might breach the honor code, please consult with me prior to submitting your work. Be aware, if it is determined that any portion of your exam or assignment has been plagiarized or completed with prohibited AI assistance, you will receive a grade of zero for that specific submission.

Use of AI
In accordance with the principles of academic integrity and trust in the educational community, students are expected to uphold the highest standards of honesty in their academic endeavors. The following guidelines specifically address the use of artificial intelligence (AI) in the context of this course:

  1. Use of AI for Homework Assignments: Utilizing AI, including but not limited to solutions generated by systems like ChatGPT, to solve or complete homework problems is strictly prohibited. Submitting work generated or significantly aided by AI will be considered a violation of the honor code.
  2. Use of AI for Learning: While AI-generated solutions for assignments are forbidden, students are encouraged to use AI tools such as ChatGPT to clarify doubts, understand course concepts, and deepen their knowledge. It's crucial, however, to differentiate between using AI as a learning tool and letting it complete assignments on your behalf.
  3. Collaboration: Unless explicitly stated otherwise, students are expected to work independently on assignments. While discussions among peers are encouraged for understanding concepts, sharing or copying solutions is an infringement of the honor code.
  4. Consequences for Honor Code Violations: Violations of the honor code will be dealt with seriously. This can range from receiving a zero on the assignment or exam in question, to failing the course, or even referral to higher academic authorities for further action.
  5. Clarifications: If you are ever in doubt about whether a specific action might violate the honor code, please seek clarification from the instructor or teaching assistants. It's always better to ask beforehand than face consequences later.

Diversity, Inclusion and Belonging
My goal is to create a learning environment that supports a diversity of thoughts, perspectives and experiences, and honors your identities (including race, gender, class, sexuality, socioeconomic status, religion, and ability). If something was said in class (by me or anyone else) that made you feel uncomfortable, please talk to me about it. If you feel like your performance in the class is being impacted by your experiences outside of class, please do not hesitate to come and talk with me. As a participant in offline and online course discussions, you should also strive to honor the diverse perspectives of your classmates and teaching staff. (Credit: based on the statement of Dr. Monica Linden at Brown University.)

COVID-19 Policy/ Contingencies
Refer to https://coronavirus.mst.edu/ for up to date information and guidlines regarding COVID-19.

Accessibility and Accommodations
It is the university’s goal that learning experiences be as accessible as possible. If you anticipate or experience physical or academic barriers based on a disability, please contact Student Disability Services at (573) 341-6655, sdsmst@mst.edu, visit http://dss.mst.edu/ for information. Lectures will be recorded and will be available via Panopto.

Nondiscrimination, Equity, and Title IX
Missouri S&T is committed to the safety and well-being of our campus community, and to creating an environment free from discrimination and harassment. The University does not discriminate on the basis of race, color, national origin, ancestry, religion, sex, pregnancy, sexual orientation, gender identity, gender expression, age, disability, protected veteran status, and any other status protected by applicable state or federal law. As used in this policy, the word “sex” is also inclusive of the term “gender.” Additionally, US Federal Law Title IX states that no member of the university community shall, on the basis of sex, be excluded from participation in, or be denied benefits of, or be subjected to discrimination under any education program or activity. Sexual harassment violations of this law include quid pro quo, hostile environment, sexual assault, dating/domestic violence, and stalking. The U.S. Department of Education has stated the prohibition on discrimination on the basis of sex includes sexual orientation and gender identity. Students who are experiencing pregnancy or pregnancy-related conditions, including the birthing parent and non-birthing parent, have rights protected under Title IX. Students should contact the Office of Equity and Title IX to learn more about their rights and pregnancy-related assistance/accommodations provided by the University to ensure equitable access to University educational programs and activities. In accordance with the University of Missouri’s Collected Rules and Regulations, all faculty and staff are required to report any information concerning discrimination disclosed through communication including, but not limited to, direct conversation, email, social media, classroom papers and homework exercises to the Equity Officer/Title IX Coordinator (https://equity.mst.edu ).

Student Mental Health
Your well-being and mental health are paramount to your success as a student. Understanding the challenges of academic life and potential personal stressors, Missouri S&T offers a range of mental health services to support students. For comprehensive information on counseling, workshops, and other mental health resources, visit Missouri S&T Student Mental Health (https://studenthealth.mst.edu/mentalhealth/). Should you ever feel overwhelmed or in distress, please reach out to these services or discuss any concerns with me.