Time: TuTh 2:00-3:15 PM
Location: Computer Science 00121 (annex)
Instructor: Avah Banerjee
Office Hours (zoom or in-person): TuTh 3:30-4:30 PM (or by appointment)
Email: banerjeeav [at] mst [dot] edu
Course website: https://www.avahbanerjee.com/cs5200.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:
Understanding basic techniques for developing algorithms such as divide and conquer, dynamic programming, greedy algorithms, use of randomness, amortization, complexity classes, quantum algorithms etc.
Learn how to formally analyze algorithms and prove their correctness.
Apply algorithmic problem solving to real-world inspired problems.
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. Prologue
2. Divide-and-conquer algorithms
3. Decompositions of graphs
4. Shortest paths
5. Minimum spanning tree
6. Applications to number theory and cryptography
7. Dynamic Programing
8. Linear Programming an Network Flow
9. Approximation algorithms
10. Quantum algorithms
9. Computational Complexity
Problem Sets
Homeowrk will be posted here but you must upload your work on Canvas. Only electronic submissions are accepted. Homework must be individual effort.
Grading Policy:
1. Homework will be graded but they do not count towards your overall score. That is, homework has 0% contribution towards your final score. None the less you must submit your homework before the deadline if you want it to be graded and to receive feedback.
2. There will be four exams where the exam with the lowest grade will be dropped. The exam with the highest grade will count towards 40%, second highest 35% and third highest 25% towards your total grades. The exam with the highest grade will count towards 40%, second highest grade 35% and third highest grade 25% towards your total grades. Example: If you score 80, 85, 70, 65 (all out of 100) in the four exams then your weighted score (out of 100) will be 85*0.4+80*0.35+70*0.25 = 79.5.
Tentative exam dates are given below.
Exam - 1 : February 09 , Exam - 2 : March 07, Exam - 3 : April 11, Exam - 4 : May 10 (according to the campus final exam schedule).
except for Exam - 4 all other exams will be held during our regular class time either Tuesday or Thursday.
[ 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 necessarily make you a distance student. As such, all distance students must send me an official confirmation (either through registrar or your advisor) before the first exam in order to receive an waiver for the in-person exam requirement. Finally, even if you are a distance student you must take the exam at the same time (synchronously) with in-person students.]
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 are a serious matter. If you are unsure whether your intended action (such as missing citations/ looking up similar solutions online etc.) may lead to an honor code violation talk to me before submitting your work.
Furthermore, if we find you have plagiarized any part of your exam will get a total of 0 (zero) grade on that exam.
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 ).