CSCI 432: Advanced Algorithm Topics
Fall 2018
Schedule subject to change. Refresh webpage (or hit F5) to view current page.
Lecture
- Monday, Wednesday, Friday 3:10 - 4:00 pm in Roberts (ROBH) 218.
- Lectures will be video taped and put on this website.
Instructor
Sean Yaw
- E-mail: sean.yaw (at) montana.edu (email me whenever, I'll respond as soon as I get it)
- Office: Barnard Hall 352
- Office Hours: Monday, Wednesday, Friday 2:00 - 3:00 pm and by appointment.
Textbook
- Algorithms by Dasgupta, Papadimitriou, and Vazirani. ISBN: 9780073523408. Not required. Can be found online easily.
- Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein (commonly called "CLRS"). Not required. Classic algorithms text.
Course Prerequisites
- CSCI 246: Discrete Structures.
- CSCI 232: Data Structures and Algorithms.
- CSCI 338: CS Theory. Strongly recommended.
Course Objectives
MSU course 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.
At the end of the course, my goal is for you to be able to:
- Given a problem, understand it and develop a clear, efficeint plan to solve it.
- Understand a broad set of algorithmic tools and have an intuition for when to apply which tools, including:
- Dynamic Programming.
- Greedy Approaches.
- Graph Representations.
- Linear Programming.
- Approximation Techniques.
- Understand and be able to comment on the time and space complexity of an algorithm, including being able to characterize recursive relations.
- Understand what NP-Complete problems are, have an intuition for the solvability of new problems, and have familiarity with techniques to deal with NP-Complete problems.
Grading
- Homework - 30% (evenly weighted with lowest dropped). Only a subset of the homework questions will be graded for correctness. The remaining will be graded for effort. I expect you to put in (nearly) the same effort as if they were graded. The goal is to give you practice without fear of failure or temptation to cheat. If you don't put in a good effort, I will dock points and may make more questions graded for correctness in future assignments. Homework solutions need to be typed in an appropriate editor (LaTeX).
- Quizes - 40% (16% for each of your two highest, 8% for your lowest)
- Final Exam - 30%
At the end of the semester, grades will be determined (after any curving takes place) based on your class average as follows:
- 93+: A
- 90+: A-
- 87+: B+
- 83+: B
- 80+: B-
- 77+: C+
- 73+: C
- 70+: C-
- 67+: D+
- 63+: D
- 60+: D-
- 0+: F
Late Policy
If you submit a homework assignment late, but within 12 hours of being due, the maximum credit you can receive is 80%. After 12 hours, you receive 0.
Collaboration Policy
- You may do homework assignments in groups of up to three people. You must indicate on the submission everyone that contributed. If someone did not substantially contribute to a submission, they cannot be included on it.
- Exams are to be taken individually.
- You may not copy or modify solutions that are not your own (e.g. from the internet, from a classmate not listed as a contributor,...) for any graded material. I know how to use the Google and I have a Chegg membership. If you find it, I will too!
- You can use the internet or any other resources you like for questions about formatting LaTeX.
Failure to abide by these rules will result in everyone involved being reported to the Dean of Students and could result in failing the course.