Data Structures and Algorithms
COMS S3137-001Q, Summer 2006

General Information | Schedule| Class BBoard | | Misc. Resources

What's New
General Information
This webpage - http://www.cs.columbia.edu/~sh553/teaching/su06-3137/

Instructor

TA

Class Meeting Times and Locations

Prerequisites

Objectives:

Fun with data structures! Want to know the difference between a hash and a graph ? Ever climbed a binary tree ? This will extend your basic programming skills by learning how and when to apply specific techniques to specific sets of problems. You can solve any problem, but can only do it efficiently if you study the structure and algorithms behind the problems. Basic CPP knowledge required for the ride.

Course Materials

Course Grade

Course Description

Homework Policy

Each homework assignment will have two sections; Programming and non-programming problems. A hard copy of the Non-programming problems should be handed in at class time on the day due, your name and login should appear on the top of your hard copy. Programming solutions should be electronically submitted before start of class.
In addition, a physical copy of the program listing and its execution on test data must be produced and turned in, together with a physical copy of answers to the questions, so that both these sections of each homework can receive TA grades, feedback, and comments.
All work is due in class on the date specified.

If you disagree with any grade, submit your grievance in writing to the grader responsible, documenting the merits of your case. The grader will respond likewise in writing. If you are still dissatisfied you may appeal in like manner to the instructor, who will only examine the written record of the dispute, and will respond in writing. "Writing" does not include email.

Programming Policy

For convenience, all programming can be developed on any machine using any C++ compiler. However, only those programs submitted electronically by the SUBMIT program on the Columbia machines and which compile using local g++ compiler on those machines will be graded.

It is importand to throughly document all your submitted programming homeworks. Readme's should be TEXT ONLY in a file called readme.txt . please see submittion instructions for more information. Good programming style will account for a substantial portion of the grade assigned to the programming part of the assignments.

All programs must compile; programs that do not compile will recieve a drastically reduced graded. Usually the homework assignments will only state the major objectives of the program to be written; it will be often up to you to make design decisions about things like I/O, efficiency, error handling, and so on. Make sure you provide adequate test cases to indicate the correctness and robustness of your approaches. In general, the failure of a grader to understand your work or to appreciate the thoroughness of its testing will be considered to be your error. Unfortunately, there is neither time nor facilities to allow live demos of homeworks.

Collaboration Policy

You are required to do the homework by yourself; collaborating with other students or copying their work will not be tolerated. Anyone found copying or using another persons work will be dealt with under the College procedures for cheating. See the policy and procedures on cheating for details.

Open Door Policy

We would like the course to run smoothly and enjoyably. Feel free to let either the TA or I, know what you find just, good, and interesting about the course. Let us know sooner about the reverse. See us, leave us a note, or send us email. Some students have problems in the beginning of the course, which is exactly the time to get help, before things get out of hand.

Class BBoard

You should be reading the BBoard on a daily basis between classes. There will be important information posted there that you are responsible for. Often test cases, problem corrections or clarifications, and announcements are made on the BBoard. You can access the BBoard through your web browser at TBD

Lecture schedule

Following is a rough estimate of the lecture schedule for the semester. Expect this schedule to be adjusted as we proceed.

Date Topics Assignment Reading
Wed, July 5 Introduction and overview, C++ Review   Reading: 1.1 - 1.7
Big-Oh notation, Running Times Class Notes

Homework 1 out 		Reading: 2.1 - 2.3
Mon, July 10 Running time, ADT, Linked lists   2.4,3.1 - 3.3
Lists and stacks; applications Class Notes 3.3-3.6
Wed, July 12 Stacks; recursion Class Notes

Homework 2 out

Words.zip for programming 		 
Queues; trees   3.6, 4.1 - 4.2
Mon, July 17 Applications; tree traversals  
Binary search trees Class Notes 4.3-4.5
Wed, July 19 Priority Queues 6-6.5
HashTables Class Notes

Homework 3 out 		5.1-5.5
Mon, July 24 Advanced Hash functions Class Notes 5.6
Search Engine Technology, Lempel-Ziv compression  
Sorting Basics   7 - 7.3
Wed, July 26 Disjointed Data Structures Class Notes 8 - 8.3
Review for midterm  
Mon, July 31 Disjoint Sets II   chapter 8
Intro Graph Theory Class Notes 9.1-9.2
Wed, Aug 2 (canceled) Graph Theory Homework 4 out

Homework 5 out
worldcities.txt file
fake 100 file
HW5 q1 pic link 		9.1-9.5
Shortest Path    
Mon, Aug 7 Network Flows, MST Class Notes 9.4-9.6
DFS and BFS   9.6
Algorithm Designs    
Smart Algorithms  
Wed, Aug 9 NP Complete Class Notes 9.7, 10.1-10.2
Algorithms  
Review  
Final!!