CSCI-2300: Data Structures and Algorithms
Sections 7, 8, 9
Spring 2001

Course Information

Time: Monday and Thursday, 6:00pm - 7:20pm
Classroom: DCC 324
Credits: 4
Prerequisites: Computer Science II (CSCI-1200) and Calculus I (MATH-1010).

Web page: http://www.cs.rpi.edu/~sakella/dsa/

Grad TA for Sections 7 and 9:
Adnan Saifee
Email: saifea@rpi.edu
Office: Lally 1A, x8489
Office Hours: Wednesday 2:00-3:00pm, Thursday 5:00-6:00 pm

Grad TA for Section 8:
Karlton Sequeira
Email: sequek@cs.rpi.edu
Office: Lally 3A, x8556
Office Hours: Tuesday 4:00-5:00pm

Description

Syllabus. postscript file, pdf file.

Labs

Note: Students must go to their assigned lab section. You may find it helpful to take a C++ reference book to the lab.

Lab

• There are no labs this week (April 16-20).
  
• Lab9: Graph1.cpp , g1.txt , g2.txt
  
• There are no labs this week (April 2-6) since it is GM week.
  
• Lab8: test.cpp , quicksort.h , insertion_sort.h , rng.h , timer.h , counter.h .
• Lab7: student.cpp , student.h , main.cpp
  
• Lab6: BSTree.h , demo_main.cpp
  
• There are no labs for the week of February 19 (as indicated in the syllabus).
  
• Labs for the week of February 12 have been cancelled.
  
• Lab5: Animal.h , Cage.h , main.cpp , cagedata.txt
  
• Lab4: accum.cpp , dlist.h , main.cpp
  

Lab solutions

• Lab1: discussion , buffer.cpp , buffer.h , main.cpp
  
• Lab2: discussion , dlist.h , main.cpp
  
• Lab3: complex.h , complex.cpp , main.cpp , main_list.cpp
  
• Lab4: dlist.h , accum.cpp
  
• Lab5: Cage.cpp , main.cpp ,
• Lab6: BSTree.h
• Lab7: main.cpp , main_mm.cpp , student.cpp , student.h
• Lab8: step3.h , step5.h , step6.h , step7.h , step8.h , step9.h , step10.h , step11.h , step12.h .
• Lab9: Graph1_sol.cpp .

Lectures

• Lecture 1 (Jan 8) notes: postscript , pdf . Example code: primes.cpp
  
• Lecture 2 (Jan 11) notes: postscript , pdf . Example code: int_array.h , int_array.cpp , test_array.cpp , primes.cpp
  
• Lecture 3 (Jan 18) notes: postscript , pdf . Example code: t_array.h , test_array.cpp , primes.cpp , primes_vect.cpp
  
• Lecture 5 (Jan 25) Example code for polynomial ADT:
  Version 1
  Version 2 (sparse representation) , with missing polynomial multiplication operator here
  
• Lecture 6 (Jan 29) HW1 .
  
• Lecture 8: Exercise solutions postscript , pdf , Exam review solutions postscript , pdf
  
• Lectures 12 and 13: Header file for BSTree class and AVL trees BSTree.h , comparison code for balanced and unbalanced BSTs compare_main.cpp , demo code for AVL trees demo_main.cpp .
  
• Lecture 15 (March 5) Code for hash tables: hash.h , main.cpp
  
• Lecture 17 (March 22) Binary heap code (from Weiss): BinaryHeap.h , BinaryHeap.cpp , dsexceptions.h
  
• Lecture 17 Exercise solutions: postscript , pdf
  
• Lecture 18 (March 26) Sorting code: insert.h , heap.h , basic_quick.h , quick.h
  
• Lecture 20 (April 2) Sorting code: select.h
  
• Lecture 21 (April 5) notes: postscript , pdf . Unweighted shortest path code (from Weiss): Graph1.cpp
  
• Lecture 21: Exercise solution postscript , pdf

Projects

• Project 1: (due Friday, February 2)
  Description postscript , pdf ,
  Code sparse_matrix.h , driver.cpp . Be sure to test your program extensively.
  Example output when using driver program: tst.out

  Project 1 solution: sparse_matrix.h and test driver driver.cpp .

• Project 2: (due Tuesday, February 27)
  Description postscript , pdf .
  Here is an example input file of requests request.txt and the resulting example output of results results.txt . Please try to match your output as closely as possible to this example output. Look at notes.txt for additional notes on the output format.
  Note that you must perform more extensive testing of your program.

  Project 2 solution

