Welcome to Grinnell’s Spring 2019 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”.
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.
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 a participation grade. As long as you show up and participate most of the time, you will get all those points. Note that participation is a small percentage of your final grade, so if you really don’t find class time helpful, you can get an A without attending, though you will have to get a perfect score on everything else.
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 the 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.
This semester we will have four oral exams. These exams are specifically for me to determine your understanding of the algorithms and corresponding proofs from class. Students previously have said they liked and even preferred the oral exam format because it lets me get a better idea of your understanding. Each exam will be individually 30 mins in my office. I will give you one of several possible questions that are similar to your homework problems. You will need to explain the algorithm, proof of correctness, and proof of time complexity for the problem. Each part is worth 20 points for a total of 60 points. You will have the option to ask for verification, which is the answer to a yes or no question, for 2.5 points off your final score. You will also have the option of asking for a hint, which is an open-ended answer, for 5 points off. It will always be better for recognize you don’t know something and ask for a hint than barrel on with an incorrect answer. Knowing the limits of your knowledge is halfway to knowing the answer and much better than having an incorrect answer.
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. Note that the reflection journals are a small percentage of your overall grade, so if you do not find them useful, you can get an A without submitting any, though you will need a near perfect score on everything else.
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.
I 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 3819
Instructor: Anya E. Vostinar [vostinar], Science 3809.
How to schedule a meeting 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 PWeb questions: I do my best to answer class questions on PWeb 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.
- Weekly homework assignments: 30%.
- Oral examinations (3): 30%.
- Class participation: 5%.
- Reflection journal: 5%.
- Final Oral Examination: 30%.
Books and Other Readings
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.
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. (2008). The Algorithm Design Manual, 2nd Edition.
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.
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.
The overarching goal of this course is for you to be able to provide a solution to 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:
- Implement several advanced data structures
- Employ a variety of techniques for designing algorithms, including
- 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.
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 will have an impact. You may have 10 absences. If you miss more than 10 classes, you will lose your participation points.
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.
There is not a late policy for homework, i.e. I will not accept late homework and you will receive a 0 unless you have a documented excuse.