CS 5200: Analysis of Algorithms
Section-101, Fall, 2023
Time: Tuesday & Thursday 9:30am - 10:45am
Location: CS Building Room-220
Huiyuan Yang
Email: hyang[at]mst[dot]edu
Office: Room-333 in CS Building
Office hours: 11:00am - 12:00pm (Tu & Th)
Date: 09/05/2023 - 12/08/2023
- Response to questions: Pollev
- Assignment: Canvas
- Textbook: Introduction to Algorithms by CLRS
- Reference: Algorithm Design by Jon Kleinberg and Eva Tardos
- Homework (50%)
- Midterm (20%)
- Final (30%)
Attention:
Due to limited capacity, no permission number will be given for CS5200 section-101.Tentative Schedule
| Lecture | Topic | Slides | References |
| Lec. 1 (08/22/23) | Introduction | slide(pdf) | Ch.1, Ch.2.1 |
| Lec. 2 (08/24/23) | Complexity Analysis | slide(pdf) | Ch.2.2 |
| Lec. 3 (08/29/23) | Asymptotic growth functions | slide(pdf) | Ch.3 |
| Lec. 4 (08/31/23) | Divide and Conquer I | slide(pdf) | Ch.4 |
| Lec. 5 (09/05/2023) | Divide and Conquer II Quick Sort |
slide(pdf) | Ch.7 Homework-1 |
| Lec. 6 (09/07/2023) | Heap sort | slide(pdf) | Ch.6, Ch.12 |
| Lec. 7 (09/12/2023) | Dynamic Programming I Rod cutting |
slide(pdf) | Ch.15 |
| Lec. 8 (09/14/2023) | Dynamic Programming II Matrix-chain Multiplication |
slide(pdf) | Ch.15 |
| Lec. 9 (09/19/2023) | Dynamic Programming III LCS |
slide(pdf) | Ch.15 |
| Lec. 10 (09/21/2023) | Dynamic Programming IV Optimal Binary Search Trees |
slide(pdf) | Ch.15 |
| Lec. 11 (09/26/2023) | Dynamic Programming V Optimal Binary Search Trees |
slide(pdf) | Ch.15 Homework-2 |
| Lec. 12 (09/28/2023) | Greedy Algorithm I | slide(pdf) | Ch.16 |
| Lec. 13 (10/03/2023) | Greedy Algorithm II | slide(pdf) | Ch.16 |
| (10/05/2023) Fall Break | |||
| Lec. 14 (10/10/2023) | Review, Q&A | Reivew slide(pdf) | |
| (9:30am-10:45am, 10/12/2023, CS Room-120) Midterm exam | |||
| Lec. 15 (10/17/2023) | Graph I Basic Concepts |
slide(pdf) | Ch.22 |
| Lec. 16 (10/19/2023) | Graph II DFS & Disjoint sets |
slide(pdf) | Ch.22, Ch.23 |
| Lec. 17 (10/19/2023) | Graph III Minimum Spanning Trees (Kruskal and Prim) |
slide(pdf) | Ch.23 |
| Lec. 18 (10/26/2023) | Graph IV Single-Source Shortest Paths (Dijkstra) |
slide(pdf) | Ch.24 Homework-3 |
| Lec. 19 (10/31/2023) | Graph V Single-Source Shortest Paths (Bellman-Ford) |
slide(pdf) | Ch.24 |
| Lec. 20 (11/02/2023) | Graph VI All-Pairs Shortest Paths (Floyd-Warshall) |
slide(pdf) | Ch.25 |
| Lec. 21 (11/07/2023) | Graph VII Maximum Flow |
slide(pdf) | Ch.26 |
| Lec. 22 (11/09/2023) | Graph VII Maximum Flow |
slide(pdf) | Ch.26 |
| Lec. 23 (11/14/2023) | Linear Programming I | slide(pdf) | Ch.29 |
| Lec. 24 (11/16/2023) | Linear Programming II | slide(pdf) | Ch.29 Homework-4 |
| (11/21/2023 & 11/23/23) Thanksgiving | |||
| Lec. 25 (11/28/2023) | Computational Geometry | slide(pdf) | Ch.33 |
| Lec. 26 (11/30/2023) | NP-Completeness | slide(pdf) | Ch.34 Homework-5 |
| Lec. 27 (12/05/2023) | Final Review | slide(pdf) | |
| (9:30am-10:45am, 12/07/2023, CS Room-120) Final | |||
Homeworks:
Submission is due via Canvas.programming language: C.
- Homework 1: [Link], Deadline: 09-17-2023 11:59pm
- Homework 2: [ Link ], Deadline: 10-06-2023 11:59pm
- Homework 3: [ Link ], Deadline: 11-10-2023 11:59pm
- Homework 4: [ Link ], Deadline: 11-30-2023 11:59pm
- Homework 5: [ Link ], Deadline: 12-08-2023 11:59pm.
Grading Guidelines:
- [Sanity Check]: A sanity check to test the correctness of your proof and your algorithm is to make sure that you use all assumptions given in the problem statement.
- [Collaboration]: You are allowed to collaborate on the homework to the extent of formulating your ideas as a group. However you must write up the solutions to each problem set completely on your own and once your assignment is written up, you must not let others see your solutions. You must also list the names of everyone whom you discussed the problem set with.
- [You may lose points]: Your proofs and explanations should be clear, well-organized and as concise as possible. Your programming should be able to run without errors.
Late Policy:
- Homework is due at midnight on the due date. 20% off after the due time. 40% off 1 day after the due time. 100% off 2 days after the due time.
- There is extra credit for you to earn in each homework. Therefore, no extension except for an emergency reason.
Grading
- The grade will be curved over the entire class.
- If you have questions about the grading of assignment, please contact the TA first within 7 days after the grade has been released.
- If the issue has not been resolved by the TA, please email/talk to me.
- Questions regarding exams and final grades should be addressed to me
Office hours:
| TA | Office hours | Room |
| S M Shovan | Mon time | Room-TBA |
| Colton Walker | Wed 2:00PM - 4:00PM | Room-205 |
Exams
All exams must be taken in-person except in certain circumstances, such as a health issue with written supportting documentations.Midterm exam:
- Time: 9:30am-10:45am, Oct-12-2023 (Thursday)
- Location: CS Building Room-120
- Open book and open notes, hard copies only
- Coverage: All topics through greedy algorithm
- Sample midterm and Solution
Final exam:
- Time: 9:30am-10:45am, Dec-07-2023 (Thursday)
- Location: CS Building 120
- Open book and open notes, hard copies only
- Coverage: All topics
- Final Topics
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. Plagiarism of any part in your homework/exam will lead to 0 (zero) grade on that homework/exam. While students are encouraged to use AI tools (such as ChatGPT) to clarify doubts and deepen their understanding of course concepts, utilizing AI to solve or complete homework problems is strictly prohibited.
COVID Update on Classroom Instruction
(1) For the Fall 2023 semester, in-person courses and assessments are scheduled without distancing between students. (2) Staying home when you are sick and seeking testing when you have symptoms of COVID-19.
Student Mental Health
Missouri S&T offers a range of mental health services to support students for their well-being and mental health. Visiting Missouri S&T Student Mental Health (https://studenthealth.mst.edu/mentalhealth/) for more inforamtion. If you're feeling overwhelmed or stressed, please reach out to these services or discuss any concerns with me.
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).