• Project 3: (due Friday, March 23)
  Description postscript , pdf .
  Here is a small example data file of points: data.txt . When the kdtree is created to store one point at each leaf node using the command

   kdtree data.txt 1 < queries.txt > out1.txt
  

  the output resulting from the queries in the query file queries.txt gives the resulting output of results out1.txt .
  Similarly when the kdtree is created to store at most two points at each leaf node
  

     kdtree data.txt 2 < queries.txt > out2.txt
  

  here is the resulting output out2.txt .
  
  You MUST match your output format to this example output format.
  
  Project 3 solution

• Project 4: (due Wednesday, April 25)
  Description postscript , pdf .

  Here is the Unweighted shortest path code (from Weiss): Graph1.cpp and Binary heap code (from Weiss): BinaryHeap.h , BinaryHeap.cpp , dsexceptions.h you can use for your project.

  Important: Look at the notes and updates about Project 4. Please check this frequently!

  Check here for project announcements .

Homeworks

• Homework 1: (due Monday, February 5) postscript , pdf . Be sure to write your name, section number, and RPI email address on your homework submission.
  
• Homework 1 solutions: postscript , pdf
  
• Homework 2: (due Monday, March 5) postscript , pdf . Be sure to write your name, section number, and RPI email address on your homework submission.
  
• Homework 2 solutions: postscript , pdf
  
• Homework 3: (due Monday, March 26) postscript , pdf . Be sure to write your name, section number, and RPI email address on your homework submission.
  
• Homework 3 solutions: postscript , pdf
  
• Homework 4: (due Thursday, April 19) postscript , pdf . Be sure to write your name, section number, and RPI email address on your homework submission.
  
• Exercise solution for Lecture 21: postscript , pdf
• Homework 4 solutions: postscript , pdf
  

Exams

• Exam 1 solutions postscript , pdf . Please contact the grad TAs if you have questions about grading: Karlton Sequeira for questions 2 and 4, Adnan Saifee for all other questions.
  
• Exam 1 is on Monday, February 12 from 6:00pm to 7:30pm in DCC 324.
• Exam 1 review solutions postscript , pdf
  
• Exam 2 is on Thursday, March 29 from 6:00pm to 8:00pm in DCC 324.
• Exam 2 review questions: postscript , pdf
  
• Exam 2 review solutions: postscript , pdf
  
• Exam 2 solutions postscript , pdf .
  
• The final exam is 8:00-11:00am on Tuesday, May 1 in Sage 3510. If you need to schedule a make-up exam because of a schedule conflict, send me email with your exam schedule by Friday, April 12.
  
• The Makeup final exam is scheduled for 1:00-4:00 pm on Monday, April 30. Only those who received email from me today (Thursday, April 26) confirming they are signed up for the makeup exam will be able to take it.
  
• Chapter 9 review questions: postscript , pdf
  
• Chapter 9 review solutions: postscript , pdf
  

Announcements

• The final grades for the semester are here: Section7 , Section8 , Section9 . The final exam grades were curved. I double checked the final exams of all students who missed a grade cutoff by 3 points or less. Grade changes will be considered only if we made a mistake in grading your final or in recording your prior scores. If you would like to see your Final exam, please stop by my office. Have a good summer!
  
• You can see the Project 4 test cases at Project 4 notes and updates .
  
• Project 4 grading update: Some of you may have had 3 points deducted for using a vector (instead of a list) in the Vertex class to store the edge pointers to adjacent vertices. Since these points were incorrectly deducted, we are updating your grades so no points are deducted for this. Although you will not receive email about this grade change, our database of grades will be updated to reflect this change.
  
• For the final, you will be given important formulas, rotation functions and graph algorithms.
  
• Here are the Project 2 solution and Project 3 solution .
  
• As mentioned in class, the Final is cumulative. Hence you should be familiar with material from the entire semester including topics such as quicksort, quickselect, mergesort, etc.
• Graded HW4 (and old HWs and exams) are available outside my office.
  
• The Makeup final exam is scheduled for 1:00-4:00 pm on Monday, April 30. Only those who received email from me today (Thursday, April 26) confirming they are signed up for the makeup exam will be able to take it.
  
• Our final class on Monday, April 23 will be a review class to discuss any questions you may have.
  
• Homework 4:
  • Question 1 clarification: Think of the reliability r(u,v) of an edge (u,v) as its weight. Then the most reliable path from a vertex s to a vertex t is the path that maximizes the product of the edge weights along the path.
    
  • Question 2: The second sentence should read: "There may be a number of minimum paths from vertex v to w."
    
  • Question 4: See Figure 9.81 on page 381 of Weiss to see an example of a bipartite graph.
    
• Important: Please check the notes and updates about Project 4 frequently!
  
• The grades so far for the semester are here: Section7 , Section8 , Section9 . Please check these to make sure there are no errors.
  
• The final exam is 8:00-11:00am on Tuesday, May 1. If you need to schedule a make-up exam because of a schedule conflict, send me email with your exam schedule by Friday, April 12.
  
