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

Course Information

Time: Tuesday and Friday, 10:00am - 11:20am
Classroom: Amos Eaton 214
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 7:
Viswanath Ramakkagari
Email: ramakv@rpi.edu
Office Hours: Monday 2:00-3:00 pm, Thursday 2:00-3:00pm
Office: Amos Eaton Basement, x2396

Grad TA for Sections 2 and 3:
Yogi Girdhar
Email: girdhy@rpi.edu
Office Hours: Monday 12:30-1:30pm, Wednesday 12:30-1:30pm
Office: Amos Eaton Basement, x2396

Description

Syllabus. 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

• Lab 12: lab12.pdf , Graph1.cpp , mstnet.txt , weiss.txt
  
• Lab 11: lab11.pdf , Graph1.cpp , compile.txt , courses.txt , west.txt , cycle.txt
  
• There are no labs this week (April 8-9). You may meet your section TA for help with Project 3 during lab hours. Location will be the TAs' office hours location.
• Lab 10: Lab10 , merge.h, main.cpp
• Lab9: Lab9 , test.cpp , quicksort.h , insertion_sort.h , rng.h , timer.h , counter.h .
• Lab 8: Lab8 , main.cpp, binary_heap.h,
• Lab7: lab7.pdf
• Lab 6: lab6.pdf , demo_main.cpp, BSTree.h,
• There is no lab this week (Feb 18-19).
• Lab 5: Lab5 , student.cpp, student.h, main.cpp
• Lab4: lab4.pdf
• Lab3: lab3.pdf
• Lab2: Lab2 , main.cpp , complex.cpp , complex.h
  
• Lab1: Lab1 , buffer.cpp , buffer.h , main.cpp
  

Lab solutions

• Lab1: discussion , buffer.cpp , buffer.h , main.cpp
  
• Lab 2: complex.h , complex.cpp , main.cpp , main_list.cpp .
  
• Lab 3: lab3_sol.pdf
• Lab 4: lab4_sol.pdf
• Lab 5: main.cpp, main_mm.cpp
• Lab 6: BSTree.h
• Lab 7: lab7_sol.pdf
• Lab 8: main.cpp, binary_heap.h, max_binary_heap.h,
• Lab9: step3.h , step5.h , step6.h , step7.h , step8.h , step9.h , step10.h , step11.h , step12.h .
• Lab 10: merge.h
• Lab 11: Graph1_topsort.cpp
• Lab 12: Graph1_mst.cpp

Lectures

Code from class lectures:

• Class 2 (Jan 17): Version 1: polynomial.h , polynomial.cpp , main.cpp
  Version 2: polynomial.h , polynomial.cpp , main.cpp
  
• Class 7 (Feb 4): max_sub.cpp
• Class 9 (Feb 11): BSTree.h
  
• Class 11 (Feb 21): demo_main.cpp , compare_main.cpp
  
• Class 13 (Feb 28): main.cpp , hash.h
  
• Class 15 (Mar 7): binary_heap.h
  
• Class 17 (Mar 21): class17_sorts.h
  
• Class 18 (Mar 25): class18_sorts.h
  
• Class 23 (Apr 15): Graph1.cpp
  

Projects

• Project 1: Due Friday, February 7.
  

• Project 2: . Due Monday, March 17.
  

• Project 3: . Due Thursday, April 10.

• Project 4: . Due Wednesday, April 30.
  

Homeworks

• Homework 1: hw1.pdf . Due Friday, January 24. 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 Friday, January 31. Be sure to write your name, section number, and RPI email address on your homework submission. (NOTE: See announcement below!)
  
• Homework 2 solutions: hw2_sol.pdf .
• Homework 3: hw3.pdf . Due Friday, February 28.
  Be sure to write your name, section number, and RPI email address on your homework submission. (NOTE: See HW3 announcement below!)
  Here is a FAQ for HW 3: hw3.faq
• Homework 3 solutions: hw3_sol.pdf .
• Homework 4: hw4.pdf . Due Friday, March 28.
  Be sure to write your name, section number, and RPI email address on your homework submission.
  
