CSCI-2300: Data Structures and Algorithms
Sections 2, 3, 4, 7
Spring 2006

Course Information

Time: Monday and Thursday, 12:00pm - 1:20pm
Classroom: Sage 3510 Sage 3303 (new location!)
Credits: 4
Prerequisites: Computer Science II (CSCI-1200), Discrete Structures (MATH-2800), and Calculus I (MATH-1010).

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

Grad TAs:
Vineet Chaoji
Email: chaojv@rpi.edu
Office Hours: Tuesday 2-3pm, Friday 2-3pm
Ethan Glasser-Camp
Email: glasse@cs.rpi.edu
Office Hours: Wednesday 12-1pm, Thursday 4-5pm,
Brandeis Hill
Email: hillb@cs.rpi.edu
Office Hours: Monday 11am-12noon, Friday 1:30-2:30pm
Office Hours location for TAs: Amos Eaton 217

Description

Syllabus. pdf file.

Books

• Data Structures and Algorithm Analysis in C++ , 2nd edition, Mark A. Weiss, Addison Wesley, 1999. ISBN: 0-201-36122-1.
  
• Introduction to the Design and Analysis of Algorithms , Anany V. Levitin, Addison Wesley, 2002. ISBN: 0201743957.
  

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

Labs

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

Lab

• Lab 1: lab1.pdf
• Lab 2: lab2.pdf , tmax1.cpp , timer.h , tmax1a.cpp , tsort2.cpp
  
• Lab 3: lab3.pdf
• Lab 4: lab4.pdf , demo_main.cpp, BSTree.h.
• Lab 5: lab5.pdf
• Lab 6: Lab6 , student.cpp, student.h, main.cpp
  Note: There will be no class lecture on March 9 (Thursday)!

• Lab 7: Lab7 , main.cpp, binary_heap.h
• Lab 8: Lab8 , test.cpp , quicksort.h , insertion_sort.h , rng.h , timer.h , counter.h .

• There are no labs the week of April 3, 2006 due to GM week.
• Lab 9: lab9.pdf , Graph1.cpp , compile.txt , courses.txt , west.txt , cycle.txt
  Note: Please see posted Project 3 below.

• Lab 10: lab10.pdf , Graph1.cpp , mstnet.txt , weiss.txt
  
• Lab 11: lab11.pdf , Graph1.cpp , rpi.txt , components.txt , slogan.txt
  
• Lab 12: Lab12 Note: This is an optional self-study lab on dynamic programming. There will be no official labs this week (May 3).

Lab solutions

• Lab1: lab1_sol.pdf
• Lab2: lab2_sol.txt , tfib.cpp ,
• Lab3: lab3_sol.pdf
• Lab 4: BSTree.h
• Lab 5: lab5_sol.pdf (partial solution)
• Lab 6: main.cpp, main_mm.cpp
• Lab 7: main.cpp, binary_heap.h, max_binary_heap.h,
• Lab 8: step3.h , step5.h , step6.h , step7.h , step8.h , step9.h , step10.h , step11.h , step12.h .
• Lab 9: Graph1_topsort.cpp
• Lab 10: Graph1_mst.cpp

Lectures

Code from class lectures:

• Class 6 (Feb 6): max_sub.cpp
• Class 8 (Feb 13): BSTree.h , compare_main.cpp
  
• Class 11 (Feb 23): demo_main.cpp
  
• Class 13 (Mar 2): main.cpp , hash.h
  
• Class 14 (Mar 6): binary_heap.h
  
• Class 17 (Mar 23): class17_sorts.h
  
• Class 18 (Mar 27): class18_sorts.h
  
• Class 19 (Mar 30): select.h
  
• Class 21 (Apr 6): Graph1.cpp
  

Projects

• Project 1: Due Friday, February 10.
  

• Project 2: . Due Tuesday, March 28.

• Project 3: . Due Friday, April 28.
  

Homeworks

• Homework 1: hw1.pdf . Due Monday, January 30. Be sure to write your name, section number, and RPI email address on your homework submission.
  
• Homework 1 solutions: hw1_sol.pdf .

• Homework 2: hw2.pdf . Due Monday, February 13. Be sure to write your name, section number, and RPI email address on your homework submission.
  Note: There was an error in the loop counter of the innermost for loop of Qn 1(a). The pdf file has now been corrected.
