| |
CSE 250 - Spring 2008 - Data Structures |
|
|
Syllabus
|
|
Name |
Office |
Phone 645-3180 |
Email |
Web |
|
Adrienne Decker |
130 |
Ext. 161 |
adrienne@cse.buffalo.edu |
Course Information
Credit hours: 4
Course Website: http://www.cse.buffalo.edu/faculty/adrienne/SP2008/cse250
Lecture Times:
Section
A - Monday, Wednesday, Friday 9:00
– 9:50 220 NSC
Recitation Times:
A1 Tuesday 3:00 – 3:50 210 NSC
A2 Thursday 1:00 – 1:50 214 Norton
A3 Thursday 11:00 – 11:50 146 Park
Course Description
This course provides a
rigorous analysis of the design, implementation and properties of advanced data
structures. Topics include order notation and time-space analysis and tradeoffs
in list, tree and graph algorithms, and hashing. The course will survey library
implementations of basic data structures in a high-level language. Advanced
data structure implementations will be studied in detail. The importance of
choosing appropriate data structures when solving a problem will be illustrated
by programming projects in C++, a high-level object-oriented language different
from the language of CSE115-CSE116. There is no expectation that you have C++
programming background prior to this course, though I will assume that you are
familiar with basic object-oriented concepts.
This course is a prerequisite
for CSE 305 Introduction to Programming Languages, CSE 396 Introduction to the
Theory of Computation, CSE 331 Introduction to Algorithm Analysis and Design,
CSE 474 Introduction to Machine Learning and CSE 480 Computer Graphics.
This course adheres to recommendations made in the ACM's
CC2001 Computer Science Volume curriculum document for a third semester data
structures course. It covers topics from the following knowledge units: DS5
Graphs and Trees, PF3 Fundamental data structures, AL3 Fundamental computing
algorithms. It reviews and reiterates
concepts from the following knowledge units (due to the change of languages) PF1
Fundamental programming constructs, AL1 Basic algorithm analysis, PL4
Declarations and types, PL5 Abstraction mechanisms, PL6 Object-oriented programming.
Schedule of Topics
The following is a tentative
schedule of topics. A more detailed
schedule is maintained on the course website and should be checked often for
updates.
3 weeks - C++ (syntax review,
OO review, templates, namespaces, pointers, make files, debuggers)
2 weeks - Asymptotic
notations, properties
1 week - Lists, stacks,
queues, deques (STL and analysis)
3 weeks - Trees (e.g. AVL,
Red-black, Splay, 2-3, trie)
2 weeks - Priority queues
(e.g. binomial, skew, leftist)
2 weeks - Hash tables/hashing
1 week - Graphs
(representations, traversals)
Course Objectives
At the end of this course you
should be able to perform basic analysis of algorithms, understand how various
data structures and algorithms function, be able to implement them in a
high-level language, and be able to pick an appropriate data structure or
algorithm for a given task.
ABET Program Objectives
Our computer engineering program is accredited by
ABET. This course is required of all
computer engineering students and has a significant relationship with the
following program objectives for computer engineering:
(a) An ability to apply
knowledge of mathematics, probability and statistics, computer science and
electrical engineering as
it applies to the fields of computer software and hardware.
(b)
An ability to conduct experiments, as well as to organize, analyze, and
interpret data.
(f)
An understanding of professional, legal, and ethical issues and
responsibilities as it pertains to
computer engineering.
This course has a strong
relationship with the following program objectives for computer engineering:
(e) An ability to identify, formulate, and
solve hardware and software computer engineering
problems
using sound computer engineering principles.
(k) An ability to use the techniques, skills,
and modern hardware and software engineering tools
necessary
for computer engineering practice.
Prerequisites
You must have passed both CSE
116 and CSE 191 with a grade of C- or better in order to take CSE 250. Your
prerequisites will be checked. If you do not have the required prerequisites,
you will be removed from the course.
Textbooks and Materials
The required textbooks for
this course are:
·
Mark Allen Weiss.
2006. Data Structures and Algorithm Analysis in C++ (Third Edition), Addison Wesley. (ISBN: 032144146X)
·
Mark Allen Weiss. 2004. C++ for Java Programmers,
Prentice Hall. (ISBN: 013919424X)
The above two titles are available in a bundled
package from the bookstore at a reduced price, perhaps not better than prices
you can find online, though.
This book is recommended as a
reference for the C++ language and is also available at the bookstore:
Though you may find the
following books useful, they are not required and have not been ordered for the
bookstore:
§
§
Bjarne
Stroustrup. 2000. The C++ Programming Language: Special Edition (Third edition),
Addison-Wesley.
Additional reading material
may be assigned during the course, and will be announced in lecture.
Computing Resources
You will be provided with a
CSE undergraduate computing account. You may use the undergraduate lab
facilities in
The name of the server that
you will be connecting to in the lab will be yeager.cse.buffalo.edu. You have the ability to connect to yeager.cse.buffalo.edu
remotely from other sites, on or off campus.
You are expected to become
proficient at using the machines in the lab, the Unix system, the C++ compiler,
and whatever other software development tools the course requires you to use.
It is your responsibility to ensure that any programs you write for this course
compile using the C++ compilers installed on the department's machines.
You are also required to read
mail sent to your CSE e-mail account. Any e-mail communication that you send
regarding this course must be sent from your CSE e-mail account or your UB
e-mail account. Under no circumstances will e-mail from non-UB accounts be
acknowledged or answered. You must include an informative subject line in all
e-mail, and include your full name in any e-mail correspondence.
All e-mail that we send in
reply to your e-mail will be sent to the address from which you sent your
e-mail. Our feedback on materials you hand in electronically will be sent to
your CSE e-mail account only. Since you may request re-grades of work only
within a set period from the time that the feedback was provided to you, it is
in your best interest to read your CSE e-mail account on a daily basis.
Course Organization
The course has both a lecture
component and a recitation component. Each component plays a role in helping
you achieve the objectives of the course. If you do not participate fully in
both you should not expect to do well in the course.
Lectures
The conceptual and
theoretical course content will be delivered primarily in the lectures,
complemented by readings from the text books. You must review readings prior to
attending a lecture, and you are expected to review the readings again, along
with any notes you took, after the lecture.
Some of the topics will be
difficult. It is therefore absolutely essential that you ask questions whenever
something is said which you do not understand.
You are expected to attend
all lectures. If you are unable to attend a lecture because of sickness or
similar reasons, make sure you get the notes from a classmate. If you are out
of class for an extended period of time because of sickness, notify your
instructor as soon as possible, and see your instructor immediately upon your
return in order to determine how to catch up. If you have missed a significant
portion of the semester due to illness, it is recommended that you resign from
the course.
Recitations
The recitations are an
integral part of the course. They will cover C++ programming in detail.
Attendance in recitation will therefore be critical for your ability to
complete the programming projects.
The recitations may review
and extend lecture material and are also an excellent forum for asking more
individual questions about the course material than can typically be addressed
in lecture. Some material needed to do the programming projects will be covered
only in recitation. Any homework will be
collected and returned in recitation. Quizzes are returned in recitation.
Attendance in recitation is expected.
Recitations do not meet in
the first week of classes.
Time outside of class
Office hours
Office hours offer you the
opportunity to ask more individual questions about the course material than can
typically be addressed in lecture. Both the instructor and the teaching
assistants have scheduled office hours. Office hours are held on a first-come
first-served drop-in basis. No appointment is necessary to attend office hours.
Be aware that office hours become increasingly busy the closer it is to a project
deadline. Plan your use of office hours accordingly. Individual appointments
may be arranged, if needed, as schedules allow.
Study time
In this course, as in any
course, you are expected to put in additional time beyond the scheduled class times.
Professors generally expect that for each credit hour a class carries a typical
student will put in 2 - 3 hours of time each week outside of class. Since this
is a 4 credit course that translates into 8 - 12 hours of time outside of
lecture and recitation times, each week. During this time you should review
your lecture notes, attend office hours as needed, get hands-on practice
applying the concepts and theoretical constructs discussed in class, and
possibly arrange to meet in small groups to study or review the concepts from
class. As a rough guide, you should expect to spend at least the following time
working on this course, each week:
o
Lectures: 3 hours
o
Lab time: 2 hours
o
Programming
assignments: 4 hours
o
Individual study:
4 hours
Course evaluation
The following indicates the
grade breakdown which will be used in assigning grades in the course. The right
is reserved to make small adjustments to the breakdown if it is necessary.
Exam component (45% of
final course grade)
There will be one midterm
examination and one final examination at the end of the term. The midterm exam
will be held on March 3rd. The final examination will be given on a date to be specified
by the University. Do not make
travel plans for times during the examination period until the final
examination schedule has been posted.
If you miss an examination
because of sickness or similar reasons, visit a physician and obtain a note
detailing the period during which you were medically incapable of taking the
exam. Notify your instructor immediately via e-mail or telephone (voice mail)
if you are going to miss an exam, before the exam takes place unless medically
impossible. See your instructor as soon as you return to class.
If you miss an examination
without a valid excuse, you will receive a zero grade for that examination.
No make-up examinations will
be available without a valid excuse. You
must bring a valid form of picture ID with you to each examination (a UB Card
will suffice).
There are two options for
calculating your score for the exam component of the course. Under the first
option the midterm exam counts for 20% of your grade, while the final exam
counts for 25%. Under the second option
the final exam counts for 45% of your grade. The option which gives you the highest
score in the course will be used automatically.
You must attempt the midterm
exam in order for the final-exam only option to be available to you.
If you do not take the
midterm exam, you cannot make use of the final-exam only option.
The motivation for having two
grading options available is to ensure that you are not penalized if you had a
rough start in the course, but managed to do really well on the final exam. If
you do poorly on the midterm exam, you can still do well in the course by
demonstrating that you have learned the material on the final exam. Of course,
if you do poorly on the midterm exam, this means you are playing without a
safety net.
The following table
summarizes the grading of the exam component of the course:
|
|
Option #1 |
Option #2 |
|
In-class exams |
20% |
0% |
|
Final Exam (Cumulative) |
25% |
45% |
A necessary but not sufficient
condition for receiving a passing grade in the course is having a passing exam
component grade.
Homework component
(10% of final course grade)
There will be regular
homework assignments throughout the semester. These are due in and handed back
in recitation. Late submissions of homework assignments will not be accepted under any circumstances. Your lowest homework
grade will be dropped from final course grade calculations. All homeworks will
count equally.
Project component (45%
of final course grade)
There will be regular
programming projects. The purpose of these is to reinforce and deepen your understanding
of the broader concepts discussed in class through application of those
concepts to concrete problems. The programming projects are designed to give
you hands-on experience analyzing problems, developing solutions to them, and
implementing these solutions in C++. The programming projects also serve to
give you feedback on your understanding of the material. I expect that we will have three-four
programming projects, weighted equally. It
is your responsibility to ensure that any programs you write for this course
compile using the C++ compilers installed on the department's machines.
Submissions which do not compile will not be graded.
You must have a passing
average on the lab component of the course in order to pass the class.
Early policy for
programming project submissions
Any programming project
submission which occurs before the due date is considered early, and will have
a 2.5% bonus (of the maximum score obtainable) added per full day early (24
hours), up to a maximum of 10%.
Late policy for
programming project submissions
Any programming project
submission which occurs after the due date is considered late, and will have a
25% penalty (of the maximum score obtainable) imposed per day (24 hours), or
portion thereof, late. A submission more than three days late (i.e. four or
more days late) will therefore be awarded no points.
When calculating final course
grades, I will “forgive" two days of programming project late penalties. I will “forgive" the two late penalties
which affect your grade the most. For example, if all of your submissions
except one are on time, and the late submissions is two days late, it counts
for full credit. As another example, if
the late submissions is three days late, but all your other submissions are on time,
the late submission counts as one day late. Unused late days do not benefit
you.
Re-grading
If you have a question about
the grading of any piece of work, first consult with the teaching assistant who
graded your work. If you cannot resolve your questions with the teaching
assistant, you should consult with the instructor of the course.
Any questions about the
grading of a piece of work must be raised within one week of the date that the
work was returned by the teaching assistant or the instructor. In other words,
if you do not pick up your work in a timely fashion, you may forfeit your right
to question the grading of your work.
Incomplete (I) grades
We will follow the UB
Undergraduate Catalog Statement on Incomplete Grades, found in the Undergraduate
Catalog.
Generally, incomplete (“I”)
grades are not given. However, very rarely, circumstances truly beyond a student's
control prevents him or her from completing work in the course. In such cases
the instructor can give a grade of “I”. The student will be given instructions
and a deadline for completing the work, usually no more than 30 days past the
end of the semester. University and department policy dictate that “I” grades
can be given only if the following conditions are met:
o
An Incomplete
will only be given for missing a small part of the course.
o
An Incomplete
will only be given when the student misses work due to circumstances beyond his/her
control.
o
An Incomplete
will only be given when the student is passing the course except for the missed
material.
o
An Incomplete is
to be made up with the original course instructor within the time specified by the
appropriate University regulation (see appropriate document above), and usually
within the following semester.
o
An Incomplete
will not be given to allow the student to informally retake the entire course,
and have that grade count as the grade of the original course.
Incompletes can not be given
as a shelter from poor grades. It is your responsibility to make a timely
resignation from the course if you are doing poorly for any reason. The last
day to resign the course is Friday, March 28th.
Letter grades
The following table indicates
the number to letter grade mapping I will use to assign final grades at the end
of the course. The Grade points column is included for your convenience only,
and is not official information. The official mapping can be found in the
Undergraduate Catalog.
|
Percentage
score |
Letter
grade |
Grade
points |
|
90-100 |
A |
4.0 |
|
85-89 |
A- |
3.67 |
|
80-84 |
B+ |
3.33 |
|
75-79 |
B |
3.0 |
|
70-74 |
B- |
2.67 |
|
65-69 |
C+ |
2.33 |
|
60-64 |
C |
2.0 |
|
55-59 |
C- |
1.67 |
|
50-54 |
D |
1.0 |
|
0-49 |
F |
0.0 |
General Notes
If you don't understand
something covered in class, ask about it right away. The only silly question is
the one which is not asked. If you get a poor mark on an assignment, quiz, or
exam, find out why right away. Don't wait a month before asking. The instructor
and teaching assistants are available to answer your questions. Don't be afraid
to ask questions, or to approach the instructor or T.A. in class, during office
hours, or through e-mail.
This course is intended to be
hard work, but it is also intended to be fun. Play with the computer, and have
fun with the neat and elegant programming ideas covered in this course. We
think computer science is interesting and exciting, and we want to convince you
of this. Work hard, but have fun!
Disabilities
If you have a diagnosed
disability (physical, learning, or psychological) that will make it difficult for
you to carry out the course work as outlined, or that requires accommodations
such as recruiting note-takers, readers, or extended time on exams or
assignments, you must consult with the Office of Disability Services (25 Capen
Hall, Tel: 645-2608, TTY: 645-2616, Fax: 645-3116,
http://www.student-affairs.buffalo.edu/ods/).
You must advise your
instructor during the first two weeks of the course so that we may review
possible arrangements for reasonable accommodations.
Your attention is called to
the
Distractions in the Classroom - Behavioral
Expectations
The following is the text of
a policy adopted by the Faculty Senate. You are expected to know and adhere to
this policy.
OBSTRUCTION OR DISRUPTION IN THE CLASSROOM –
To prevent and respond to
distracting behavior faculty should clarify standards for the conduct of class,
either in the syllabus, or by referencing the expectations cited in the Student
Conduct Regulations. Classroom "etiquette" expectations should
include:
Academic Integrity
Source:
http://www.cse.buffalo.edu/academics-academic integrity.shtml
The academic degrees and the
research findings produced by our Department are worth no more than the
integrity of the process by which they are gained. If we do not maintain
reliably high standards of ethics and integrity in our work and our
relationships, we have nothing of value to offer one another or to offer the
larger community outside this Department, whether potential employers or fellow
scholars.
For this reason, the
principles of Academic Integrity have priority over every other consideration
in every aspect of our departmental life, and we will defend these principles
vigorously. It is essential that every student be fully aware of these
principles, what the procedures are by which possible violations are
investigated and adjudicated, and what the punishments for these violations
are. Wherever they are suspected, potential violations will be investigated and
determinations of fact sought. In short, breaches of Academic Integrity will
not be tolerated.
Departmental Statement on Academic Integrity in Coding Assignments and Projects
The following statement
further describes the specific application of these general principles to a common
context in the CSE Department environment, the production of source code for
project and homework assignments. It should be thoroughly understood before
undertaking any cooperative activities or using any other sources in such
contexts.
All academic work must be
your own. Plagiarism, defined as copying or receiving materials from a source
or sources and submitting this material as one's own without acknowledging the
particular debts to the source (quotations, paraphrases, basic ideas), or
otherwise representing the work of another as one's own, is never allowed.
Collaboration, usually evidenced by unjustifiable similarity, is never permitted
in individual assignments. Any submitted academic work may be subject to
screening by software programs designed to detect evidence of plagiarism or
collaboration.
It is your responsibility to
maintain the security of your computer accounts and your written work. Do not
share passwords with anyone, nor write your password down where it may be seen
by others. Do not change permissions to allow others to read your course
directories and _les. Do not walk away from a workstation without logging out.
These are your responsibilities. In groups that collaborate inappropriately, it
may be impossible to determine who has offered work to others in the group, who
has received work, and who may have inadvertently made their work available to
the others by failure to maintain adequate personal security In such cases, all
will be held equally liable.
These policies and interpretations
may be augmented by individual instructors for their courses. Always check the
handouts and web pages of your course and section for additional guidelines.
Departmental and Course
Policy on Violations of Academic Integrity
If, after following the
procedures required by the University for investigation of suspected breaches of
academic integrity, a student is found guilty, the policy of the department of
Computer Science & Engineering is that the student minimally receive a
grade of F in the course.
University at
Department of Computer Science & Engineering
I, ____________________________________________(PRINT
name), acknowledge that I have read and understood the syllabus for this
course, CSE 250 Data Structures.
I also acknowledge that I
understand the definition of academic integrity as outlined in the syllabus,
and that I will minimally receive a grade of F in the course if I am found to
have breached academic integrity.
I also understand that I am
required to have successfully completed all of the listed prerequisites for
this course with a minimum grade of C-. I understand that if I do not meet the
prerequisites that I may be dropped from the course by the department.
Signature: ________________________________________________ Date: _____________
Announcements | Assignments | Meetings | People | Resources | Schedule | Syllabus |
Page Maintained by: Adrienne Decker |