CSCI-2300: Data Structures and Algorithms
Sections 1, 2, 3, 7
Spring 2002

Course Information

Time: Tuesday and Friday, 10:00am - 11:20am
Classroom: Sage 3303
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 1 and 2:
Jitendra Deshpande
Email: deshpj@cs.rpi.edu
Office Hours: Tuesday 4:00-5:00 pm, Wednesday 1:00-2:00pm
Office: Lally 9, x8981

Grad TA for Sections 3 and 7:
Justin Chen
Email: chenh3@rpi.edu
Office Hours: Monday 12:00-1:00pm, Friday 12:00-1:00pm
Office: Lally 3A, x8556

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

• Lab1: buffer.cpp , buffer.h , main.cpp
  
• Lab2: dlist.h , main.cpp
  
• Lab3: Animal.h , Cage.h , main.cpp , cagedata.txt , input.txt
  
• Lab4: complex.h , complex.cpp , main.cpp ,
• Lab5: accum.cpp , dlist.h , main.cpp .
• Lab6: (Feb 26/27) Please see announcement below.
• Lab6: BSTree.h , demo_main.cpp .
• Lab7: student.h , student.cpp , main.cpp .
• Lab8: merge.h , main.cpp .
• Lab9: test.cpp , quicksort.h , insertion_sort.h , rng.h , timer.h , counter.h .
• There is no lab the week of April 8 since it is GM week.
• Lab10: Graph1.cpp , courses.txt , west.txt , cycle.txt .
• Lab11: Graph1.cpp , mstnet.txt , weiss.txt .
• The last lab was Lab 11. There is no lab this week (April 30)!

Lab solutions

• Lab1: discussion , buffer.cpp , buffer.h , main.cpp
  
• Lab2: discussion , dlist.h , main.cpp
  
• Lab3: Cage.cpp , main.cpp
  
• Lab4: complex.h , complex.cpp , main.cpp , main_list.cpp .
  Note: You may need to download and install Visual Studio Service Pack 5 from Microsoft's site for VC++ to be able to handle friend functions.
• Lab5: accum.cpp , dlist.h
• Lab6: BSTree.h .
• Lab7: main.cpp , main_mm.cpp .
• Lab8: merge.h .
• Lab9: step3.h , step5.h , step6.h , step7.h , step8.h , step9.h , step10.h , step11.h , step12.h .
• Lab10: Graph1_sol.cpp .
• Lab11: Graph1_mst.cpp .

Lectures

• Class 1 (Jan 15): primes.cpp
  
• Class 2 (Jan 18): int_array.h , int_array.cpp , test_array.cpp , primes.cpp
  
• Class 3 (Jan 22): t_array.h , test_array.cpp , primes.cpp primes_vect.cpp
  
• Class 5 (Jan 29): Version 1: polynomial.h , polynomial.cpp , main.cpp
  Version 2: polynomial.h , polynomial.cpp , main.cpp
  
• Class 9 (Feb 12): max_sub.cpp
  
• Class 12 (Feb 26): BSTree.h
  
• Class 13 (Mar 1): demo_main.cpp , compare_main.cpp
  
• Class 15 (Mar 8): main.cpp , hash.h
  
• Class 16 (Mar 19): BinaryHeap.h , BinaryHeap.cpp , dsexceptions.h
  
• Class 18 (Mar 26): insert.h , mergesort.h , heap.h , basic_quick.h
  
• Class 19 (Mar 29): quick.h , select.h
  
• Class 22 (Apr 9): Graph1.cpp

Acknowledgment: Class lecture notes and code examples are based on those generously provided by Prof. Chuck Stewart.

Projects

• Project 1: postscript , pdf . Due Wednesday, February 6.
  nba.txt , tfile.txt , pfile.txt
  Sample input and output files.

• Project 2: postscript , pdf . Due Monday, March 4.
  sample files and expected output

• Project 3: postscript , pdf . Due Friday, March 29.
  Project 3 notes and sample files

• Project 4: postscript , pdf . Due Tuesday, April 30.
  Project 4 notes and sample files

Homeworks