• Homework 2 solutions: hw2_sol.pdf .

• Homework 3: Revised hw3.pdf , BSTreehw3.h . Due Monday, March 6.
  Be sure to write your name, section number, and RPI email address on your homework submission.
  To receive credit, submit Questions 1--4 and 9--10 of your HW at the beginning of lecture , and Questions 5--8 before midnight on March 6. Online submission instructions have been posted below (in the Announcements section).

• Homework 3 code testing and solutions: hw3.instructions, Perl grading script, README, main_sol.cpp , main.cpp, BSTreehw3.h, correct_sol.txt, compile-net.bat.

• Homework 3 (partial) solutions: hw3_sol.pdf .

• Homework 4: hw4.pdf . New due date: Monday, April 3.
  Be sure to write your name, section number, and RPI email address on your homework submission.
  

• Homework 4 (partial) solutions: hw4_sol.pdf .

• Homework 5: hw5.pdf . Due Monday, May 1.
  Be sure to write your name, section number, and RPI email address on your homework submission.
  Note: For questions 2(b) and 4(b), assume the edge weights are integers.
• Homework 5 solutions: hw5_sol.pdf .

Exams

• Exam 1 is on Tuesday, February 21 from 12:00pm to 1:50pm in Sage 3303. (Don't forget, Tuesday follows a Monday schedule!)

• Exam 1 review questions and list of formulas that will be provided on the exam.

• Solutions to Exam 1 review questions review1_sol.pdf
  

• Partial solutions to Exam 1 exam1_sol.pdf
  

• Exam 2 is on Monday, April 10 from 12:00pm to 1:50pm in Sage 3303.

• Exam 2 review questions: review2.pdf

• Solutions to Exam 2 review questions review2_sol.pdf
  

• List of rotations that will be provided on the exam.

• Solutions to Exam 2 exam2_sol.pdf
  

• The Final Exam will be held on Thursday, May 11 from 3:00pm to 6:00pm during Finals week. It will be a comprehensive exam covering all material from the course. The location for the Final Exam is Amos Eaton 214/216.

• Review questions on graphs to help you prepare for the Final: review.pdf

• Solutions to review questions on graphs: review_sol.pdf

Announcements

• A few of you seem to be confused about the HW and Project contributions to the grade. First note that as per the syllabus, each HW is worth 3.75% and each project is worth 7.5%. As I discussed in class, there are two equivalent ways to view this.
  1. You can think of HW 3 as counting as one of the Projects (worth 7.5% each) and the remaining 4 HWs as the 4 HWs (each worth 3.75%) mentioned in the syllabus.
  2. You can view HW 3 as counting for twice as many points as a regular HW since it had 100 points (unlike the other HWs which had 50 points). So HW 3 would contribute 7.5% of the grade, and each Project would contribute 7.5% of the grade.
• If you have questions regarding your grade on the Final, please first send email to your section TA and cc me. (I am away at a conference.)
• I have just submitted grades on SIS. I curved HW 3 and lowered the cutoffs as follows:
  A: 88.25, B: 78.8, C: 68.475, D: 58.8.
  Have a good summer!
• The DSA Final Exam scores will be posted on WebCT later today. The average score was 70.42 and the highest score was a 97. I will finalize letter grades and submit to SIS by this evening.

  If you wish to see your Final Exam, please see it in Pam Paslow's office (-- you cannot take it with you). Pam Paslow will be in AE 123B today and Wednesday from 7-2:30, and in MRC 334 (?) on T,R from 7-2:30. She will be off on Friday to work on the commencement.

• Graded HW 5 for all sections are outside my office (MRC 330B).
• New!: If you need to see the class lecture notes, go here .
• I have posted (partial) solutions to Exams 1 and 2 above.
• HW 5 solutions have been posted above.
  

• If you are sending me email, particularly about grading issues, please state your section in your email and also cc the grad TA for your section. Doing so will help us respond sooner to your email. Thanks.
• All students should have resolved issues with scores posted on WebCT by now (Saturday, May 6).
  
• For students in Section 7 (Wednesday 2:00-3:50pm): Please contact Vineet immediately if you have any Project 3 grading issues. He goes out of town on Monday, May 8.

• There will be no official labs this week (May 3). I have posted an optional self-study lab on dynamic programming for those who are interested.
• HW5: For questions 2(b) and 4(b), assume the edge weights are integers.
• The final exam is Thursday, May 11 from 3:00pm to 6:00pm. I believe all final exam schedule conflicts have been resolved.
• Please check your course scores thus far posted on WebCT, and contact your TA immediately to correct any errors. Any errors in grade entry must be corrected by Thursday, April 20.
• Project 3 is now posted. It is due Friday, April 28.

• New: List of rotations that will be provided on the exam.
• New!: If you need to see the class lecture notes, go here .
• New: I have posted partial solutions for HW 3 and HW 4 above.

• Please see the Project 2 web page FAQ for a note about the analysis of the kd-tree orthogonal range query.
• Lab 8 on Quicksort has been posted since it is very long. Please make sure you read it before you go to lab.
• As discussed in class, the new due date for HW 4 is Monday, April 3 .

• There will be no class lecture on March 9 (Thursday)!
• My office hours on Wednesday (March 8) are cancelled.
• Exam 1 grading: Qns 1 and 4: Vineet, Qns 2 and 5: Ethan, Qns 3 and 6: Brandi.

• HW 3, Qn 8: To store the calculated height, please add a height member variable to the BSNode class (as in Lab 4).
• HW 3, Qn 3(a): You do not need to prove this by induction. It may help you to try answering the following two questions in your solution. What do the two terms in the product (inside the summation) signify? Why does the summation go from 0 to n-1?
• HW 3, Qn 3(b): Successor refers to the inorder successor and predecessor refers to the inorder predecessor.
• As mentioned in class, for Qn 1, you cannot just invoke the Master Theorem to get the answer.
• Homework 3 Submission: Please submit only your filled-in BSTreehw3.h file. Please add any discussion of the running time of your algorithm to the comments accompanying the function.
  Important: Please verify you are submitting your homework under the correct section. You will be penalized for submitting to an incorrect section.
  • Section 2, (Wednesday 10:00-11:50am; Sage 4101), TA: Ethan Glasser-Camp
    
  • Section 4, (Wednesday 4:00-5:50pm; Sage 2715), TA: Brandi Hill
    
  • Section 7, (Wednesday 2:00-3:50pm; Sage 4101), TA: Vineet Chaoji
    

• The revised HW 3 has been posted above (2pm, Thursday, March 2). The changes are mainly in Qns 5--8.
• HW 3 has been posted above.

• New!: If you need to see the class lecture notes, go here .

• Solutions to Exam 1 review questions have been posted above.
  
• Exam 1 review questions and list of formulas are posted above. Solutions will be posted by Monday morning.
  
• AVL trees will not be included for Exam 1.

• Graded HW 2 for Sections 4 and 7 are outside my office (MRC 330B).
• HW 2 solutions have been posted above.
  
• HW 2 correction: There was an error in the loop counter of the innermost for loop of Qn 1(a). The pdf file above has now been corrected.
  
• HW 2 is out (see above). Due at beginning of lecture on Feb 13.
  Graded HW 1 is outside my office if you did not pick it up in class today.
  
• My office hours today (Wed, Feb 1) will be 3:30-4:30pm (instead of the regular 3-4pm).
• All TA office hours have been posted above.
• Section 3 (Tuesday 6pm) has been cancelled. All students in that section should sign up for one of the other sections.
  
• Project 1 is out (see above).
  
• My office hours today (Wed, Jan 25) will be 3-3:30pm. If you were planning to meet me between 3:30 and 4pm today, please send me email. Or we can talk after class on Thursday.
  
• HW 1 is out (see above). Due at beginning of lecture on Jan 30.
  
• The new location for class is Sage 3303.
  
• Labs begin the second week of classes.
  

Links

• Standard Template Library Programmer's Guide . You may find it helpful to start here: Table of Contents .
• C++-FAQ-Lite
• Cygwin tools (including Gnu C++ compiler and bash) for Windows machines.
• Emacs for Windows.
• Programming Pearls , sorting animations
• Computing the Mysteries of Attraction , Harvard Magazine article , 1965 Harvard Crimson article .