Welcome to the Spring 2018 iteration of Grinnell College’s CSC 301 – Algorithm Analysis. CSC 301 is the department’s advanced course in algorithms and serves as a successor to CSC 207 – Algorithms and Object-Oriented Design. In this course, we will work to develop your skills in the design, implementation, analysis, and verification of algorithms, 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. While I do not expect to make this a full workshop-style course, akin to CSC 151 or CSC 161, I will do my best to regularly give you the opportunity to work individually and together on problems during class time. I will try to 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.
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. Click here to sign up for it.
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.
Section 1 Meets: MWF, 11:00-11:50 p.m., Noyce 3819.
Section 2 Meets: MWF, 1-1:50pm, Noyce 3819.
Instructor: Anya E. Vostinar [vostinar], Science 3809.
Office hours: Posted here
Be aware that I bring Cache the wonder dog to my office regularly and she will likely be at office hours. If you would like a dog-free meeting, just let me know a day ahead of time and I’ll make arrangements.
- Weekly homework assignments: 30%.
- Take-home examinations (2): 30%.
- Class participation: 5%.
- Reading journal: 5%.
- Final Examination: 30%.
Books and Other Readings
Kleinberg, Jon and Eva Tardos. (2005). Algorithm Design, 1st Edition. Pearson.
This is the first semester I am using this book. I think that it 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 also like the order in which it introduces the various topics we will discuss.
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.
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.
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
- 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.
- Describe a variety of classic ADTs.
- Describe and implement a variety of classic data structures.