CSCI 432: Advanced Algorithm Topicss, Fall 2019

This repository is for class materials for CSCI 432 in Fall 2019, 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.

Course Outcomes and Objectives

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.
• Design NP completeness reductions.
• Analyze algorithms from recent research publications.

When and Where?

When? MWF 15:10-16:00 Where? Roberts 218

How do I contact you?

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: TW 16:30-17:30, and by appointment. In Barnard 259.
• TA: Brad McCoy: F 10:00-11:00. In Barnard 259.

What is in this repository?

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).
• README.md: the course syllabus
• extra-credid.md: List of Extra Credit assignments

The schedule is at the bottom of this Markdown file. If you want to learn more about Markdown, check out this tutorial.

Accessing this Repo

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/csci-432-fa19.git

Other Course Tools

• Group discussions, questions, and announcements will be through the discussion board on D2L.
• Homework and exams will be graded on Gradescope.

Grading

Your grade for this class will be determined by:

• 30% Homework (individual and group)
• 30% Project
• 35% Exams
• 5% In-class Exercises

A grade above an 85 will earn at least an A-, above a 70 will earn at least a B-, and above 60 will earn at leat a C-.

• 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.
• Project: Groups will be assigned. You will be creating a video presentation of a "modern" algorithm.
• 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%.
• In-class Exercises: At least 10 need to be submitted.
• Opportunities to earn extra credit by attending colloquia and other events will be announced in class and posted on the course website. To earn the extra credit (typically five points towards a HW), 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

Class Policies

Policy on Class Attendance

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.

Policy on Collaboration

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.

Classroom Etiquette

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 the attendance grade.

Withdrawing

After 31 October 2019, 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.

Special Needs Information

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.

Diversity Statement

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.

MSU Policies

Academic Integrity

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.

MSU Drug and Alcohol Policies

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.

## Resources

### Technical Resources

