This repository is for class materials for CSCI 432 in Fall 2021, taught by Prof. Fasy.
MSU Course Catalog Description: A rigorous examination of advanced algorithms and data structures. Topics include average case analysis, probabilistic algorithms, advanced graph problems and theory, distributed and parallel programming.
From the Instructor: This course is NOT a programming class, and is not structured like the 132 and 232 courses that precede it. In this course, we will do many proofs (especially using induction), and will be writing pseudo-code, not code.
Prerequisites:
CSCI 246 (Discrete) and CSCI 232 (Data Structures and
Algorithms) are a prerequisite for this course.
In particular, a student enrolled in CSCI 432
should be familiar with
sorting and searching algorithms, big-Oh notation,
basic recurrence relations,
heaps, queues, lists, hash tables,
proof by induction and by contradiction, and discrete probability.
Living in Montana, we are on the ancestral lands of American Indians, including the 12 tribal nations that call Montana home today: A’aninin (Gros Ventre), Amskapi/Piikani (Blackfeet), Annishinabe (Chippewa/Ojibway), Annishinabe/Métis (Little Shell Chippewa), Apsáalooke (Crow), Ktunaxa/Ksanka (Kootenai), Lakota, Dakota (Sioux), Nakoda (Assiniboine), Ne-i-yah-wahk (Plains Cree), Qíispé (Pend d’Oreille), Seliš (Salish), and Tsétsêhéstâhese/So’taahe (Northern Cheyenne). We honor and respect these tribal nations as we live, work, learn, and play in this state.
To learn more about Montana Indians, I suggest starting with the following pamphlet: Essential Understandings Regarding Montana Indians
This course introduces students to the analysis and design of computer algorithms. In this course, students will:
- Analyze asymptotic time and space complexity of algorithms.
- Describe algorithmic design paradigms (including dynamic programming, greedy algorithms, divide and conquer) and explain when an algorithmic design situation calls for it.
- Apply methods of analysis (prove correctness, time/space complexity, termination) to new problems.
- Use and analyze major graph algorithms and data structures.
- Analyze algorithms from recent research publications.
When? MWF 15:10-16:00 Where? Roberts 218
Note: if necessary (e.g., if the instructor must quarantine or self-isolate), class will be held via Zoom. If so, a link will be sent via email and via the class discussion board.
The preferred method to ask questions relating to this class is a public post on the group discussion board, or in my office hours.
Office Location: 363 Barnard Hall Office Phone: x4804
Office hours:
- Prof. Fasy: Monday 9:30-10:30, Wednesday after class, and by appointment.
- TA: Dalton Gomez.
Note: These office hours are times that we are available to meet, and will be held via Zoom (please see email for links). Please email or call (x4804) in advance if you plan to join. This will eliminate waiting (both on your end and on our end).
The folders in this repository contain all materials for this class.
-
hw: Homework assignments, as well as a LaTex template for your submissions.
-
lec_notes: Copies of lecture notes and board photos.
-
slides: Source for my Beamer slides (which only happens occasionally).
-
misc.md: List of Miscellaneous assignments (see grading).
-
README.md: The course syllabus.
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://github.com/msu/csci-432-fall2021
Your grade for this class will be determined by:
- 35% Homework (individual and group)
- 30% Project
- 35% Exams
- Homework: All assignments must be submitted by 23:59 on the due date. Late assignments will not be accepted. The lowest two homework grades will be dropped. The submission should be typeset in LaTex, and submitted as a PDF both in D2L and Gradescope. Each problem should be started on a fresh page.
- The miscellaneous assignments will be worth up to 10 points each, and the total sum will count as a HW grade (max grade: 100). If you choose not to do the miscellaneous assigments, that grade will be one of the two lowest homework grades dropped, as mentioned above.
- Project: Groups will be assigned. You will be creating a video presentation of a "modern" algorithm. More details to come.
- Exams: We will have three exams in this course. Each exam will be 10% of the grade, with the best exam counting an additional 5%.
Class attendance and participation is required and expected. If you consistently miss class, then your final grade may be dropped one letter grade (e.g., from B+ to C+).
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. Groups should be small enough that each member plays a significant role.
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 one half-point will be deducted from your final course grade.
After 25 October 2021, I will only support requests to withdraw from this course with a "W" grade if extraordinary personal circumstances exist. 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 both me and the office of Disabled Student Services within the first two weeks of class.
Montana State University considers the diversity of its students, faculty, and staff to be a strength and critical to its educational mission. MSU expects every member of the university community to contribute to an inclusive and respectful culture for all in its classrooms, work environments, and at campus events. Dimensions of diversity can include sex, race, age, national origin, ethnicity, gender identity and expression, intellectual and physical ability, sexual orientation, income, faith and non-faith perspectives, socio-economic status, political ideology, education, primary language, family status, military experience, cognitive style, and communication style. The individual intersection of these experiences and characteristics must be valued in our community.
If there are aspects of the design, instruction, and/or experiences within this course that result in barriers to your inclusion or accurate assessment of achievement, please notify the instructor as soon as possible and/or contact Disability Services or the Office of Institutional Equity.
This syllabus, course lectures and presentations, and any course materials provided throughout this term are protected by U.S. copyright laws. Students enrolled in the course may use them for their own research and educational purposes. However, reproducing, selling or otherwise distributing these materials without written permission of the copyright owner is expressly prohibited, including providing materials (or solutions) to commercial platforms such as Chegg or CourseHero. Doing so may constitute a violation of U.S. copyright law as well as MSU’s Code of Student Conduct.
Masks are required in the classroom, at least through 1 October 2021. The instructor requests that you wear masks as long as Gallatin county is in a "high transmission" status. If you need to miss class due to COVID-19 infection or quarantine (or any other reason), please communicate with the instructor as soon as possible in order to coordinate a plan for making up the missed classwork. As a reminder, attendance is required. If the instructor is unable to make it to class, either a substitute will be found for those lectures or the class will be held via Zoom.
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 Merriam-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.
Per the Code of Conduct for students, no student may come to class under the
influence of drugs or alcohol, as that would not beFostering 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.
- Git Udacity Course
- Forking in Git
- Markdown
- More Markdown
- Inkscape Can Tutorial
- Plagiarism Tutorial
- Big-O, Intuitive Explanation
- Discrete Lecture Notes
- (Required) Algorithms by Jeff Erickson
- (Suggested) Introduction to Algorithms, Third Edition by Cormen, Leiserson, Rivest, and Stein (CLRS).
Each week, we assign:
- Textbook Reading: These are readings from Erickson's Algorithms, please skim before class, and fully read after class.
- Additional Readings: additional resources that your classmates have found helpful. Skim/read as you find appropriate. If you need more resources, ask!
- Topics: Intro to Analysis of Algorithms; Induction; Asymptotic Notation
- Reading: Chapter 0
- Additional Reading: Induction Review
- Topics: Recursion: Runtime and Correctness
- Reading: Appendix II; Chapter 1
- Topics: More Recursion: Correctness and Master Theorem
- Reading: Appendix II; Chapter 1
- Topics: Proof of Termination; Backtracking
- Reading: Chapter 2
- Exam on Wednesday!
- Topics: Dynamic Programming
- Reading: Chapter 3
- Topics: More Dynamic Programming
- Reading: Chapter 3
- Topics: Greedy Algorithms, Loop Invarints
- Reading: Chapter 4
- Additional Reading: Gas Stop Problem
- Topics: Graph Algorithms
- Reading: Chapters 5,6
- Topics: Graph Algorithms (cont.)
- Reading: Chapters 5,6
- Topics: More Graph Algorithms
- Reading: Chapter 7
- Exam on Wednesday!
- Topics: MST and SSSP
- Reading: Chapter 8
- Topics: APSP and Flows
- Reading: Chapter 9 and 10.1
- Topics: Flows and Cuts
- Reading: Chapter 10-11
- Fall Break (no classes)
- Topics: Randomized Algorithms
- Reading: TODO
- We meet Wednesday, 15 December, 14:00-15:50.
- See Finals Week Schedule for university policies.
This syllabus was created, using wording from previous courses taught by myself, as well as my colleagues. Thanks all! If you are teaching an algorithms or related course and wish to use any of the materials, you have permission to do so, as long as solutions to HW questions are not posted online.