Time: TuTh 2:00-3:15 PM
Location: Computer Scince Room 207
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:
Introduces fundamental techniques and analytical tool for design and analysis of algorithms. This course 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 etc.
Learn 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 or equivalent.
Textbook (required)
Dasgupta, S., Papadimitriou, C. H., & Vazirani, U. V. (2008). Algorithms (p. 336). New York: McGraw-Hill Higher Education.
Syllabus
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. NP-completeness
10. Approximation and huristic algorithms
11. Quantum algorithms
Problem Sets
You must upload your work on Canvas. Only electronic submissions are accepted.
For problem sets submit either a word or a pdf document. You can scan your handwritten work and submit electronically. However, your submission must be legible otherwise it will not be graded.
Problem Set 1 (Due January 31th, 11:59PM CST)[PDF]
Problem Set 2 (Due February 14th, 11:59PM CST)[PDF]
Problem Set 3 (Due March 2th, 8:00 AM CST)[PDF]
Problem Set 4 (Due March 21th, 11:59 PM CST)[PDF]
Problem Set 5 (Due April 11th, 11:59 PM CST)[PDF]
Problem Set 6 (Due April 25th, 11:59 PM CST)[PDF]
Grading Policy:
1. 7 problem sets (to be done individually unless otherwise stated), out of which lowest two scores will be dropped = 16% x 5 = 80%. Depending on the problem set you will get somewhere bewteen 24HRS to 7 Days to submit. Think of them as mini take-home exams. There will no in-class exams.
2. Programming Project (20%) [Implimenting some algorithm from a recently published paper], this can be done as a group (max group size 2)
Late submissions are not accepted for homework (problem sets). A late submission is only accepted if one or both memebers have some official documented reason and will be co sidered at a case by case basis.
In the unlikely event that the class modality changes to online, grading policy will remain as above
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.
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.