• Homework 1: postscript , pdf . Due Tuesday, January 29. Be sure to write your name, section number, and RPI email address on your homework submission.
  
• Homework 1 solutions: postscript , pdf .
• Homework 2: postscript , pdf . Due Tuesday, February 12. Be sure to write your name, section number, and RPI email address on your homework submission.
  
• Homework 2 solutions: postscript , pdf .
• Homework 3: postscript , pdf . Due Tuesday, March 19. Be sure to write your name, section number, and RPI email address on your homework submission.
  
• Homework 3 solutions: pdf .
• Homework 4: pdf . Due Tuesday, March 26. Be sure to write your name, section number, and RPI email address on your homework submission.
  
• Homework 4 solutions: pdf .
• Homework 5: pdf . Due Friday, April 19. Be sure to write your name, section number, and RPI email address on your homework submission.
  
• Homework 5 solutions: postscript , pdf . Correction: The correct solution to Question 1 was updated at 3pm on April 25.

Exams

• Exam 1 is on Friday, February 15 from 10:00am to 11:50am in Sage 3303.
• Exam 1 review questions postscript , pdf
  
• Exam 1 review solutions postscript , pdf
  
• Exam 1 solutions postscript , pdf .
  
• Exam 2 is on Friday, April 5 from 10:00am to 11:50am in Sage 3303.
  
• Exam 2 review questions pdf
  
• Exam 2 review solutions pdf
  
• Exam 2 solutions postscript , pdf .
  
• The Final Exam is on Monday, May 6 from 6:30pm to 9:30pm in Sage 3303. If you have an exam conflict, please send me email before Friday, April 19 with your final exam schedule.
• Chapter 9 review questions pdf
  
• Chapter 9 review solutions pdf
  

Announcements

• The final grades are finally here: Section 1 , Section 2 , Section 3 , Section 7 . After curving Exam 1 and HW 2, the grade cutoffs were 88 (A), 78 (B), 69 (C), 59 (D). I checked the final exams of all students who were close to grade cutoffs. If you would like to see your graded final exam, please contact Chris Coonrad in the Computer Science Main Office (Lally 207). Have a good summer!
• Justin Chen will hold office hours 11:10am-12:10pm on Friday (May 10) to resolve any Project 4 grading issues. All Project 4 grades will be treated as final after this.
• Jitendra Deshpande will hold office hours 11am-noon on Friday (May 10) to resolve any Project 4 grading issues. All Project 4 grades will be treated as final after this.
• The DSA grades will be posted by the end of the day on Friday after all the final exams are graded and Project 4 grading is completed.
• Sections 1 and 2 will receive their Project 4 grades on Thursday. Students in Sections 3 and 7 should have received their Project 4 grades already.
• Justin Chen will be holding office hours 3:30-4:30pm on Thursday (May 9) to resolve any Project 4 grading issues. Jitendra Deshpande will also hold office hours on Thursday, probably from 4pm to 5:30pm.
• The Project 4 test files have been posted on the Project 4 notes and sample files page.
• The TAs have graciously agreed to hold office hours past the last day of classes to help students with final exam, project, or grading questions.
  • Jitendra Deshpande will hold office hours 12noon to 1:00pm on Friday, May 3 (instead of Justin Chen).
  • Justin Chen will hold office hours 1:00pm-2:00pm on Monday, May 6.
• I will have office hours today (Thursday, May 2) from 2 to 3:30pm. Please stop by then if you have any questions or issues to resolve.
• Clarification on late days: In the grade listings, the number of late days is the number of late days used thus far.
• There is no lab this week (April 30).
• If you need a note from me to resolve a final exam schedule conflict, I need to receive email from you by the end of the day today (Tuesday, April 30).
• HW 5 was graded by Jitendra Deshpande. Please direct all questions about HW 5 grading to him.
• All graded exams and homeworks are outside my office.
• Solutions to HW5 and Chapter 9 review questions have been posted above.
• Here are the grades so far: Section 1 , Section 2 , Section 3 , Section 7 . If you notice an error in your entered scores, please contact your section TA immediately. You have till Friday, May 3 to correct any errors. After that, all posted scores will be treated as final.
• Here is a description of the STL partial sort algorithm in email from Prof. Musser that you may find interesting.
• Important: Please see Project 4 clarification regarding the addition of a quit query on the Project 4 notes and sample files page.
• All students will be taking the Final Exam as scheduled at 6:30-9:30pm on Monday, May 6 in Sage 3303. No makeup exam will be given, even if you miss the Final exam.
  
