Advanced Topics in Algorithms
Spring 2012
Professor: Ran ("RON") Libeskind-Hadas
Office: Olin 1258
Phone: x18976
Ran's E-mail: ran@cs.hmc.edu
Office Hours: Scheduled office hours can be found here (... but you are always welcome to get in touch
to set up a time to meet outside of regular office hours)
Time and Location: Mondays and Wednesdays 2:45-4 PM,
Parsons B144
Course Ends: This is a 1.5 unit half course. The last lecture
is on
Wednesday, February 29 and the final exam is due on Friday, March 2.
Getting Help:
You are strongly encouraged to come and visit Ran during office hours,
just drop in, or send an e-mail to set up a meeting time.
Course Homepage:
www.cs.hmc.edu/courses/2012/spring/cs181b
What Is This Course About?
This course covers several topics that are not typically
covered in an undergraduate course in algorithms. Of course, there
are far too many algorithms topics to be covered in half a semester, so I have
selected several that have some high combination of being elegant
(admittedly somewhat subjective), interesting (definitely subjective),
useful (in many cases this is indisputable!), prototypical (exhibiting
ideas that are found in many other contexts), and famous (good for
impressing your friends at cocktail parties)! The course
topics for this offering include:
- Graph matching algorithms in bipartite and general graphs
(Hungarian Algorithm and Edmond's Blossom Algorithm)
- Matroids and Greed
- Online algorithms (deterministic and randomized)
- Amortization analyses of splay trees, union-find, and other
"advanced" data structures
- Approximation algorithms and schemes
Lecture Notes and Text
The lecture notes provided in class will be self-contained outlines,
but will require that you fill in many of the details that we do
interactively at the blackboard. Taking good notes will be important.
Attendance
If you are sick or have a
special reason for missing class, please send Ran e-mail before the class
that you will miss. Otherwise, you are expected to be in class.
Please make sure to arrive on-time as a courtesy to the instructor and your
classmates.
Assignments
There will be one assignment each week, given out on Wednesday and due
back the following Wednesday. There will be 5 assignments in total.
Advanced Algorithms Dollars
There will be times during the semester when you will need a little
extra time on an assignment. To that end, an account has been
established for you with two "Algorithms Dollars". A dollar
may be redeemed for an extension until 5 PM on the day after the
assignment is normally due. You do not need to request permission for
a dollar, simply slide your homework under Ran's office door by the
extension time and a dollar will automatically be charged from your
account.
Exam
There will be a takehome exam given in the week of February 27 and
will be due on Friday, March 2 at 5 PM.
Grades
The 5 homework assignments are worth a total of 60% of the grade and
the final exam is worth 30% of the grade. Attendance and
participation are worth 10% of the grade.
Honor Code and Collaboration Policy
All students in this class are expected to abide by the Harvey Mudd
Honor Code for work in this course.
Collaboration on homeworks is permitted and encouraged.
Here are the stipulations:
- You may only discuss problems with students currently in the
class, the grutors, and with Ran. Do not discuss the problems with
other students not currently in the class.
- Collaboration is limited to discussion. You may use
a whiteboard, blackboard, or paper as part of your discussion, but
you should erase or throw away those written materials before starting your
own write-up.
- Each individual must write up their own solutions.
- Looking for solutions or hints on the web, books, course notes
from previous semesters, or any other source is not permitted.
- You should indicate at the top of your homework submission who
you collaborated or consulted with on that assignment.
Use of laptops and portable devices in class...
As a courtesy to your fellow students and your instructor, please do
not use laptops, iPads, mobile phones, etc. in class. If you genuinely need to use such
a device in class, please talk to me and we'll find a way for you to
do so.