CSCI-313:
Data Structures, Fall 2008
CUNY Queens College
Course Structure * Course Topics * Assignments * Resources
Instructor:
Dr. Matt Huenerfauth
Office: Science Building A330 (office may change during the semester)
Phone: 7 1 8 - 9 9 7 - 3 2 6 4
Email: matt (AT) cs (DOT) qc (DOT) cuny (DOT) edu
Web: http://eniac.cs.qc.cuny.edu/matt
Office Hours: Mondays and Wednesdays from 5:30pm to 6:30pm.
Class Schedule:
Monday and Wednesday afternoons, 6:30pm to 7:45pm.
Classroom: Science Building A-103.
Note: Due to a travel conflict, I will need to reschedule the classes on October 14 and 15, 2008. We will discuss rescheduling options closer to the date during the semester. I anticipate setting up some extra class times during the week of October 20-24, 2008. I will also post the slides online, and I will be available to answer questions during office hours (or by appointment) during the week of October 20-24, 2008.
Online:
The public website for this course is: http://eniac.cs.qc.cuny.edu/matt/csci313/
Lecture slides, assignments, and handouts are only available on the BlackBoard site.
Course Prerequisites:
CSCI-211 (C++), CSCI-212 (Java), CSCI-220 (Discrete Structures).
Required Textbook:
Data Structures and Algorithms in Java (4th edition).
Authors: Michael T. Goodrich and Roberto Tamassia.
Publisher: John Wiley & Sons, 2006.
ISBN: 0-471-73884-0
Grading Percentages:
Your final grade in the class will be calculated as follows:
30% Homework Projects
30% Midterm Exam
30% Final Exam
10% Class participation
These percentages are tentative. Any changes will be announced in class.
Grading Equivalences:
Your final letter grade will be calculated as follows:
100.0-96.67 = A+
96.66-93.34 = A
93.33-90.00 = A-
89.99-86.67 = B+
86.66-83.34 = B
83.33-80.00 = B-
79.99-76.67 = C+
76.66-73.34 = C
73.33-70.00 = C-
69.99-66.67 = D+
66.66-63.34 = D
63.33-0.00 = F
Exam Policy:
The midterm exam will be administered in class sometime in the middle of the semester. The date will be announced in the first few weeks of the semester. There is no scheduled make-up for the exam; so, if for some reason you are unable to attend the exam, you should contact the instructor ahead of time to discuss the circumstances.
The final exam will occur during the final exam period of the semester.
Class Participation Policy:
Your class participation grade will be determined based on your attendance and active participation in class throughout the semester. Participating in discussions, answering questions, reading the textbook before class, and participating during in-class activities are all good ways to show "active participation." There are also CUNY/Queens College policies that can become applicable if there is an excessive number of lateness or absences.
Being considerate of your fellow students in the classroom is also an important part of your "class participation" grade. You can do this by not causing a distraction for your fellow classmates -- you can remember to turn off your cell phone before class, arrive on time for class, avoid side conversation or noise during class, etc. A good learning environment is also one in which everyone feels welcome and comfortable; so, please be respectful of the diversity of backgrounds, beliefs, and lifestyles of the students in our class.
Textbook Policy:
We will be following the organization and terminology of the textbook throughout the semester. (We will be covering some topics in a different order than they are presented in the textbook -- see the "COURSE TOPICS" section below.) You are encouraged to read the relevant chapters of the textbook before each class.
Grading Questions:
Your grades will be posted on BlackBoard during the semester. If you have specific questions about your grade on an assignment or exam, then the best way to proceed is to send an e-mail with your question to the instructor. You should mention which problem/question you are referring to, and you should discuss why you feel the grade should be reexamined.
Students with Disabilities:
If you are registered with the Office of Special Services for Students with Disabilities (OSS), please feel free to make an appointment with the course instructor to discuss any academic accommodations you may need. It is best if this is done at the beginning of the semester. If you need academic accommodations and are not registered with the OSS, please contact them in person at 171 Kiely Hall or by telephone at 718-997-5870. Upon individual request, this syllabus can be made available in alternative forms.
Students with Other Concerns:
If you are having academic concerns beyond issues specifically connected with this class, you may find it useful to make an appointment with an academic counselor at the Queens College Advising Center, tel: (718) 997-5599. If you need counseling or advisement beyond academic issues, you may find it useful to contact the Counseling and Advisement Center, tel: (718) 997-5420.
The following is a tentative set of topics that will be discussed in class. Specific calendar dates for each topic will be determined during the course of the semester. The numbers in the "Readings" column indicate the chapter and section numbers in the textbook that correspond to each topic.
|
Topics |
Readings |
|
Java Programming |
1, 2 |
|
Algorithm Analysis |
4 |
|
Recursion |
3.4 |
|
Arrays and Linked-Lists |
3.1-3.3 |
|
ADTs, Vectors, Lists, Iterators |
6.1-6.4 |
|
Stack, Queues, and Deques |
5 |
|
Trees |
7, 9.3, 10.1, 10.2, 10.4, 14.2.1, 14.3 |
|
Heaps (Priority Queues) |
8.1, 8.3 |
|
Sorting |
8.2.3, 8.3.5-8.3.6, 11.1-11.5, 14.4 |
|
Graphs |
13.1-13.6 |
|
Hash Tables |
9.1, 9.2 |
|
Algorithm Design Techniques |
11.1, 13.6 |
The most up-to-date listing of readings will be available on the BlackBoard website for the course.
Lecture Slides:
Slides will appear in the Course Documents page of the BlackBoard site.
An initial version of the slides will be posted shortly before class, and a final version of the slides will be posted after class. (We will use a TabletPC in class for lectures, and sometimes we will add additional drawings/comments to the slides during lecture.)
Assignments will be posted on the class page on BlackBoard as they are announced. Tentatively, there will be three homework projects for the semester. (Each would be worth 10% of the final grade.) Each project will require you to answer questions and write programs that use or implement some of the data structures we discuss in class.
Assignments will appear in the Assignments page of the BlackBoard site.
Homework Projects:
Homework projects will be handed out in class and posted on the course page on BlackBoard. Unless otherwise specified, homework is due at the beginning of class. (Depending on the assignment, some homeworks may be submitted via Blackboard and some may be submitted as a paper copy in class.)
Late homeworks will be penalized according to this policy:
-- after class on the day that the HW is due: 20% penalty.
-- after class on the following class day: 35% penalty.
-- after class one week after the HW was due: 50% penalty.
If homework will be submitted more than two weeks late, then you should discuss the circumstances ahead of time with the instructor. Such homework will be accepted on a case-by-case basis. After the answers to a homework assignment have been discussed in class or handed out, then homeworks can no longer be accepted.
Academic Integrity Policy:
There is no group work in this class. It is fine to discuss course topics with other students and to discuss assignments in general terms with other students. However, you should think about and work on all assignments yourself, and you should write your own solutions to any problems which are assigned. You should not search the web for computer code which you can copy and submit for your homework assignments. In general, the instructor will have also performed an extensive search for code on the web that could be similar to the assignments you will be asked to write, and it's pretty easy to see past surface modifications to detect when code has been adapted from another source. If asked, you should be able to explain any code which you submit. Since assignments are a much smaller portion of your total grade than the exams, it is in your interest to do the assignments yourself (and to understand them) since these skills will be tested during the in-class exams.
At the bottom of each assignment, I'd like you to include a section entitled: "Resources that Helped Me." If you had a good conversation with someone in the class, you had a good discussion with me during office hours, or you found a useful website that helped you understand a concept (without copying code from the website), then you can list these resources at the end of your assignment. I'd like to know about information sources that you found helpful (they might also be good to share with other students in the class). If you only used the textbook and the in-class lectures when you did your assignment, then you don't need to include a "Resources that Helped Me" section on your assignment.
Any evidence of cheating, copying, or obtaining answers from the Internet or other students will be passed on to the appropriate disciplinary committee on the campus.
Important Note about Programming Assignments:
For any homework assignment in which I ask you to write Java code, you should do the following steps:
1. Write the Java code and make sure that it compiles. You should include helpful comments in the code that explain what it is doing. If you submit a method that does lots of calculations or assignments without explaining the underlying strategy of the method, then you won’t get full credit. (In other words, it should be easy to understand what your code is doing by reading it and its comments.) If it takes a lot of effort to understand your code because it is poorly commented, then this will reflect poorly on the final grade.
2. Write a method that tests the Java code (perhaps by adding a “main” method to the class). Usually I’ll give you a sample input that you should try to run your code on or I will describe how to test your code as part of the assignment.
3. Submit a print-out of what happens when you execute your code on some sample input(s) in the “test code” above. This has to be an actual copy/paste from the output screen.
4. Submit a print-out of all of your Java code. If you used some code that came with the textbook, that is fine (I’ll tell you when there are classes you can use), but I’d like you to indicate what parts of the code were newly written by you. (You could indicate this inside your programming comments or by highlighting the new code with a marker after you print it out.)
You should not submit Java code that doesn’t compile or which you don’t show a print-out of its execution. It’s part of your assignment to prove to me that your code works… (And to make sure your code is understandable by including helpful comments.) You have to do this by showing a print-out of the code correctly performing the required task. You also have to make sure that any Java code that you submit actually compiles – or else you should include a written explanation with your assignment that says that you could not get your code to compile. If asked, you should be able to e-mail me any Java code you’ve written so that I can run it on the sample inputs.
The textbook for the course is your primary resource for background information about the important data structures we will be learning about. You may also find it useful to consult websites about the Java programming language or about the BlackBoard course website.
Logging-In to the BlackBoard Online Course System:
http://qcpages.qc.edu/edtech/BlackBoard/loggingOn.html
Information about Using BlackBoard:
http://qcpages.qc.edu/edtech/BlackBoard/students.html
SUN Java Tutorials Websites:
http://java.sun.com/javase/reference/tutorials.jsp
http://java.sun.com/docs/books/tutorial/