- [Git Udacity
  Course](https://www.udacity.com/course/how-to-use-git-and-github--ud775)
- [Forking in Git](https://help.github.com/articles/fork-a-repo/)
- [Markdown](http://daringfireball.net/projects/markdown/)
- [More Markdown](https://www.markdowntutorial.com/)
- [Inkscape Can Tutorial](http://tavmjong.free.fr/INKSCAPE/MANUAL/html/SoupCan.html)
- [Plagiarism Tutorial](http://www.lib.usm.edu/legacy/plag/pretest_new.php)
- [Ott's 10 Tips](http://www.ms.uky.edu/~kott/proof_help.pdf)
- [Big-O, Intuitive Explanation](https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/)

### Course Textbook(s) 

* Introduction to Algorithms, Third Edition} by Cormen, Leiserson, Rivest, and
  Stein (CLRS). 
* _Elements of Programming Interviews_ (EPI) by Azis, Lee, and~Prakash.  Please
  bring this book to class on Fridays.

## Schedule

Each week, we assign:
- CLRS reading: should be skimmed before class, read after class
- EPI reading: read introductions of chapters and select problems
- Additional readings: skim before class, read after class

### Week 1 (26 August)
- Topics: Intro to Analysis of Algorithms; Induction
- Reading: CLRS, Chapter 2; EPI, Chapter 13
- Additional Reading: [Induction Review](https://www.cs.montana.edu/brittany/teaching/algorithms/15_fall/docs/induction.pdf)

### Week 2 (2 September)
- **MONDAY, 2 September, is Labor Day Holiday!**
- Topics: Divide and Conquer, Recurrence Relations, Asymptotics
- Reading: CLRS, Chapter 4; EPI, Chapter 15
- Additional Reading: [Pseudocode 1](https://onlinelibrary.wiley.com/doi/pdf/10.1002/0470029757.app1) and [Pseudocode 2](https://www.cs.oberlin.edu/~asharp/cs383/2007fa/handouts/pseudocode.pdf)

### Week 3 (9 September)
- Topics: Randomized Algorithms
- Reading: CLRS, Chapters 5 & 7; EPI, 5.12 & 5.13

### Week 4 (16 September)
- Topics: Models of Computation & Order Statistics & Loop Invariants
- Reading: CLRS, Chapter 8 & 9  
- Additiona Reading: [Savage, Ch. 1, Section 4](http://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation_Chapter1_v2.pdf)

### Week 5 (23 September)  
- Topics: Dyamic Programming 
- Reading: CLRS, Chapter 15; EPI, Chapter 16  
- Additional Reading: TBD  

### Week 6 (30 September)  
- **EXAM I: 30 September 2019 (Monday)**
- Topics: Greedy Algorithms
- Reading: CLRS, Chapter 16; EPI, Chapter 17

### Week 7 (7 October)
- Topics: Amortized Analysis
- Reading: CLRS, Chapter 17; EPI, Chapter 12

### Week 8 (14 October)
- Topics: Union-Find Data Structure and Connected Components
- Reading: CLRS, Chapters 21 and 22; EPI, 18.1--3

### Week 9 (21 October)
- **EXAM II: 25 October 2019 (Friday)**
- Topics: More Graph Algorithms
- Reading: CLRS, Chapters  24 & 25; EPI, 18.3--6

### Week 10 (28 October)
- Topics: Max Flow / Min Cut and Matching
- Reading: CLRS, Chapter 26; EPI, 18.7--9

### Week 11 (4 November)
- Topics: Linear Programming
- Reading: CLRS, Chapter 29

### Week 12 (11 November)  
- **MONDAY, 11 November, is Veteran's Day Holiday!**
- Topics: Distributed & Parallel Programming
- Reading: EPI, Chapter 19  
- Additional Reading: [Blelloch & Maggs](https://www.cs.cmu.edu/~guyb/papers/BM04.pdf)

### Week 13 (18 November)  
- **EXAM III: 22 November 2019 (Friday)**
- Topics: Computational Geometry and Topology
- Reading: TBA

### Week 14 (25 November)  
- **27--29 November is Thanksgiving Break!**
- Topics: TBA
- Reading: TBA

### Week 15 (2 December)
- **Video Presentation Week**
- group 1 and 10: https://youtu.be/74tzwEzLxiQ
- group 2: https://www.youtube.com/watch?v=shGO7FmmfOs&feature=youtu.be
- group 4: attached
- group 5: https://www.youtube.com/watch?v=rA2uR0s66Cg&feature=youtu.be
- group 6: https://www.youtube.com/watch?v=tp3qVe7H-Wc&feature=youtu.be
- group 7: https://www.youtube.com/watch?v=X4fggkhG54Q&feature=youtu.be
- group 8: https://drive.google.com/file/d/1V-9pR4-GvOrjmQ1-2Nw1QCz2-WzCOa6M/view
- group 9: attached
- group 11: https://www.youtube.com/watch?v=A1J6g1kiLyE&feature=youtu.be
- group 12: https://youtu.be/6Jc5RLOPTEE
- group 13: https://youtu.be/qFD-ErR1erQ

### Finals Week
- Peer Feedback and Self-Assessment (Required Attendance)


# A Note on the Year of Undergraduate Research:

In March 2019, NCUR 2020 will be hosted by Montana State University.  You are
encouraged to attend this conference (for free!).  The deadline for submitting
abstracts for oral and poster presentations is 6 December 2019.  In order to
gain the most out of this conference experience, please submit an abstract so
that you can be an active participant.  The course material we cover in this
class lays the groundwork for research in algorithms, and some of our
assignments and project components will provide steps towards developing your
own research.  If you are interested in submitting to NCUR 2020, I am willing to
guide you with the research and abstract writing.  If you are interested, please
let me know as soon as possible, either in writing or in person.

--- 

This syllabus was created, using wording from previous courses taught by myself, as well as my colleagues.  Thanks all!