Time: TuTh 11:00AM - 12:15PM AM
Location: Computer Science 00221
Instructor: Avah Banerjee
Office Hours (in-person in CS 309): Tu 2:30-3:30 PM and Th 9:30-10:30 AM(or by appointment)
Course website: https://www.avahbanerjee.com/cs5200-s24.html
Zoom link: Zoom link for the class 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.
Prerequisites:
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.
Topics
1. Introduction to Algorithms
2. Divide-and-conquer algorithms
3. Decompositions of graphs
4. Shortest paths
5. Minimum spanning tree and greedy algorithms
6. Fast Fourier Transformation and applications
7. Dynamic Programing
8. Linear Programming an Network Flow
9. Approximation algorithms
10.Randomized algorithms
Problem Sets
There will be 5 homework assignments, each worth 6 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. Submission-specific instructions will be posted along with the homework.
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 Feb 15, 12:00 Noon CST)[PDF]
Problem Set 2 (Due March 05, 9:00 AM CST)[PDF]
Practice Midterm [PDF]
Problem Set 4 (Due Apr 17, 10:00 PM CDT )[PDF]
Problem Set 5 (Due May 01, 10:00 PM CDT )[PDF]
Grading Policy:
1. Homework: 30 points (5 assignments, 6 points each)
2. Midterm: 20 points (Exam date: March 7 2024, 11:00AM-12:15 PM CS 00221)
3. Final Exam: 40 points (Exam date: May 9 2024, 12:30-2:30 PM CS 00221) (see here for details)
4. Recitation Quizzes: 20 points (These activities are conducted in person unless you are registered as a distant student.)
[ Accommodation for Missing Recitations: It is expected that you try to attend as many recitations as possible, not just for participating in graded quizzes, which count towards your grades, but also to use the opportunity to understand homework and practice problems assigned during lectures. We understand that you will not be able to attend some recitations; hence, there are 10 extra points available (the total points you can earn in the course is 110)]
[ Exam Modality: All exams must be taken in person; even if you are a distance student, you must come to class to take the exams unless suitable arrangements can be made with the instructor.]
[ 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 (for example, non-emergency and non-university-sponsored travel is not 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:
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.
Copyright, FERPA, and Use of Video
It is vitally important that our classroom environment promote the respectful exchange of ideas. This entails being sensitive to the views and beliefs expressed during discussions, whether in class or online. Please obtain instructor permission before recording any class activity. It is a violation of University of Missouri policy to distribute such recordings without authorization and the permission of all who are recorded. For more info see here.
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/ and https://wellbeing.mst.edu ). Should you ever feel overwhelmed or in distress, please reach out to these services or discuss any concerns with me.