Bryn Mawr College
CS 330: Algorithms: Design & Practice
Spring 2008
Course Materials
Prof. Deepak Kumar
General Information
Instructor: Deepak Kumar, 246 Park Hall, 526-7485
E-Mail: dkumar at cs brynmawr dot edu
WWW: http://cs.brynmawr.edu/~dkumar
Lecture Hours: Tuesdays & Thursdays , 10:00a to 11:30a
Room: Park 336
Lab: TBA in Room 231 (additional lab hours
will also available, see below)
Laboratories:
- Computer Science Lab Room 231 (Science Building)
- You will also be able to use your own computer to do the labs for this course.
Texts & Software
- Programming Pearls, 2nd edition, by Jon Bentley, Addison-Wesley, 2000.
- Software: We will be using C, C++, Python, and Java programming languages for all laboratory exercises. Software for writing and running programs is available on all computers in the lab.
Important Dates
January 22: First lecture
May 1: Last lecture
Assignments
Unless explicitly specified, all assignments are due at the beginning of the class (at 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. On the top of every program include the following comment header:
/* Name: Your Name
Exercise: Exercise#
Date: Date assigned
Purpose: A short description of the program/exercise.
*/
|
- Homework#1 is posted (Due on Tuesday, January 28). Click here for details.
- Homework#2 is posted (Due on Thursday, February 7). Click here for details. <---NOTE NEW DUE DATE!
- Homework#3 is posted (Due on Thursday, February 14). Click here for details.
- Homework#4 is posted (Due on Thursday, February 21). Click here for details.
- Homework#5 is posted (Due on Thursday, February 21). Click here for details.
- Homework#6 is posted (Due on Thursday, March 6). Click here for details.
- Homework#7is posted (Due on Tuesday, March 25). Click here for details.
- Homework#8 is posted (Due on Tuesday, April 8). Click here for details. (Map file has been updated as of 4/2/2008 10:46a)
- Homework#9 is posted (Due on Monday, April 21 (12noon)). Click here for details.
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.
However, be aware that many of them have been revised by Deepak. The latest revised versions are available in: ~dkumar/cs330/...
Presentation Order
- Jessica Billings
- Priscy Pais
- Natasha Eilbert
- Mansi Gupta
- Stephanie Hilton
- Ashley Gavin
- Caitlin Evans
- lauren Maksym
- Jesse Rohwer
- Shikha Prashad
- Marwa Nur Muhammad
- Joe Huttner
- Emily Somach
- Simona Radu
Mini-Conference on Computing Algorithms
April 22, April 24, April 29, May 1, 2008
Room 236 PSB
10:00a to 11:30a
Speaker Schedule
Tuesday, April 22
Session Chair: Caitlin Evans
10:10a - 10:30a Heapsort by Lauren Maksym
10:30a - 10:50a Fisher-Yates Shuffle by Simona Radu
10:50a - 11:10a Hashing by Jesse Rowher
11:10a - 11:30a Memoization by Natasha Eilbert
Thursday, April 24
Session Chair: Natasha Eilbert
10:10a - 10:30a Monte Carlo Methods by Mansi Gupta
10:30a - 10:50a The RSA Algorithm by Marwa Muhammad
10:50a - 11:10a Simplex Algorithm by Shikha Prashad
11:10a - 11:30a Data Compression by Priscy Pais
Tuesday, April 29
Session Chair: Joe Huttner
10:10a - 10:30a Porter Stemmer by Caitlin Evans
10:30a - 10:50a String Matching by Emily Somach
10:50a - 11:10a Page Rank Algorithm by Stephanie Hilton
Thursday, May 1
Session Chair: Lauren Maksym
10:10a - 10:30a Map Coloring by Ashley Gavin
10:30a - 10:50a Dijkstra's Shortest Path Algorithm by Joseph Huttner
10:50a - 11:10a The MiniMax Algorithm by Jessica Billings
Lectures
- Week 1 (January 22, 24)
January 22: Course introduction, logistics, overview. Agorithms: Truth, Beauty, and Engineering. Algorithms: A Bird's Eye View (What is an algorithm, information processing, problem solving, models, solvability, computability, complexity and complexity classes, time complexity).
January 24: Cracking the Oyster: Sorting very large data files. Timing program runs. Generating non-repeating random numbers. Using I/O redirection in Linux.
Read: Chapter 1 from Bentley.
Homework#1 is posted (Due on Tuesday, January 28). Click here for details.
- Week 2 (January 29, 31
January 29: Presentations by Jessica Billings & Priscy Pais. Discussion of all the programs and timings and Python versions. Try out all the Python versions posted in ~dkumar/Homework1/Python.
January 31: 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, gnuplot etc.
Read: Chapter 2 from Bentley.
Homework#2 is posted (Due on Thursday, February 7). Click here for details. <---NOTE NEW DUE DATE!
- Week 3 (February 5, 7)
February 5: The world of UNIX/LINUX; stdio, I/O redirection, pipes, programs as filters, popular filter programs, man, the AWK programming language, gnuplot.
February 7: Finding anagrams from a dictionary. Presentations by Natasha & Mansi. Discussions. Lessons learned. A short introduction to gnuplot.
Read: Chapter 3 from Bentley.
Homework#3 is posted (Due on Thursday, February 14). Click here for details.
- Week 4 (February 12, 14)
February 12: Data Structures Programs. Examples: Soundex algorithm, days in a month, etc.
Read: Chapter 3 from Bentley.
February 14: Presentations by Ashley & Stephanie. Regular Expressions. The Metaphone algorithm.
Homework#4 is posted (Due on Thursday, February 21). Click here for details.
- Week 5 (February 19, 21)
February 19 : Writing correct programs: searching for data. Program verification techniques, pre/post conditions.
Read: Chapter 4 from bentley.
February 20: Distinguished Speaker Series: Prof. Maria Klawe, President of Harvey Mudd College will give a talk at Haverford College on Women in Computing. All should try to attend. We will provide rides if needed.
February 21: Presentations by Caitlin & Lauren. Writing correct programs and program verification.
Homework#5 is posted (Due on Thursday, February 21). Click here for details.
- Week 6 (February 26, 28)
February 26: Program verification & testing. Creating test harnesses and scaffolding. Using program assertions (in C, C++, Python).
Read: Chapter 5 from Bentley.
February 28: Presentations by Jesse & Shikha.
Homework#6 is posted (Due on Thursday, March 6). Click here for details.
- Week 7 (March 4, 6)
March 4: Testing using code coverage techniques. Variable naming conventions (Hungarian), estimation quiz.
Read: Chapters 6 and 7 from bentley.
March 6:
- Week 8 (March 11, 13)
No classes. Spring Break!
- Week 9 (March 18, 20)
March 18: Sorting: Insertion sort, Selection Sort, Quick Sort.
Read: Chapter 11 from Bentley.
Homework#7is posted (Due on Thursday, March 6). Click here for details.
March 20: Deepak is out of town.
- Week 10 (March 25, 27)
March 25: Sorting: results from Assignment#7. presentation by Simona & Emily. Analyzing sorts.
Homework#8 is posted (Due on Tuesday, April 8). Click here for details.
March 27: Deepak is out of town.
- Week 11 (April 1, 3)
April 1: Abstraction in computing. Encapsulation, object-oriented design. Examples from C++, Java, Python.
(Map file has been updated as of 4/2/2008 10:46a)
April 3: Computational Thinking. A discussion of jeannette Wing's CACM article. (See dept web page for Prof. Wing's talk)
- Week 12 (April 8, 10)
April 8: Designing abstractions for maps. Discussion on presentations and your last assignment (See below).
Homework#9 is posted (Due on Monday, April 21 (12 noon)). Click here for details.
April 10: Maps, contd. Refining abstractions
- Week 13 (April 15, 17)
April 15: Maps, contd: Redesigning data formats. Markup languages for data specification.
April 17: Applications of Maps: Red-Blue states. Searching: Breadth-First and Depth-First Searches...implementations.
- Week 14 (April 22, 24)
April 22: Mini Conference on Computing Algorithms
Session Chair: Caitlin Evans
10:10a - 10:30a Heapsort by Lauren Maksym
10:30a - 10:50a Fisher-Yates Shuffle by Simona Radu
10:50a - 11:10a Hashing by Jesse Rowher
11:10a - 11:30a Memoization by Natasha Eilbert
April 24:
Mini Conference on Computing Algorithms
Session Chair: Natasha Eilbert
10:10a - 10:30a Monte Carlo Methods by Mansi Gupta
10:30a - 10:50a The RSA Algorithm by Marwa Muhammad
10:50a - 11:10a Simplex Algorithm by Shikha Prashad
11:10a - 11:30a Data Compression by Priscy Pais
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, 2008.