CS 330: Algorithms: Design & Practice Spring 2004

Bryn Mawr College
CS 330: Algorithms: Design & Practice
Spring 2004
Course Materials

Information

Texts

Important Dates

Assignments

Lectures

Grading

Links

General Information

Instructor: Deepak Kumar, 248 Park Hall, 526-7485
E-Mail: dkumar@cs.brynmawr.edu
WWW: http://cs.brynmawr.edu/~dkumar

Lab Hours: Thursdays 2-4p and Fridays 10-12noon
Lecture Hours: Mondays & Wednesdays, 2:30 p.m. to 4:00 p.m.
Room: Park 232

Laboratories:

PC Lab Room 232 (Science Building)

Texts & Software

Programming Pearls, 2nd edition, by Jon Bentley, Addison-Wesley, 2000.
Software: We will be using C++ and Java programming languages for all laboratory exercises. Software for writing and running C++ and Java programs is available on Windows PCs in Room 232 as CodeWarrior 8 and also on other computers on the campus. You may also use the Java SDK installed on the Computer Science Linux cluster in Room 232. The Linux server can be accessed via a terminal session from any networked computer on campus via a SSH client. CodeWarrior can be used for writing C++ programs. Alternately, you can also use the g++ compilers on our Linux computers.

Important Dates

January 19: First lecture
April 29: Last lecture

Assignments

Unless explicitly specified, all assignments are due at the beginning of the class 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 Java program include the following comment header:

/* Name:     Your Name 
   Exercise: Exercise#
   Date:     Date assigned        
   
   Purpose:  A short description of the program/exercise.  

*/

Lab Groups

All homeworks will be done by assigned groups listed below:

Group 1: Catherine & Audrey

Group 2: Ioana & Sarah

Group 3: Karen & Christina

Group 4: Kathy & Kirstin

Homework 1 (Due on Monday January 26): See file ~dkumar/cs330/Homework1
Homework 2 (Due on Monday February 2): See file ~dkumar/cs330/Homework2
Homework 3 (Due on Monday February 9): See file ~dkumar/cs330/Homework3
Homework 4 (Due on Monday February 16): See file ~dkumar/cs330/Homework4
Homework 5 (Due on Monday February 23): See file ~dkumar/cs330/Homework5
Homework 6 (Due on Monday March 1): See file ~dkumar/cs330/Homework6
Homework 7 (Due on Monday March 29): See file ~dkumar/cs330/Homework7
Homework 8 (Due on Monday March 29): Self-study: Chapter 10 from Bentley
Homework 9 (Due on Monday April 5): See file ~dkumar/cs330/Homework9
Final Homework: See file ~dkumar/cs330/FinalProjects

Lectures

Week 1 (January 19, 21)
January 19: Introduction to the course. Algorithms: A Bird's Eye View (What is an algorithm, information processing, problem solving, models, solvability, computability, complexity and complexity classes, time complexity).

January 21: Cracking the Oyster: Sorting very large data files. Timing program runs. Generating non-repeating random numbers.

Read: Chapter 1 from Bentley.
Homework 1 (Due on Monday January 26): See file ~dkumar/cs330/Homework1
Week 2 (January 26, 28)
January 26: Presentation by Group 1: Catherine & Audrey. Discussion on parameters that affect performance: CPU, memory, disk, bus, etc.

January 28: Aha! Algorithms: Finding missing data, rotating, anagrams.

Read: Chapter 2 from bentley.
Homework 2 (Due on Monday February 2): See file ~dkumar/cs330/Homework2
Week 3 (February 2, 4)
February 2: Presentation by Group 2: Ioana & Sarah. Recap of the anagram program. Finding anagrams in texts. Generating permutations: all, lexicographic order, random order.

Homework 3 (Due on Monday February 9): See file ~dkumar/cs330/Homework3

February 4: Group lab meeting since Deepak is away on NSF work.

Read: Chapter 3 from Bentley.
Week 4 (February 9, 11)
February 9: Presentation by Group 3: Karen & Christina. Discussion on Chapter 3: Structuring data, reworking repeated code into arrays, encapsulation, meta-languages and specialized languages.

