CSCI-2300: Data Structures and Algorithms
Sections 2, 3, 4, 5, 6, 7
Spring 2004

Course Information

Time: Monday and Thursday, 10:00am - 11:20am
Classroom: DCC 318
Credits: 4
Prerequisites: Computer Science II (CSCI-1200) and Calculus I (MATH-1010).

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

Grad TAs:
Douglas Gregor , Head TA
Email: gregod@cs.rpi.edu
Phone: 276-8981
Office Hours: Mon 2-3pm, Fri 1-2pm
Nagender Parimi
Email: parimi@cs.rpi.edu
Phone: 276-8556
Office Hours: Thu 3-4pm, Fri 4-5pm, Location: Lally 3
Evan Shechter
Email: sheche@rpi.edu
Office Hours: Tue: 4:30-5:30pm, Fri: 2-3pm
Metin Inanc
Email: inancm@rpi.edu
Office Hours: Wed 1-2pm, Fri 2-3pm

Office Hours location: Science Center 1W01 (Bray Room) (except for Nagender Parimi)

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 a C++ reference book to the lab.

Lab

• Lab 12: lab12.pdf , Graph1.cpp , rpi.txt , components.txt , slogan.txt
  
• Lab 11: lab11.pdf , Graph1.cpp , mstnet.txt , weiss.txt
  
• Lab 10: lab10.pdf , Graph1.cpp , compile.txt , courses.txt , west.txt , cycle.txt
  
• There are no scheduled labs this week (March 30-31) since it is GM week.
• Lab9: Lab9 , test.cpp , quicksort.h , insertion_sort.h , rng.h , timer.h , counter.h .
• Lab 8: (Please see Announcements below:)
  Lab8 , main.cpp, binary_heap.h
• Lab7: lab7.pdf
• Lab 6: lab6.pdf , demo_main.cpp, BSTree.h.
• There are no labs this week (Feb 17-18).
• 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: Graph1_topsort.cpp
• Lab 11: Graph1_mst.cpp
• Lab 12: Graph1_traversal.cpp

Lectures

Code from class lectures:

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

Projects

• Project 1: Due Friday, January 30.
  IMPORTANT: Please see correction on Project 1 web page.

• Project 2: New Due Date: Monday, March 1.
  

• Project 3: . Due Friday, March 26.

• Project 4: . Due Friday, April 23.
  

Homeworks

• Homework 1: hw1.pdf . Due Thursday, January 22. 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 Thursday, February 5. Be sure to write your name, section number, and RPI email address on your homework submission.
  Note: There was a small error in Question 1(a) which has now been corrected. Use index "i" for the terms inside the summation.

• Homework 2 solutions: hw2_sol.pdf .

• Homework 3: hw3.pdf . Due Thursday, March 4.
  Be sure to write your name, section number, and RPI email address on your homework submission.
  To receive credit, submit your HW at the beginning of lecture .

• Homework 3 solutions: hw3_sol.pdf .

• Homework 4: hw4.pdf . Due Monday, March 22.
  Be sure to write your name, section number, and RPI email address on your homework submission.
  NOTE: See Announcement about HW 4, Qn 5 below!

• Homework 4 solutions: hw4_sol.pdf .

