pchapin's CIS-5050 Advanced Algorithms and Data Structures, Spring 2020


Peter C. Chapin. Office: BLP-415 on the Williston campus. Office hours are by appointment. Phone: 802-879-2367 (voice mail active). Email: pchapin@vtc.edu. I will usually respond to email within 24 hours, not including weekends or holidays. Email is the best way to contact me. I am also sometimes on the FreeNode IRC network under the nickname pcc.

Course Description

The official course outline lists high level course objectives and content.

This course extends the content of the our undergraduate Algorithms and Data Structures course, CIS-3050. In this course we will be looking at more exotic algorithms and data structures, and we'll be studying additional theoretical and implementation issues that are not covered in the lower level course (for example: the mathematical basis of asympotic notation and recurrences, computational complexity issues, etc.). We will also look at some relevant papers that explore current research in the area of algorithms and data structures.

In keeping with curricular our focus on software engineering, there will be a lot of programming in this course. In addition to implementing certain algorithms and data structures you will be expected to appropriately test your code and, in some cases, do a performance analysis of your code. The required programming language will be Ada, a software engineering language that is worth knowing, even if you never use it again!


This course assumes you are familiar with the material in our CIS-3050 course. Specifically, with data structures such as linked lists, trees, and hash tables, and with the basic algorithms for sorting and searching. I will also assume that you have seen asymptotic notation before, although we will be studying the notation is greater depth here.


The text is Introduction to Algorithms third edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ISBN=978-0-262-03384-8

I have created an email distribution list for the class. I will use this list to distribute announcements and other supplementary materials. Be sure to check your mail regularly (daily) or you might miss something important. If you send a question in email directly to me, I may reply to my distribution list if I think that others would benefit from my answer. If you would rather I did not reply to the list you should say so in your message.

My home page contains various documents of general interest.

Grading Policy

I grade on a point system. Each assignment is worth a certain number of points. At the end of the semester I total all the points you earned and compare that to the total number of possible points. In this course there are two components to your grade.

  1. Homework. 20 pts/each. There will be approximately eight assignments during the semester for a total of 160 points. You will have one to two weeks to do each assignment, depending on the complexity of the assignment and other scheduling issues.

  2. Exam. 50 pts. There will be one exam. It will be a take home exam given during the final exam period.

When doing the exam you can use any resources available to you except that you can not consult with other students about exam questions nor post questions related directly to the exam on Internet forums or mailing lists (it is okay to read existing posts, however). If you have questions about the exam, please contact me.

For homework you can discuss the questions with other students and post questions related to the assignments in on-line forums. However, you should still do your own work. See the section on "Copying Policy" below for more information.

I will not formally take attendance, but I will notice people who seem "disengaged" in the class. Although attendance is not specifically part of my grading policy it will, like other intangible items such as "professionalism," play a role in how likely I am to round up borderline grades.

Late Policy

Roughly, late submissions are not accepted. If something comes up that prevents you from handing in an assignment on time, contact me, before the deadline if at all possible, to discuss your issue. As a practical matter I can accept a late submission if I have neither distributed a solution nor graded the assignment. Since either of those things can happen at any time after the due date, you should plan on submitting all materials on time. Some of the assignments in this course are complicated and it may be appropriate for me to change due dates in some cases. Don't hesitate to talk with me if you think that would be helpful.

Copying Policy

I encourage you to share ideas with your fellow students so I won't be shocked to learn that you've been talking with someone about an assignment. In fact, if you worked closely with someone else you should make a note on your submission that mentions the names of your associates.

However, I do ask you to do your own work in your final submissions. If two submissions exhibit what I feel to be "excessive similarity" I will grade the submissions based on merit and then divide the grade by two, assigning half the grade to each submission. If I receive more than two excessively similar submissions I will divide the grade by the number of such submissions and distribute the result accordingly.

Since "excessive similarity" is a bit subjective, I may only give you a warning if the similarity is not too excessive—especially for a first offense. However, I do keep records when I find excessive similarity and I will be much less inclined to be forgiving if I discover it again. If you are concerned about the possibility of submitting something that might be too similar to another student's work, don't hesitate to speak with me first. Remember that I won't be surprised to learn that you are working closely with someone (it's a good thing!), so don't feel reluctant to say so.

If you find material on the Internet or in a book that seems to answer questions I ask in an assignment, you may include such material in your submission provided you properly reference it. If I discover that you have included unreferenced material from such sources, I may not give you any credit for the question(s) answered by such material. You do not need to provide a reference to our text book or to materials I specifically provide in class.

Other Matters

Students with disabilities may request accommodation as provided within federal law. All such requests should be made by first contacting Robin Goodall, Learning Specialist, in the Center for Academic Success on the Randolph campus. She can be reached by phone at (802) 728-1278 or by email at rgoodall@vtc.edu.

Last Revised: 2020-01-04
© Copyright 2020 by Peter C. Chapin <pchapin@vtc.edu>