This repository is for class materials for TODO-courseinfo, taught by Prof. Fasy.
Course Catalog Description: In this course, we explore the field of algorithms. In particular, we will cover concrete time and space complexity; combinatorial algorithms; greedy algorithms; dynamic programming; probabilistic and randomized algorithms; branch-and-bound algorithms.
By the end of this course, a student will be able:
- to understand graduate level algorithms and data structures, including graph and network flow algorithms, techniques such as dynamic programming and greedy methods, and randomized and approximation algorithms.
- to understand and discuss recent papers on algorithms.
If you are enrolled in this course, I expect that you know (or are willing to learn quickly) the following:
- Program in your language of choice.
- Cloning a git repository. (at least well enough to access the course information)
- LaTex.
- Proof by induction (both weak and strong form).
- Solving recurrence relations.
- Discrete probability.
- Basic algorithms, including DFS, BFS, Dijkstra's SP, and binary search.
- Asymptotic notation.
- Computing distances, including Euclidean (L2) and other Lp distances.
When? T,H 8:00 - 8:50
Where? Wilson 1138
electronic: The preferred method to ask questions relating to this class is a public post on the course discussion board on D2L. If you would prefer to ask the question privately, please use the D2L email system.
in person: My office hours are posted on the CS website.
phone: x4804
The folders in this repository contain all materials for this class.
- lec_notes: Copies of lecture notes and/or board photos.
- hw: homework assignments, as well as a LaTex template for your submissions.
The schedule is at the bottom of this Markdown file. If you want to learn more about Markdown, check out this tutorial.
The repository is set as public, so you can access all course materials easily. I suggest creating a fork, so that you can use your fork to maintain your own materials for this class. See the resources section below for forking directions.
To clone this repo:
$ git clone https://bitbucket.org/msu-cs/csci532-sp19.git
Your grade for this class will be determined by:
- 25% Homework
- 10% Algorithm Presentation
- 5% Oral Proof
- 25% Midterm
- 25% Final
- 10% Best of Midterm and Final
A grade above an 85% will earn at least an A-, above a 70% will earn at least a B-, above 50% will earn at least D-.
NOTE: Do not ask for me to inflate your grade, unless I have made an error in grading. Asking an instructor to inflate grades is unethical and unprofessional.
All assignments must be submitted by 23:59 on the due date. Late assignments will not be accepted.
For descriptive assignments and reports, the submission should be typeset (in LaTex), and submitted as a PDF both to D2L. Each problem should be started on a fresh page. All submissions must be individually written, unless oterwise specified. Please read the plagiarism policy below carefully.
For code assignments, well organized source code with clear comments should be submitted. In this case, a separate dropbox folder will be created.
Note: Not every question will be graded: some may be chosen to be graded for completeness, others for correctness, and others not at all.
The Midterm will consist of five questions, of which at least
In groups of up to three people, you will choose an algorithm and present it to the class. The presentation will be 20-30 minutes long. In these presentations, you must present: the problem being solved and the algorithm that solves it. In addition, you must present either a runtime or space complexity analysis, or a proof of correctness. The presentation should conclude with a brief literature review of what related advancements have been made since the publication of the algorithm. A paper, and related assignments, will contribute toward the grade for this presentation.
Throughout the semester, a list of potential oral proof topics will be given.
This all-or-nothing 5% part of your grade will be
based on whether or not the student has mastered the topic of his/her choosing.
If a failed attempt is made at the oral proof, feedback will be provided and a
re-test can be scheduled after at least one week's time. It is the responsibility
of the student to schedule a time with the instructor for this exam. Be sure to
schedule early. Be prepared to explain the proof, as it is presented in the book,
as well as to answer questions related to the proof.
Collaboration is encouraged on all aspects of the class, except where explicitly forbidden. Note:
- All collaboration (who and what) must be clearly indicated in writing on anything turned in.
- Homework may be solved collaboratively except as explicitly forbidden, but solutions must be written up independently. This is best done by writing your solutions when not in a group setting, and preferably without notes from group meetings. Groups should be small enough that each member plays a significant role.
The integrity of the academic process requires that credit be given where credit is due. Accordingly, it is academic misconduct to present the ideas or works of another as one's own work, or to permit another to present one's work without customary and proper acknowledgment of authorship. Students may collaborate with other students only as expressly permitted by the instructor. Students are responsible for the honest completion and representation of their work, the appropriate citation of sources and the respect and recognition of others' academic endeavors.
Plagiarism will not be tolerated in this course. According to the Meriam-Webster dictionary, plagiarism is `the act of using another person's words or ideas without giving credit to that person.' Proper credit means describing all outside resources (conversations, websites, etc.), and explaining the extent to which the resource was used. Penalties for plagiarism at MSU include (but are not limited to) failing the assignment, failing the class, or having your degree revoked. This is serious, so do not plagiarize. Even inadvertent or unintentional misuse or appropriation of another's work (such as relying heavily on source material that is not expressly acknowledged) is considered plagiarism.
By participating in this class, you agree to abide by the Student Code of Conduct. This includes the following academic expectations:
- be prompt and regular in attending classes;
- be well-prepared for classes;
- submit required assignments in a timely manner;
- take exams when scheduled, unless rescheduled under 310.01;
- act in a respectful manner toward other students and the instructor and in a way that does not detract from the learning experience; and
- make and keep appointments when necessary to meet with the instructor.
Except for note taking and group work requiring a computer, please keep electronic devices off during class, as they can be distractions to other students. Disruptions to the class will result in being asked to leave the lecture, and 1% will be deducted from your course grade.
Per the Code of Conduct for students, no student may come to class under the
influence of drugs or alcohol, as that would not be Fostering a healthy, safe and productive campus and community. See Alcohol and Drug Policies
Website for more
information. In particular, note:
As a federally-funded institution, we must adhere to all federal laws when it
comes to alcohol and drug use or distribution. This holds true for marijuana as
well. Using or distributing marijuana on or off campus is a violation of our
code of conduct even if a student has a medical card or comes from a state in
which marijuana is legal or has been decriminalized.
As noted, the University's alcohol and drug policies apply off campus. Using
drugs and/or alcohol and returning to your residence hall in a disruptive
fashion- either via odor, noise, destruction, etc- can lead to residence life
policy and alcohol or drug policy violations. Remember, not everyone wants to
hear or smell you.
After the add/drop deadline, I will only support requests to withdraw from this course with a ``W" grade if you meet with me during office hours. If you are considering withdrawing from this class, discussing this with me as early as possible is advised. Since this class involves a project, the decision to withdraw must also be discussed with your group.
If you have a documented disability for which you are or may be requesting an accommodation(s), please contact me and Disabled Student Services within the first two weeks of class.
- Git Udacity Course
- Forking in Git
- Markdown
- More Markdown
- Inkscape Can Tutorial
- Plagiarism Tutorial]
- Ott's 10 Tips
- Big-O, Intuitive Explanation
The main text for this course is: Algorithm Design by Kleinberg and Tardos. Pearson, 2006.
Another great reference for algorithms is: Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. MIT, 2009.
Related courses:
- Algorithms, Erin Chambers, SLU
- Algorithms, Jeff Erickson, UIUC and his book
- Graduate Algorithms, Vigoda, Georgia Tech
- Topics: Proof of Termination and Pseudocode
- Reading: Chapters 1-2
- Topics: Loop Invariants & Graphs
- Reading: Ch. 3
- Topics: Greedy Algorithms
- Reading: Ch. 4
- Topics: Divide and Conquer (and Recurrence Relations)
- Reading: Ch. 5
- Topics: More D&C, including FFT
- Reading: Ch. 5 (again)
- Topics: Dynamic Programming
- Reading: Ch. 6
- Topics: DP II
- Reading: Sariel Har-Peled's notes on Frechet Distance - Ch. 30, v 0.1
- Topics: TBA (on Tues) & Midterm (on Thurs)
- Reading: TBA
- Topics: Network Flow, Max-flow
- Reading: Ch. 7
- Topics: Approximation Algorithms
- Reading: Ch. 11
- Spring Break! Enjoy!
- Topics: Linear Programming
- Reading: TBA
- Topics: Randomized Algorithms
- Reading: Ch. 13
- Topics: More Randomized Algorithms
- Reading: TBA
- Topics: Algorithm Presentations
- Reading: none
- Topics: Advanced Topic
- Reading: TBA
- April 30, 12:00 - 13:50 (Note: please verify the time and date for yourself.)
This syllabus was created, using wording from previous courses that I have taught, as well as templates from MSU CFE and COE, as well as David Millman's Spring 2018 Graphics course.