• Homework 4 solutions: hw4_sol.pdf .
• Homework 5: hw5.pdf . Due Friday, April 25.
  Be sure to write your name, section number, and RPI email address on your homework submission.
  (NOTE: See HW5 clarifications below!)
  
• Homework 5 solutions: hw5_sol.pdf .

Exams

• Exam 1 is on Friday, February 14 from 10:00am to 11:50am in West Hall Auditorium.
• Exam 1 review questions review1.pdf
  
• Solutions to Exam 1 review questions review1_sol.pdf
  
• Solutions to Exam 1 exam1_sol.pdf
  

• Exam 2 is on Friday, April 4 from 10:00am to 11:50am in West Hall Auditorium.
• Exam 2 review questions: review2.pdf , Exam 2 topics: exam_topics.pdf
• Solutions to Exam 2 review questions review2_sol.pdf
  
• Exam 2 has been rescheduled for Tuesday April 8 from 10:00am to 11:50am in West Hall Auditorium.

• Solutions to Exam 2 exam2_sol.pdf
  

• Important: The Final Exam is on Monday, May 5 from 3:00pm to 6:00pm in DCC 308. All final exam schedule conflicts have been resolved, so the time is now fixed and there will be no makeup exam.

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

Announcements

• I have submitted final course grades on SIS. I set the grade cutoffs as follows: A(89), B(79), C(69.5), D (60) after I curved HW2, Exam 1, and the Final Exam. I double checked the Final exams of all students within one point of a grade cutoff. I will ask the TAs to post your raw Final Exam and HW 5 scores on WebCT. If you wish to see your Final Exam, stop by my office. Have a good summer!
• The test cases used for Project 4 grading are on the Project 4 web page.

• Graded HW5 is available outside my office. Final Exam and Project 4 grading is going on right now. I expect it will be at least a day after you receive the Project 4 grades before the course grades will be ready.

• I will be holding special office hours 4-5pm on Thursday in my office (AE 112). If you have any Project 3 or other grading issues you wish to discuss with me, please stop by then.

• Viswanath will hold special office hours on Thursday and Friday at 10:30--11:30am and Yogi will hold special office hours on Thursday and Friday at 1-2pm. Please use these times to resolve any HW or Project grading issues.

• The Final Exam is on Monday, May 5 from 3:00pm to 6:00pm in DCC 308.
• Instructions for all Labs have been posted above.
• The test cases used for Project 3 grading are on the Project 3 web page.
• Solutions to review questions on graphs: review_sol.pdf .
• Review questions on graphs to help you prepare for the Final: review.pdf .
• HW5: Since we did not complete our discussion of graph traversal algorithms, you may submit the solution to Qn. 5 of HW 5 in class on Tuesday, April 29.
• HW5 clarification: If you need to add any additional vertex member variables for any of the code writing questions, just mention them clearly and then use them.
• HW5, Qn. 1 clarification: "Draw the vertices in topological order" means draw the vertices from left to right in a horizontal line in increasing topological order. Then when you draw the edges of the graph, all edges will go from left to right. (If not, you have an error!)
• For Exam 2, Qns. 1, 2, 3, 4, 6 were graded by Viswanath and Qns. 5, 7, 8 were graded by Yogi. Solutions to Exam 2: exam2_sol.pdf .
  
• The final exam is 3:00-6:00pm on Monday, May 5. If you have an exam schedule conflict, please send me email with your exam schedule by Friday, April 19.
• Here is the Project 4 description . Due Wednesday, April 30.
  
• Since Exam 2 was postponed to this Tuesday, the due date for Project 3 has been extended to 11:59:59pm on Saturday, April 12. Please note that you should get all your questions answered by Friday since the TAs and instructor will not be available on Saturday.
• There are no labs this week. You may meet your section TAs for help with Project 3 during lab hours. Location will be the TAs' office hours location.
• Exam 2 has been rescheduled for Tuesday April 8 from 10:00am to 11:50am in West Hall Auditorium.
• NEWS FLASH! As morning classes today (April 4) have been cancelled due to the weather, Exam 2 will not be held today. Exam 2 will probably be held on Tuesday April 8 from 10:00am to 11:50am. I will confirm the new time and location on this web page later today. Meanwhile please work on Project 3 in the safety of your rooms!