• Homework 4 is due on Thursday, April 19: postscript , pdf .
  
• The homework exercise in the class handout from Class 21 (April 5) is due on April 12. Here is the handout postscript , pdf .
• Project 4 (due Wednesday, April 25) is now available. Here is the description: postscript , pdf .
  
• Correction: There was an error in the leftist heap shown after the second deletemin operation in the Lecture 17 Exercise solutions. The corrected solution is here: postscript , pdf
  
• Someone just pointed out that the splay tree solution (question 1) in the test review solutions was incorrect. I have updated the file (March 29, 2:15am), but have not had a chance to check the answer again.
  
• For Exam 2, only insertion sort and heapsort are included in the material to be studied. You do not need to study merge sort and quick sort.
  
• Clarification: Your program output should match the format shown in the files out1.txt and out2.txt as described above. The files all_tree1.txt and all_tree2.txt are provided only to help you understand the kdtree structure.
• If you are following the Build_KdTree pseudocode closely, note that you need to pass the bounding box of the rectangle (the node rectangle) that the subtree being constructed will represent. This parameter is not listed in the argument list. Remember that the node rectangle at the root is infinite in all directions, and for this project, infinity is represented by 10^6.
• To better understand the structure of the kdtree generated in the above example, you may find it helpful to look at the file all_tree1.txt that contains all nodes of the kdtree from an in-order traversal when c=1 and the file all_tree2.txt when c=2.
• Your program must parse the command-line using argc and argv to both get the name of the points file and to get the value of c. The command-line must look like

    kdtree points.txt c
  

  where points.txt is the name of the file and c is the integer. You may not hard-code either of these names and you will be penalized if you do so.
• The queries will come from cin and the output will go to cout.
• Please check the Project 3 description above for an example data set and resulting output files. Your output must match the output file format. There will be at least a 5 point penalty if your program output does not match the example output.
• The Project 3 due date has been postponed to Monday, March 26. It is due at 11:59:59pm on March 26.
• Project 3: There's a slight mistake in the project description for choosing the median. Suppose there are n points, indexed from 0..n-1, and sorted into increasing order (either by increasing x or by increasing y). Then the value of m referred to in the project description should be the floor of (n-1)/2, not the floor of n/2. This is important. If you have n=10 points, then the value of m referred to in the handout will cause the set of points to be split into 6 point and 4 point subsets!
  
• Homework 2 is due Monday, March 5: postscript , pdf . Be sure to write your name, section number, and RPI email address on your homework submission.
  
• Project 2: The example output file results.txt has been updated again so all cancellation requests are reported in the same format.
• Project2: The files request.txt and the resulting example output of results results.txt have been updated to correct an error (two flights had the same id).
• Project2: Here is an example input file of requests request.txt and the resulting example output of results results.txt . Please try to match your output as closely as possible to this example output. Look at notes.txt for additional notes on the output format. Note that you must perform more extensive testing of your program.
  
• Lecture 8 Exercise solutions postscript , pdf , Exam review solutions postscript , pdf
  
• Graded homeworks are available outside Amos Eaton 112 if you have not yet picked up your homework.
• Homework 1 solutions: postscript , pdf
  
• There will be no lab the week of February 12 and week of February 19.
• WARNING: The matrix addition and multiplication operators should not use the get function to obtain element values while looping over the rows or columns of the matrix. This leads to code where addition and multiplication are implemented extremely inefficiently! An example for addition might look like

    template <class T>
    sparse_matrix<T>
    sparse_matrix<T>::operator+( const sparse_matrix& rhs ) const 
    {  sparse_matrix<T> result( this->rows.size(), this->cols.size() );
       for ( int i=0; i<this->rows.size(); ++i )
         for ( int j=0; j<this->cols.size(); ++j )
            T value = this->get( i, j) + rhs.get(i, j);
         if ( value != T(0) ) result.put(i, j, value );
       return result;
    }
  

  This will be penalized heavily because it does not make use of the sparse structure. To exploit the sparseness of the matrix, you should step through the linked lists and perform computations using only non-zero elements. You can use the put function to insert elements into the resulting matrix.
• Similarly, to exploit the sparseness of the matrix, you should not use the get function in your copy constructor and assignment operator.

Books

• Data Structures and Algorithm Analysis in C++, 2nd edition, Mark A. Weiss, Addison Wesley, 1999. ISBN: 0-201-36122-1.
  

• The C++ Programming Language, 3rd edition, Bjarne Stroustrup. Addison Wesley, 1997. ISBN: 0-201-88954-4.
  

Links

• Standard Template Library Programmer's Guide . You may find it helpful to start here: Table of Contents .
• Cygwin tools (including Gnu C++ compiler and bash) for Windows machines.
• Emacs for Windows.