CSCI 332: Advanced Data Structures and Algorithms

Course schedule

Schedule subject to change. Lecture videos in this Panopto folder.

Catalog description

3 Credits. Prereq., CSCI 232 and M 225 or consent of instr. Algorithm design, analysis, and correctness. Commonly used algorithms including searching and sorting, string search, dynamic programming, branch and bound, graph algorithms, and parallel algorithms. Introduction to NP-complete problems.

Course info

This course meets in Education 241 on Tuesdays and Thursdays from 9:30-10:50am.

Class time will be a mix of lecture and active problem solving, both as individuals and as groups. Every week will have a short homework assignment. Most of your homework grade will come from a short homework quiz on Tuesdays, where you will demonstrate your understanding of the algorithm analysis and design topics from the homework.

During class time, I will ask that you refrain from using all laptops and cell phones, except when they are useful for accessing information during group problem solving sessions. I highly recommend that you use paper or a tablet for notetaking, but please let me know if you require an exception to this rule.

Course resources

Textbook

The textbook for this course is Algorithm Design by Jon Kleinberg and Eva Tardos. New copies of the textbook are available in the bookstore, but you may also obtain the textbook in other ways. Either first or second edition is fine.

Lecture videos

Lectures will be recorded and available to watch after class. However, if there are technical difficulties recording a lecture, it will not be re-recorded, so come to class when you can to make sure that you do not miss course content or announcements. Videos can be found in the Panopto folder.

Discord

Please join the UM Computer Science Discord to keep up with announcements and to ask questions. Instructions can be found on Canvas.

Teaching and learning assistants

We are lucky to have both a teaching Assistant (TA) and a learning assistant (LA) in this course. Our TA Onila is a graduate student in computer science and will be assisting with in-class activities, outside of course help, and grading. Our LA Jacob is a computer science undergraduate student who has recently taken CSCI 332. He will also assist with in-class activities, but with the attitude of being your peer, not your instructor.

Course help hours (aka office hours)

I will be available in the CS conference room (SS 402) from 1-2:30 on Mondays and Wednesdays to help with homework or answer any other questions you have. You’re also welcome to come even if you don’t have specific questions and just work on your homework in there.

Homework and homework quizzes

As detailed below, homework assignments are open everything (internet resources, generative AI, other people, etc.), but you must write your answers in your own words and you must cite every source you use for every problem. The point of the homework is to give you practice with solving algorithmic problems and communicating your solutions in writing. To this end, your homework writeups will be graded based on your communication skills, and your understanding of the material will be graded using short closed-notes quizzes based on the homework questions. These quizzes are not meant to be difficult or stressful, but to allow you to demonstrate that you understood the homework questions and their solutions.

Homework submission

Submit your homework on Gradescope. Go to gradescope.com and sign up using entry code XGV5DY.

You may submit homework individually or in groups of up to 3. To do so, have one group member submit and select the other groupmates.

Homework problems will be graded based on completion, according to the following criteria:

• Does the solution address the correct problem?
• Does the solution make a reasonable attempt at solving the problem, even if not fully correct
• Is the presentation neat?
• Is the explanation clear?
• Does the solution list collaborators or sources, or state that the student did not use any collaborators or outside resources?
• Is the solution written in the student’s own voice (not copied directly from an outside resource)?

You are encouraged to write your homework using LaTex, a typesetting program that is popular in computer science research. Overleaf is an online LaTeX compiler, and I’ve provided a homework template that you can use to write up your homework solutions.

Homework quizzes

To complement the submitted homework, we will also have short homework quizzes in class on the day after homework is due. These will consist of definitions questions and some questions that are similar to questions from the homework.

A sample homework quiz is available here. Your lowest homework quiz grade will be dropped.

Exams will cover material already seen on homework quizzes, so your homework quiz score will be the max of your homework quiz score and 75% of your score on the corresponding section of the exam. This policy does not apply if you did not take the homework quiz, however.

Grading

You will be graded on the following:

• 10% homework completion (lowest score dropped)
• 30% homework quizzes (lowest score dropped)
• 40% exams: midterm 1 (10%), midterm 2 (10%), cumulative final (20%)
• 20% participation

Your grade will be determined by your total score as follows: 93+: A; 90+: A-; 87+: B+; 83+: B; 80+: B-; 77+: C+; 73+: C; 70+: C-; 67+: D+; 63: D; 60: D-.

Participation

Your particiapation grade will be based on lecture attendance. You can make up lecture attendance by attending office hours or in other ways; please contact Lucy if you need to arrange another way to make up attendance.

Bonus

There are two ways to earn bonus points in this class.

Catch errors in course materials

If you find an error in any of the course materials (typo, incorrect statement, etc.), make a post in the #errors-in-course-material Discord channel. If it is really an error, you get a quarter of a point. Only the first person to post about an error gets the points. You can earn a max of 1 total point toward your 100 for the course (for four errors).

Course survey and evaluation

If 100% of the class completes the mid-semester course survey, the whole class gets 1 bonus point. Same goes for the course evaluation at the end of the semester.

Collaboration policy

You may use any resource available to you, as long as you write up your answers in your own words and properly cite your source. Some examples of resources you might use:

• other students in the class
• other students not in the class
• other instructors
• textbooks or online notes
• anything you find on the internet
• ChatGPT or other AI tools

The only resources you may use without citation are our course textbook, Algorithm Design by Kleinberg and Tardos, our posted lecture slides, our in-class or Discord discussions, and office hours discussions. For this reason, you will likely need citations on most of your homework assignments.

Please ask if you have questions about how to properly cite a source or a collaborator.

Accessibility

The University of Montana assures equal access to instruction through collaboration between students with disabilities, instructors, and the Office for Disability Equity (ODE). If you anticipate or experience barriers based on disability, please contact the ODE at: (406) 243-2243, ode@umontana.edu, or visit www.umt.edu/disability for more information. As your instructor, I will work with you and the ODE to implement an effective accommodation, and you are welcome to contact me privately if you wish.