This repository is for class materials for CSCI 432 in Fall 2020, 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 the 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.
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? T,H 8:00-9:15 Where? Zoom (please see email for link)
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 hours: 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).
- Prof. Fasy: Mondays 14:00-16:00.
- TA: Giorgio Morales Luna. Monday: 1:00 - 2:00 pm. Webex link: https://montana.webex.com/meet/w63x712. E-mail: [email protected]
The folders in this repository contain all materials for this class.
-
README.md: the course syllabus
-
hw: homework assignments.
-
lec_notes: Copies of lecture notes not posted publicly elsewhere.
-
slides: Source for my Beamer slides (which only happens occasionally).
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.
- Group discussions, questions, and announcements will be through Piazza.
- Homework will be graded on Gradescope. All homework should be posted both in Gradescope and in D2L.
Your grade for this class will be determined by:
- Homework (min 25 / max 50 points)
- Group Project (min 15 / max 30 points)
- Exams (min 0 / max 4 points)
- In-class Exercises (min 10 / max 25 points)
- Miscellaneous (min 0 / max 6 points)
- Yes ... that adds up to more than 100! This allows for you to adjust where you put your effort in the class. Hopefully this will help you focus on practicing the skills, and not worrying about the point distribution.
- Minimum points indicate the minimum points necessary to pass the class.
- Maximum points indicate the maximum points allowed in that category.
- The grading for this class is based on a "no grading" policy. The theory here is the more you practice, the better you will become!
- Homework: All assignments must be submitted by 23:59 on the due date. Late assignments will not be accepted. The submission should be typeset in the template provided. Each homework will be graded on the following scale: incomplete (-1), low pass (+0.5), pass (+1), high pass (+2).
- Project: Groups will be assigned. You will be creating a video presentation of a "modern" algorithm.
- Exams: We will give two oral exam questions throughout the semester. You can choose to take one, both, or neither. Grading scale: incomplete (0), low pass (+0.5), pass (+1), high pass (+2).
- In-class Exercises: Each day that we have groupwork in class, you will get credit: not present in groupwork (-1), low pass (+0.5), pass (+1), high pass (+2). (Note: for the first week, not present in groupwork will be zero points instead of -1).
- Miscellaneous: Opportunities to earn points by attending colloquia and other events will be announced in class and posted on the course website. To earn the extra credit, you must attend the entire presentation and write a one-to-two page summary and reflection on the presentation(s). For a list of EC assignments, see extra-credit.md. Credit will be: not attempted (0), low pass (+0.5), pass (+1), high pass (+2).
Class attendance and participation is required, but attendance will not be taken. However, to submit in-class exercises, you must be in class on the day of the exercise.
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.
Please come to class prepared by reading and working on homework problems throughout the week. We welcome questions! In the Zoom breakout rooms, we expect that you are actively working on problems. If needed, start your group by recapping what was discussed right before going into the breakout room or during the class period before. If something is unclear, ask for a clarification from your classmate. If your group is unsure of what the task is, please ask and do not sit idle!
After 15 October 2020, we 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 class will be held synchronously online. However, you (or your family/friends) might become ill with COVID-19 or something else, which can make even remote attendance difficult. If this happens, please communicate with the instructor as soon as possible to minimize impact on your academic experience. Also, we welcome feedback throughout the semester about what is working well / not working well with the online delivery. Doing so will help this be a better experience for all!
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.
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
Each week, we assign:
- Textbook Reading: should be skimmed before class, read after class
- Additional Readings: additional resources that your classmates have found helpful. If you need more resources, ask!
- Topics: Intro to Analysis of Algorithms; Induction
- Reading: Chapter 0
- Additional Reading: Induction Review
- Miro Boards: Tuesday Thursday
- Topics: Recursion, Recursion Invariants, Asymptotics
- Reading: Chapter 1
- HW-1 Due on 27 August
- Topics: Recursion, Termination, Partial Correctness, Master Theorem
- Reading: Chapters 1 (cont.) and Chapter 2
- HW-2 Due on 3 September
- Topics: Backtracking
- Reading: Chapter 2
- Topics: Dynamic Programming
- Reading: Chapter 3
- HW-3 Due on 17 September
- Topics: Dynamic Programming
- Reading: Chapter 3 (cont.)
- Topics: Greedy Algorithms
- Reading: Chapter 4
- Topics: Graph Algorithms
- Reading: Chapters 5,6
- HW-4 Due on 6 October
- Topics: More Graph Algorithms
- Reading: Chapter 7
- HW-5 Due on 12 October
- Topics: Shortest Paths
- Reading: Chapter 8,9
- Topics: Max Flow / Min Cut
- Reading: Chapter 10
- HW-6 Due on 26 October
- 3 November: Vote!!
- Topics: Applications of Flows / Cuts
- Reading: Chapter 11
- Topics: Special Topic
- Reading: TBD
- HW-7 Due on 9 November
- Topics: Special Topic
- Reading: TBD
This syllabus was created, using wording from previous courses taught by myself, as well as my colleagues. Thanks all!