• I have sent email to all students who reported a final exam schedule conflict. If you did not receive email from me regarding the final exam, you are listed as being able to take the final exam at 6:30-9:30pm on Monday, May 6.
  
• Project 3 grading: You can test your programs on the test files . If you have concerns about your Project 3 grades, please contact your section TA.
  
• Please see the Project 4 notes and sample files for information and announcements regarding Project 4. Be sure to check this Project 4 page frequently for updates and clarifications.
  
• Clarification on HW5, Question 4 (a): It should read "Find a topological sort of the directed acyclic graph below. Draw the vertices in topologically sorted order (from left to right), along with all edges of the graph.".
  
• Graded Exam 2 was handed back in class today (April 12). Justin Chen graded Questions 1, 2, 4, 6, and Jitendra Deshpande graded Questions 3, 5, 7, 8. Please contact them if you have any grading questions. Exam 2 solutions discussed in class will be posted this weekend.
• The Final Exam is on Monday, May 6 from 6:30pm to 9:30pm. Please send me email with your final exam schedule if you have an exam conflict. You should send me this information before Friday, April 19.
• Here are the grades so far (not including Project 3 and Exam 2): Section 1 , Section 2 , Section 3 , Section 7 . If you notice an error in your entered scores, please contact your section TA immediately. You have till Wednesday, April 17 to correct any errors.
• There is no lab the week of April 8 since it is GM week.
• Extra copies of the lecture handouts are outside my office (Amos Eaton 112). Let me know if handouts for a particular class are not available.
• Here is the web site with the sorting animations I showed in class: Programming Pearls: sorting animations .
  
• Solutions to the exam review questions, homeworks, and labs are now available above.
• Important: Exam 2 is on Friday, April 5 from 10:00am to 11:50am in Sage 3303. All material covered after Exam 1 (excluding graphs) is included in the topics for the exam. Here are some review questions: pdf .
  
• Graded HW 3 will be handed back during the labs this week. Questions 1-3 were graded by Justin Chen, and Questions 4-5 were graded by Jitendra Deshpande.
• Please check the clarifications on Project 3 in the Project 3 notes for any updates before you submit your project.
• Homework 4, Qn.5: Since we did not go over a leftist heap merge example, you can submit Qn. 5 during lab next week. I will complete discussion of leftist heaps in Tuesday's class (March 26). However I strongly recommend that you read the text and try to solve Qn. 5 before class since the merge operations can be a bit tricky.
• Project 2 grading: If you have concerns about your Project 2 grades, please contact your section TA. You can test your programs on the test input files and output file.
  
• Homework 4 is due on Tuesday, March 26.
• Look here for Project 3 notes and sample files .
• Project 3 is due on Friday, March 29.
• Homework 3 is due on Tuesday, March 19.
• Some of you have asked about your lcs_linear output differing from the example output we posted. Please ensure that your program is generating valid LCSs of the same size. If your program is working correctly and we are able to verify that, then you will receive either a small (or no) penalty. If your LCS is of incorrect size or if the edit distance differs, then there is likely a bug in your function.
• Important Project 2 debugging note: The most common problem has been runtime errors causes by "array out of bounds" errors. Note that the rows must be long enough to store the initialized value; If the sequence Y is aligned along the top, the rows size must be Y.size()+1. Be very careful not to run off the end of the array, especially when computing the reverse rows. If you are having strange runtime errors, the best debugging strategy is to print out the value of every cell computed and step through the algorithm for a very small example (sequences of size 3 or 4). This will help you detect the possible source of the error, which many students can not seem to find.
  The other common problem is mis-aligning the middle rows. Be aware that if the middle rows are not properly aligned to compute the edit distance, your algorithm may appear to work but will produce slightly smaller lcs sizes. Again, you should print out the values in the middle rows along with the sum used to predict the location of the lcs. Step through a small example to make sure you're selecting the correct vertical split.
  
