CSC 301 F18: Analysis of Algorithms

Introduction

Welcome to Grinnell’s Fall 2018 CSC 301 – Analysis of Algorithms. CSC 301 is the department’s advanced course in algorithms and is a successor to CSC 207 – Algorithms and Object-Oriented Design. In this course, we will develop your skills in the design, implementation, analysis, and verification of algorithms. We will also explore advanced abstract data types and data structures.

Along the way, we will consider a variety of classic algorithms, ADTs, and data structures – the “literature” of CS, as it were. Why do we read the literature? Because knowing how problems have been solved in the past helps us solve future problems. An article on mathematics suggests the value of knowing the literature.

Yet, as they told me, the proof [of the Green-Tao Theorem] depended on the insights of many other mathematicians. In the game of devil’s chess [mathematics], players have no real hope if they haven’t studied the winning games of the masters. A proof establishes facts that can be used in subsequent proofs, but it also offers a set of moves and strategies that forced the devil to submit — a devious way to pin one of his pieces or shut down a counterattack, or an endgame move that sacrifices a bishop to gain a winning position. Just as a chess player might examine variations of the Ruy Lopez and King’s Indian Defense, a mathematician might study particularly clever applications of the Chinese remainder theorem or the sieve of Eratosthenes. The wise player has a vast repertoire to draw on, and the crafty player intuits the move that suits the moment.

Cook, Gareth (2015). The Singular Mind of Terry Tao. The New York Times Magazine. 26 July 2015. Available online at http://www.nytimes.com/2015/07/26/magazine/the-singular-mind-of-terry-tao.html.

This course will certainly expand your “repertoire to draw on”.

Accommodations

If you have any disability that requires accommodations, please speak with me as soon as possible so we can figure out how I can best facilitate your learning in this course. Note that you will also need to provide documentation of your disability to the Dean for Student Academic Support and Advising, John Hirschman, located on the 3rd floor of the Rosenfield Center (x3089). If you do not have documentation for any reason, please still contact me to discuss options.

Class Format

I firmly believe that you learn by doing. The structure of the class will be heavily discussion and group-work based. You will frequently be asked to solve a problem that you haven’t encountered before (but never on exams!). Once you have worked on a problem with a partner, we will then discuss it together as a class and you will need to submit a write up. I will randomly call on students throughout class. You should do your best to answer those questions, but you should feel free to say “I’m not sure” or to ask me your own questions. Because this class is based heavily on discussion, there is an attendance/participation grade. As long as you show up and participate most of the time, you will get all those points.

To encourage you to learn from everyone in the class, there will be cards with dogs at each computer station. When you come into class, please pick up a dog card near the door. The image will match one of other cards. Please sit at a station and work with the other student with the same dog card. Return the dog cards to the mentor at the end of class.

We will use Piazza to communicate about the class. You are expected to read everything posted to the class Piazza and are responsible for announcements made there. There are several email settings to ensure that you don’t miss anything. Additionally, you may earn extra credit for posting helpful videos or articles to Piazza about class content. There are so many resources out there for the material we will be covering, so if my explanation doesn’t make sense, go look for another one and then post it for others to use as well.

This semester we will have four in-class exams. These exams will have several problems on them. These problems will be extremely similar to homework or in-class problems. Therefore, the best way to study for the exams is to make sure you can recreate the solution for every in-class and homework problem. The large number of exams is so that you don’t have to worry about messing up on one exam because it will be evened out by all the others.

Studies show that reflecting on what you have recently read or learned greatly improves recall. Therefore, you will be required to submit reflection journals every day before the start of class. These are scored 0-2, 0 being you didn’t turn anything in, 1 being you turned something in but it was not sufficient, and 2 being you turned in a sufficient reflection. To earn a 2, you should have at least two paragraphs recapping the material for the day or otherwise responding to the prompt. These reflections help me to see where everyone is and also serve as excellent review material for you.

