CS: 301.02 F17 Syllabus

Introduction

Welcome to the Fall 2017 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. 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).

Class Format

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.

Important Warnings

Warning! Although I love algorithms, this is my first semester teaching CSC 301. I will be using the same structure as SamR’s section, so hopefully we’ll stay on schedule.

Warning! I have chronic migraine disorder and will be starting a new treatment which requires driving to Des Moines every three months. Hopefully it will work and I’ll never have trouble getting things done on time, but in the mean time be aware that I may have to adjust my schedule suddenly on a bad day. This would include having to reschedule office hours or appointments. I hope that you’ll understand if that does happen, but hopefully it won’t.

Basics

Meets: MWF, 3:00-3:50 p.m., location TBD.

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.

Grading

  • Weekly homework assignments: 20%.
  • Take-home examinations (2): 30%.
  • Class participation: 10%.
  • Final Examination: 30%.
  • Best of (HW, Take-homes, Final): 10%.

Books and Other Readings

Required

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, so I will provide supplementary material to help you understand those structures.

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.

Recommended Texts

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.

Learning Outcomes

By the time you finish this course, you should be able to

  • Employ a variety of techniques for designing algorithms, including
    • Greed
    • Divide and conquer
    • Dynamic programming / memoization
  • 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.