• Project 2 submission: If you submitted Project 2 before 7pm on Friday (March 1), please resubmit your project on RCS. There appears to have been a problem and your submission may have been lost.
• Please return your Exam 1 to your section TA during lab next week (March 5-6) so we can review grading for Question 5.
• The scheduled lab activity for this week (Feb 26 and 27) will be postponed. However the TAs will be available during the lab session and you can consult them with questions about Project 2, or use the time to resolve Project 1 grading issues. You are strongly encouraged to use this time to work on Project 2.
• Important Note: Please resolve all Project 1 grading issues by Wednesday (Feb 27). Project 1 grades will be final and no changes will be permitted after this Friday (March 1).
• I will be unavailable during my regular office hours on Tuesday (Feb 26). Justin Chen has extended office hours from 12noon-2pm on Monday (Feb 25), and Jitendra Deshpande has extended office hours from 4-6pm on Tuesday (Feb 26) if you have any questions.
• For Exam 1, questions 1-3 were graded by Jitendra Deshpande, and questions 4-6 were graded by Justin Chen. For HW 2, questions 1-2 were graded by Justin Chen and questions 3-5 were graded by Jitendra Deshpande.
• Project 2: The project description files and Sequence.h have been updated again (Feb 20, 5pm). The changes are basically in the function specifications and prototypes for the member functions to compute the normalized edit distance and the LCS.
• Project 2: Here are the sample files and expected output . NOTE: The project 2 descriptions ( postscript , pdf ) have been updated to correct a few typos. Please be sure you have the corrected version.
• Graded Exam 1 will be handed back in class on Friday.
• Project 1: Justin Chen will be available 12noon-2pm on Friday and Monday to resolve any project 1 grading concerns for Sections 3 and 7.
• Project 1: Jitendra Deshpande will be available 8am-12noon and 1-2pm on Wednesday to resolve any project 1 grading concerns for Sections 1 and 2.
• Project 1 grading: If you have concerns about your Project 1 grades, please contact your section TA. You can test your programs on the test input files and compare your program output with the test output files .
  Important note: The program execution tests were performed by an automated grading script, and even a small difference between your program output and the expected output could cause a significant loss of points. It is in your best interests to test your program on the above input cases before you meet the TA.
  
• Project 2 is now available (see Projects section above). Relevant sample files will be posted shortly.
• Solutions to HW 2 and to the exam review questions are available above in the Homeworks and Exams sections of the web page.
• HW 2: You may resubmit your solutions to (only) Questions 4 and 5 at the start of your lab session this week if you wish. This is because we completed discussion of those topics in class today (Feb 12).
• HW 2: We will discuss material relevant to questions 4 and 5 in class on February 8 (Friday).
• Project 1: Some students have asked if you are required to create a default constructor, copy constructor, assignment operator, and destructor for all classes in your program. You should write these for all your classes -- you will lose some class design points if you do not implement them.
  At this stage you should probably focus on the functionality of your program first, since there are more points allocated for that, and then focus on writing the above functions if you haven't already done so.
• Graded HW 1 has been handed back. For grading questions about Questions 1-3, contact Justin Chen, and for Questions 4-5, contact Jitendra Deshpande.
• Project 1: The output.txt file has been updated again. You do not need to worry about setting the output precision of your floats/doubles.
• Please note that HWs or projects submitted by email are not graded, and will receive zero credit.
• Project 1: The output.txt file has been updated again.
• Project 1: The output.txt and bucks.txt sample files had some errors that have been corrected. Please download the most recent versions.
• Project 1: Sample input and output files are now available.
  
• Homework 1 has been handed out and is due at the beginning of class on Tuesday, January 29. Be sure to write your name, section number, and RPI email address on your homework submission.
  
• Project 1 has been handed out and is due by Wednesday, February 6.
• Copies of class lecture handouts and project handouts are available outside Amos Eaton 112.

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.