Due to the varied mathematical backgrounds of students coming into this class, you may find you are already familiar with some of the material or even specific problems that we discuss. This is not an excuse not to attend or participate. Instead, it is an opportunity for you to reinforce your own understanding by helping others understand the material. You don’t truly understand something until you can teach it to someone else.

Logistics

There are two sections of 301 and we will be trying to stay completely in sync for my sanity. I also prefer to bring Cache the wonder dog to class, so please let me know if that would impinge on your learning.

Monday, Wednesday, Friday
Section 1: 11am-11:50am, Science 3815
Section 2: 1pm-1:50pm, Science 3819

Instructor: Anya E. Vostinar [vostinar], Science 3809.
Student Office hours here
Be aware that I bring Cache the wonder dog to my office regularly and she will likely be at student office hours. If you would like a dog-free meeting, just let me know a day ahead of time and I’ll make arrangements.

On email and Piazza questions: I do my best to answer class questions on Piazza when I’m able. However, I have chronic migraine and therefore cannot give a guarantee on when I’ll respond, even during traditional business hours.

On regrades: I will only consider changing a grade on any graded work if it within one week of you receiving that grade. Any requests after that time will not be considered.

Grading

  • Weekly homework assignments: 30%.
  • In-class examinations (2): 30%.
  • Class participation: 5%.
  • Reflection journal: 5%.
  • Final In-Class Examination: 30%.

Books and Other Readings

Required

Kleinberg, Jon and Eva Tardos. (2005). Algorithm Design, 1st Edition. Pearson.

This book is a good balance between rigor and simplicity compared to the other options on the market. We will be following it’s layout closely because I like the order in which it introduces the various topics we will discuss.

Recommended Texts

Skiena, Steven S. (2008). The Algorithm Design Manual, 2nd Edition.
Springer-Verlag.

I like the Skiena book because it helps you think carefully through algorithm design and it’s not quite as overwhelming as the CLRS text. Unfortunately, Skiena does not cover all of the important data structures in depth.

Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., and Stein, Clifford (2009). Introduction to Algorithms, 3rd Edition. MIT Press.

A classic (and somewhat exhaustive) text on algorithms. This text is an excellent reference, but is also somewhat dense. As a professional computer scientist, you’ll want it on your bookshelf, but it will supplement the Skiena text.

Skiena, Steven S. (n.d.). Web Site for The Algorithm Design Manual, 2nd Edition. http://www.algorist.com/.

The Web site includes lecture slides and some audio/video material.

Knuth, Donald E. (2011). The Art of Computer Programming, Volumes 1-4a. Addison-Wesley.

These texts are dense, thorough, and classic.

Learning Outcomes

The overarching goal of this course is for you to be able to provide a solution t0 a real-world problem that you can prove is correct and time-efficient. To work towards that goal, we will be tackling these smaller goals:

  • Employ a variety of techniques for designing algorithms, including
    • Greedy
    • Divide and conquer
    • Dynamic programming / memoization
    • Network Flow
  • Analyze the asymptotic behavior of deterministic algorithms using Big-O notation.
  • Prove certain characteristics of algorithms (e.g., correctness, lower bounds, running time).
  • Describe and implement a variety of classic algorithms.

Absence Policy

Remember that participation is 5% of your grade, so missing a few days won’t add up to any impact on your grade, but missing half the class days and not participating much the other half will have an impact. You don’t need to tell me why you are missing class unless you are missing several classes, which could affect your grade.

If you think you are ill with a contagious illness, please do not come to class. Instead, let me know via email and I’ll provide you with the prompt for the day. It is your responsibility to make up for the lost discussion time by talking with others in the class or coming to office hours to discuss with me after you are no longer contagious.

If you need to be absent for any other reason, that will generally  be fine as long as it doesn’t become a habit. Again email me and I’ll provide the prompt and you will need to make sure that you understand the material.

There is not a late policy for homework, ie I will not accept late homework and you will receive a 0 unless you have a documented excuse.