• Homework 5: hw5.pdf . Due Monday, April 19.
  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 Tuesday, February 17 from 10:00am to 11:50am in West Hall Auditorium. (Don't forget, Tuesday follows a Monday schedule!)

  • 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 Monday, April 5 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
    

  • Solutions to Exam 2 exam2_sol.pdf
    

  • IMPORTANT: The Final Exam is on Wednesday, May 5 from 8:00am to 11:00am. If you have an exam conflict, please send me email by Monday, March 1 with full details (course name, number, section, and instructor name).

  • I believe all final exam schedule conflicts have been resolved, so there will be no makeup exam.

  • IMPORTANT: The Final Exam is on Wednesday, May 5 from 8:00am to 11:00am in West Hall Auditorium. Note that this location is different from that listed in the Poly. Also, there will be no makeup exam if you miss this exam.

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

  • Solutions to review questions on graphs: review_sol.pdf

  ---

  Announcements

  Last updated Tuesday, May 11 at 10:50am. Please check these announcements frequently.
  • Your graded Final Exams are now with Chris Coonrad in the CS Main Office (Lally 207). You can look at them to see how you did, but you cannot take them with you.

  • Alan Nouri says WebCT is working and that to view DSA on WebCT, "You just have to manually select the course."

    Instructions:
    1. Goto http://webct.rpi.edu/webct/public/show_courses.pl
    2. Select "view by term"
    3. pick spring 2004
    4. select DSA
    5. login
    

  • Clarification: Your DSA letter grade should be available on SIS. (Based on email from students, I am not sure if WebCT is working for DSA now.)

  • DSA grading is complete and I have submitted DSA grades on SIS. The grade cutoffs were: A: 88.725, B: 79.125, C: 69.196, D: 60.0. I will request the TAs to post Final exam grades on WebCT soon. I double checked the Final exams of all students within half a point of a grade cutoff. If you wish to see your Final exam, you can stop by my office. Have a good summer!

  • Grading update: Grading of the Final Exams has not yet been completed. Final grades will be assigned by Monday. I will post an announcement here as soon as grade assignment is completed.

  • IMPORTANT REMINDER: The Final Exam is on Wednesday, May 5 from 8:00am to 11:00am in West Hall Auditorium. Also, there will be no makeup exam if you miss this exam.

  • The handout for the Final Exam will have the formulas from Exam 1, rotation code from Exam 2, and the graph algorithm pseudocode/outline from the lecture notes for topsort, Dijkstra's, Prim's, DFS, BFS, and articulation points. You will need to know what types of graphs the graph algorithms may be applied to, as well as any initialization steps.

  • Solutions to review questions on graphs: review_sol.pdf

  • If you have any questions or issues to resolve before the Final, please contact Doug Gregor or your section TA (and cc me). I may not be able to respond to your email before Tuesday afternoon.

  • Graded HW 5 is available outside my office for all Sections.

  • Pdf files of lecture notes for all classes are available on WebCT in the Course Notes section.

  • Graded HW 5 is available outside my office except for Sections 6 and 7. Please pick those up from Metin later this week.

  • IMPORTANT: The Final Exam is on Wednesday, May 5 from 8:00am to 11:00am in West Hall Auditorium. Note that this location is different from that listed in the Poly. Also, there will be no makeup exam if you miss this exam.

  • I will be away and not be able to hold office hours on Tuesday, April 27.

  • I believe all final exam schedule conflicts have been resolved, so there will be no makeup exam.

  • Late days clarification: You may use a total of 3 late days over all 4 projects. If the cumulative number of late days you have used for your first three projects exceeds 3, you have no late days left for Project 4.

  • 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 those of you trying to figure out what your current grade is, here is a recap of the grading guidelines described in the syllabus. The final grading breakdown is: Laboratories 10 %, Programming Projects 30 %, Homeworks 15 %, Exams 45 %.

    You have so far received 74.5 % of your course grade (up to and including Project 3, HW 4, Lab 11, and Exam 2). You can compute your current score from the 10 best labs (each lab is worth 1 point, so multiply your score by 0.5), 3 projects (each worth 7.5 points, multiply by 0.075), 4 HWs (each worth 3 points, multiply by 0.06), and two exams (each worth 15 points, multiply by 0.15).

  • Congratulations to Dr. Doug Gregor on successfully defending his PhD!

  • Exam 2 grading:
    Qn. 1: Doug
    Qn. 2: Evan
    Qn. 3: Nagender
    Qn. 4: Nagender
    Qn. 5: Metin
    Qn. 6: Doug
    Qn. 7: Evan
    Qn. 8: Metin
    

  • 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 15.

  • Evan Shechter will not be holding his office hours on Tuesday (April 6) and Doug Gregor will not be holding his office hours on Friday (April 9).

  • Solutions to Exam 2 review questions review2_sol.pdf
    

  • Pdf files of lecture notes for Classes 8 through 19 (except Class 10 which was Exam 1) are available on WebCT in the Course Notes section.

  • Metin Inanc will be cancelling his Friday 2-3pm office hours and holding them instead on Wednesday 2-3pm. So his office hours this week will be Wed 1-3pm (March 31).
  • Nagender Parimi will be holding office hours today (Thursday, March 25th) from 6:30-7:30pm.
  • HW 4: Since we did not complete our discussion of quicksort, you may submit your answer to Qn. 5 during your lab next week. Of course, you can submit it on Monday if you have worked out the solution.

  • The section representatives for DSA are:
    Section 2: Anand Patil (Email patila@rpi.edu ).
    Section 3: Zyad Tamimi (Email tamimz@rpi.edu ).
    Section 4: Mark Stenpeck (Email stenpm@rpi.edu ).
    Section 5: Ben Russell (Email russeb@rpi.edu ).
    Section 6: Brad Greenwood (Email greenb3@rpi.edu ).
    Section 7: Kyle McDonald (Email mcdonk@rpi.edu ).
    

    Please contact them with any suggestions or issues. Of course, you are always welcome to contact me or the grad TAs directly.

  • Update on Lab 8: Today's lab is optional, although I encourage you to go to lab and do the work. We will use the best 11 of your 12 lab scores to compute your overall lab grade.
    For students in Sections 3 and 6 (Tuesday), if you missed a previous lab, you can attend one of the sections today to get credit if there is sufficient space in the room.

  • Since classes after 6pm today (3/16) are cancelled, students in Sections 3 and 6 should work on Lab 8 on their own. If you need help, consult the TAs during one of the lab sessions tomorrow. (The policy for grading credit will be posted later.)
    Students in other sections should go to their labs as usual tomorrow.

  • Homework 4: hw4.pdf . Due Monday, March 22.
    

  • Project 3: . Due Friday, March 26.

  • If you need to know your Project 2 grade for the drop deadline of March 5, you can send email to your section TA as soon as you submit the final version of your project. Since the TAs are very busy this week, please send them email regarding this only if you really need to know your grade for the Friday deadline.

  • Project 1 grades for Sections 2 and 3 have been posted on webct and sent out by email (3pm, Friday).

  • Project 1 grades have not yet been sent out to students in Sections 2 and 3. I apologize for the delay, but among other things the laptop on which the execution grades were compiled crashed. Evan will send these grades out as soon as they are ready (I expect today, Friday).

  • Homework 3: hw3.pdf . Due Thursday, March 4 at the beginning of lecture .

  • Exam 1 grading:
    Qn. 1: Nagender
    Qn. 2: Evan
    Qn. 3: Metin
    Qn. 4: Nagender
    Qn. 5: Doug
    Qn. 6: Doug
    

  • IMPORTANT: The Final Exam is on Wednesday, May 5 from 8:00am to 11:00am. If you have an exam conflict, please send me email by Monday, March 1 with full details (course name, number, section, and instructor name). Please also check with the other instructor if an alternative exam time for that course is being arranged.

  • New Due date for Project 2 is 11:59:59pm on Monday, March 1, 2004 .

  • Graded HW2 for all Sections are now available outside Amos Eaton 112.

  • Evan Shechter's office hours this week on Friday (Feb 13) have been changed to 3-4pm.

  • Here are Exam 1 review questions review1.pdf

  • Metin Inanc's office hours this week on Wednesday (Feb 4) have been changed to 4-5pm.

  • HW2: There was a small error in Question 1(a) which has now been corrected ( hw2.pdf ). Use index "i" for the terms inside the summation.

  • HWs are to be submitted on paper at the beginning of class, while programming projects are to be submitted online.
    
  • The WebCT discussion board for DSA is now available for use.
  • HW 1 is to be submitted at the beginning of class on Thursday, Jan 22.
  • HW1 is available at hw1.pdf .
  • Here is the Project 1 web page . Due date is Friday, January 30.
    IMPORTANT: Please see correction to project description on Project 1 web page (update at 1:30pm, January 15).

  • I will be out of town the week of January 19, and my office hours during this week are therefore cancelled. Please direct any questions, particularly about Project 1, to Doug Gregor (Email gregod@cs.rpi.edu ).

  ---

  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

  ---

  Srinivas Akella
  Department of Computer Science
  Rensselaer Polytechnic Institute
  110 8th Street
  Troy, NY 12180
  Email: sakella@cs.rpi.edu