Bryn Mawr College
CS 330: Algorithms: Design & Practice
Spring 2012
Course Materials
Prof. Douglas Blank
General Information
Instructor: Douglas Blank, 248 Park Science, 526-6501
Course: These course materials are based on those designed by Deepak Kumar, who is on leave this semester.
E-Mail: dblank@cs.brynmawr.edu
WWW: http://cs.brynmawr.edu/~dblank
Office Hours: Wednesdays at 1:30 - 2:30 and by appointment
Lecture Hours: Mondays & Wednesdays , 10:00am to 11:30am
Room: Park 349
Lab: Wednesdays 1:30 - 2:30 in Room 231 (additional lab hours will also available, see below)
Laboratories:
- Computer Science Lab Room 231 (Park Science Building)
- You will also be able to use your own computer to do the labs for this course.
Texts & Software
- (REQUIRED) Writing For Computer Science, Second Edition, by Justin Zobel, Springer, 2004.
- (REQUIRED) Programming Pearls, 2nd edition, by Jon Bentley, Addison-Wesley, 2000.
- (REQUIRED) More Programming Pearls, by Jon Bentley, Addison-Wesley.
- (REFERENCE) Algorithms, by Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, McGraw Hill, 2008.
- (REFERENCE) The Advent of the Algorithm, by David berlinski, Harcourt, 2000.
- Software: We will be using a variety of programming for laboratory exercises. Software for writing and running programs is available on all computers in the lab, and also available for download for your own computer.
Important Dates
January 18: First lecture
April 28: Last lecture
Assignments
Unless explicitly specified, all assignments are due at the beginning of the class (BY 10:15a sharp) on the date due. No credit will be awarded for any late work.
For all programming exercises, hand in a printout of your program file along with a printout of the screen output of your program showing an example run.
- Homework #1 : (Due on Janurary 30): Click here for details.
- Homework #2 : (Due on February 6): Click here for details.
- Homework #3 : (Due on February 13): Click here for details.
- Homework #4 : (Due on February 20): Click here for details.
- Homework #5 : (Due on February 27): Click here for details.
- Homework #6 :
- Homework #7 :
Many assignments in this course will use programs written by Jon Bentley. You can download them directly from his web site: http://netlib.bell-labs.com/cm/cs/pearls/code.html.
Lectures
- Week 1 (January 18)
January 18: Course introduction, logistics, overview. What is an algorithm? What does it mean to solve a problem? What is a problem? How do algorithms relate to models, solvability, computability, time complexity, and space complexity.
Read: Chapter 1 from Bentley.
- Week 2 (January 23, 25)
Jan 23: Sorting very large data files. Timing program runs. Generating non-repeating random numbers. Column 1 Notes
January 27: Utilities.
Read: Chapters 1, 6, and 14 from Zobel (these will be especially good for preparing your report for Assignment#1)
Homework#1 (Due in class on January 30): Click here for details.
- Week 3 (Jan 30, Feb 1 )
January 30: Presentations on Homework#1. Review and discussion on presentations.
February 1: Writing technical reports. Aha! Algorithms: Three problems: Finding missing numbers, rotating a 1-D vector by n places, finding anagrams. Also a quick review of some more UNIX/Linux commands
Read: Chapter 2 from bentley.
Homework#2 (Due in class on February 6): Click here for details.
- Week 4 (February 6, 8)
February 6: Presentations on Homework#2. Review & Discussion.
Homework#3 (Due in class on February 13): Click here for details.
February 8: Minimum edit distance: Levenshtein's distance algorithm and other Spelling Checker algorithms.
- Week 5 (February 13, 15)
February 13: Presentations on finding anagram classes in texts. An introduction to AWK.
February 15: Search as an algorithm. search.py.
Read: Bentley's Chapter 3.
Homework#4 (Due in class on February 20): Click here for details.
Extra credit assignment (Due by Monday, February 20): What do the names: Alice, Bob, Carol, Carlos, Charlie, Chuck, Dave, Eve, Isaac, Ivan, Justin, Mallory, Matilda, Oscar, Pat, Peggy, Victor, Vanna, Plod, Steve, Trent, Trudy, Walter, Zoe, Arthur, Merlin, Paul, and Carole have in common?
- Week 6 (February 20, 22)
February 20: Two implementations of Soundex. Table-driven algorithms. Designing correct programs using assertions. An example using Binary Search.
Read: Chapter 4 from Bentley.
Homework#5 (Due in class on February 27): Click here for details.
February 24: Implementing correct programs. Assertions.
- Week 7 (March 1, 3)
March 1: Presentations & Discussion on Soundex and Metaphone.
March 3: Testing programs. Structured basis testing. Creating scaffolding for testing. Language support for program testing. Examples.
Read: Chapter 5 from Bentley.
Homework#5 is assigned (Due on Wed, March 17). This is a wriiten assignment. Topics: Data Mining, Recommender Systems.
- Week 8 (March 8, 10)
No classes. Spring Break!
- Week 9 (March 15, 17)
March 15: Performance, design levels. Back of the Envelope estimations.
Read: Chapters 6 & 7 from Bentley.
March 17: Presentations on Recommender Systems.
- Week 10 (March 22, 24)
March 22: Presentations on Data Mining.
March 24: Peformance, more formally. Compexity analysis: Time & space. The RAM model. Big-Oh, Omega, and Theta characterizations, properties of assymptotic complexity. Start thinking about your final project ideas.
- Week 11 (March 29, 31)
March 29 : Sorting algorithms.
Read: Chapter 11 from Bentley.
Homework#6 is posted (Due on Monday, April 3): Click here for details.
March 31 : Sorting contd.
- Week 12 (April 5, 7 )
April 5: Presentations on performance of sorting algorithms.
April 7: Discussion on thinking and living computer science...
Homework#7 is posted (Due on Monday, April 10): Click here for details.
- Week 13 (April 12, 14 )
April 12: Presentations on Hybrid sorting algorithms.
April 14: Draft versions of papers due on final projects. Teach Yourself programming in Ten years, Peter Norvig. A discussion.
- Week 14 (April 19, 21)
April 19:
April 21:
Final versions of papers due on Final Project.
- Week 15 (April 26, 28)
April 26:
April 28:
Grading
All graded work will receive a grade, 4.0, 3.7, 3.3, 3.0, 2.7, 2.3, 2.0, 1.7,
1.3, 1.0, or 0.0. At the end of the semester, final grades will be calculated
as a weighted average of all grades according to the following weights:
Labs & Written Work: 50%
Presentations: 30%
Class Participation & Attendance: 20%
Total: 100%
Links
Created on
January 18, 2012.