Algorithm Analysis (CSC 301 2015F) : Home
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] [FAQ] [IRC] [Teaching & Learning]
Current: [Outline] [EBoard] [Reading] [Lab] [Assignment]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Algorist]
Related Courses: [Walker (2014F)]
Misc: [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] [Issue Tracker]
Welcome to the Fall 2015 section 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. A recent 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".
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 am also likely to conduct many class sessions using my standard "pseudo recitation" style - I will randomly select students and ask a series of questions. 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.
Warning! Although I love algorithms and have taught CSC 207 or its equivalent many times, this is my first semester teaching CSC 301. I expect to be developing materials as the semester progresses, so the schedule and other aspects of the course are likely to change.
Warning! This course is larger than normal for a 300-level course. That means that some of the normal approaches I'd hope to use (e.g., oral exams, some forms of recitation) are unlikely to be possible.
Warning! I am teaching three new courses this fall and a large section of CSC 151. I am also serving as department chair. I have instituted a wellness schedule for myself: Except on weeks in which I have an exam to grade, I am limiting myself to two hours of evening work and five hours of weekend work.
Meets: MWF, 3:00-3:50 p.m., Science 3819.
Instructor:
Samuel A. Rebelsky
[rebelsky],
Science 3824. 641-269-4410 (office). 641-990-2947 (cell).
Office hours: See outside door.
I also tend to follow an open door policy: Feel free to stop by when my
door is open or to make an appointment for another time.
I also try to keep a channel for the course open on Slack.
Rebelsky, Samuel A. (2015). The CSC 301 Course Web
The hypertext that you are currently reading. Many of these materials (particularly those under Readings and Labs are required. You should make it a point to load the page of the day at the beginning of each class to check announcements and such.
Skiena, Steven S. (2008). The Algorithm Design Manual, 2nd Edition.
Springer-Verlag.
Although this is not a new text, it is a new text for the Grinnell algorithms course. 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, so I will provide supplementary material to help you understand those structures.
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.
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. This text is optional. As a professional computer scientist, you'll want it on your bookshelf, but it will supplement the Skiena text.
Knuth, Donald E. (2011). The Art of Computer Programming, Volumes 1-4a. Addison-Wesley.
If I were braver, I'd make this the required text for the course. These texts are dense, thorough, and classic. As you progress in CS, you'll find yourself turning to these volumes to challenge yourself to think more carefully, more deeply, and more clearly.
By the time you finish this course, you should be able to