• Solutions to Exam 2 review questions: review2_sol.pdf
  
• Exam 2 topics: exam_topics.pdf
• Here are some Exam 2 review questions: review2.pdf .
  
• HW 4 solutions have been posted above.
• HW 3 solutions have been posted above. Qns. 1 and 2 were graded by Viswanath, and Qns. 4, 5, 6 were graded by Yogi. Graded HW 3 are available outside Amos Eaton 112.
• The Project 3 page has been updated with example files. Please make sure to match your output format to the example output format.
• Please check your grades posted on WebCT, and contact your TA immediately to correct any errors.
• For more info on Introsort, see Prof. Musser's description .
• Here is Project 3 , due by 11:59:59pm on Thursday, April 10.
• Here is the link to the sorting animations from Programming Pearls that we saw in class.
• New! In view of the fact that we have no office hours for Project consultation this week, the due date for Project 2 has been changed to 11:59:59pm on Thursday, March 20.
  
• These fine people have volunteered to be your class representatives: Tim Robichaud (Section 1) , Jonathan Lobel (Section 2) , Ryan Jerchau (Section 3) , Thomas Manhart (Section 7) . Please contact them with DSA suggestions, concerns, and comments. Of course, you are always welcome to talk to or email me or the TAs.
• The files used for testing Project 1 are available here .
• Here are the sample files for Project 2 .
• Here is a FAQ for HW 3: hw3.faq .
• I will not be holding office hours on Thursday (Feb 27) as I will be teaching in Prof. Luk's class. Viswanath will be holding extended office hours from 2:00 to 3:30pm to answer any questions you may have.
• Project 2 has been posted: project2.pdf . Due on Monday, March 17.
• Since we did not cover splay trees in class yet, you can hand in your answer to Qn. 5 of HW 3 at the beginning of lecture on Tuesday, March 4.
• Graded Exam 1 was handed back in class. Solutions to Exam 1 are here: exam1_sol.pdf . Yogi graded the odd numbered questions and Viswanath graded the even numbered questions. Please contact the corresponding TAs if you have any grading concerns. If there was an addition error in your exam score, please see your section TA.
  
• Important: The Final Exam is on Monday, May 5 from 3:00pm to 6:00pm. If you have a final exam schedule conflict, please send me email by Monday, February 24 indicating which course (course name, number, section, and instructor name) the conflict is with.
• Homework 3 is now available: hw3.pdf .
• HW 3 has not yet been posted. It will be due next week, not this Friday (Feb 21) as originally mentioned in the syllabus.
• As mentioned in the syllabus, there is no lab this week (Feb 18-19) since Tuesday is a Monday.
• I am unable to make it in for office hours today (Tuesday, February 18). Please send me email if you need to meet me.
• Graded HWs are outside Amos Eaton 112. You can find links to HW solutions above. Qns. 1, 2, 3 were graded by Viswanath, and Qns. 4 and 5 were graded by Yogi. Please contact them if you have any grading questions.
• Here are some Exam 1 review questions pdf
  
• As mentioned in class, your lab grade for the semester will be based on your best 11 lab scores among all 12.
• Chap. 7.6.1 (Weiss textbook) has a discussion of a couple of methods to evaluate a recurrence equation.
• Please check the Project 1 page frequently for project updates and clarifications.
• HW 1 has been graded. Viswanath graded Qns 1, 4, 5, and Yogi graded Qns. 2 and 3. If you have grading concerns about a question, please contact the corresponding TA.
• You can submit your solution to Qn. 5 on HW 2 at the beginning of class on Tuesday, February 4 if you wish. Solutions to all remaining questions must be submitted at the beginning of class on Friday, Jan 31.

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.
• Programming Pearls , sorting animations