February 11: Verifying program correctness. Designing binary search. Proving correctness. Desiging unsing pre- and post conditions.

Homework 4 (Due on Monday February 16): See file ~dkumar/cs330/Homework4

Read: Chapter 4 from bentley.
Week 5 (February 16, 18)
February 16: Presentation by Group 4: Kathy & Kirstin. Reviewing presentations. Tips for good presentations.
February 18: A small matter of programming. Testing: Scaffolding, automated testing. Using assertions. Timing functions. The <ctime> and <cassert> libraries.

Read: Chapter 5 from Bentley.

Homework 5 (Due on Monday February 23): See file ~dkumar/cs330/Homework5
Week 6 (February 23, 25)
February 23: Correctness, Efficiency, and Performance criteria. Improving program performance. The value of estimation. Estimation Quiz.

Read: Chapter 6 & 7 from Bentley.

February 25: Complexity Analysis. The RAM model of computation. Best, worst, and average case complexities. Big-Oh notation. Examples of complexity analysis.

Homework 6 (Due on Monday March 1): See file ~dkumar/cs330/Homework6
Week 7 (March 1, 3)
March 1: Presentation by Group 2: Ioana and Sara. More on timing, complexity and estimation. Algorithm Design Strategies: an introduction.

March 3: Algorithm Design Techniques. A simple pattern recognition proglem.

Read: Chapter 8 from Bentley.

Homework 7 (Due on Monday March 29): See file ~dkumar/cs330/Homework7
Week 8 (March 8, 10)
No class, Spring Break!!
Week 9 (March 15, 17)
March 15: Algorithm Design Techniques: 1-D Pattern Recognition.

Read: Chapter 8 from Bentley.

March 17: Code Tuning: Profiling to detect "hotspots". Low-level code tuning tricks. Look unwinding/unrolling.

Read: Chapter 9 from Bentley.

Homework 7 (Due on Monday March 29): See file ~dkumar/cs330/Homework7
Week 10 (March 22, 24)
March 22: No class today, Deepak is out of town (AAAI Spring Symposium).
March 24: No class today, Deepak is out of town (AAAI Spring Symposium).

Homework 8 (Due on Monday March 29): Self-study: Chapter 10 from Bentley.
Week 11 (March 29, 31)
March 29: Presentation on Homework 7 by Karen & Christina and Homework 8 by Kathy & Kirstin.
March 31: Sorting.

Read: Chapter 11 from Bentley.

Homework 9 (Due on Monday April 5): See file ~dkumar/cs330/Homework9
Week 12 (Apri1 5, 7)
April 5: Presentation on Homework 9 by Catherine & Audrey. A Sample Problem: Sorted sampling.

Read: Chapter 12 from Bentley.

April 7: Sorting: Guest Lecture by Michael Eckmann (Lehigh University).

Final Homework: See file ~dkumar/cs330/FinalProjects
Week 13 (Apri1 12, 14)
April 12: Case Study: Questions from a technical interview (Ioana Butoi). An introduction to Heaps.

April 14: Heaps, priority queues, and sorting using heaps and priroty queues.

Read: Chapter 14 from Bentley.
Week 14 (Apri1 19, 21)
April 19: Strings: Extracting all the words from a text file, counting word occurrences in a text file, extracting longest repeated substrings from a text file (using suffix arrays). Draws for final presentations.

Read: Chapter 15 from Bentley.

April 21: Algorithms: A Bird's Eye View (What is an algorithm, information processing, problem solving, models, solvability, computability, complexity and complexity classes, time complexity). Emergence and information processing. Course Evaluations.
Week 15 (April 26, 28)
April 26: Final project presentations: Text File Compression (Ioana & Sara), Map Coloring (Kathy & Kirstin)
April 28 : Final Project Presentations: Dynamic Programming (Audrey & Catherine), Topological Sort (Christina & Karen). Course Wrap up!

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: 55%
Class Presentations: 35%
Class Participation & Attendance: 10%
Total: 100%

Links

Created by dkumar@cs.brynmawr.edu on January 20, 2004.