CSI 3334: Data structures, Spring 2012
Overview
Data structures and the algorithms that operate on them are the keys to making efficient software. They are also very interesting. This course will cover data structures in a way that exercises your problem-solving skills. These problem-solving skills are what you will need to be a successful programmer, scientist, engineer, or mathematician.
This course covers:
- fundamental data structures: arrays, lists, queues, stacks, heaps, trees, and graphs
- appropriateness of different data structures for different tasks
- standard algorithms to operate on data structures, including searching and sorting
- analysis of algorithms for time and space complexity
- data abstraction (separation of interface and implementation)
- C++ implementation
This is a difficult course. My recommendation is to attend lectures, study hard, start projects early, and seek help from the professor when you need it.
Practical information
Lectures are from 11:15 AM to 12:05 PM in Rogers 210 on Mondays, Wednesdays, and Fridays. You may use the general labs on the first floor of Rogers, though there is no lab component of the course.
My office is in the Rogers Engineering and Computer Science building, and office hours are to be determined. I am glad to talk to students during and outside of office hours. If you can't come during my office hours, please make an appointment for another time.
The TA for this course is Lyles Kirk.
Schedule
Here is a schedule of the material we will cover:
Week | Dates | Topics | Reading | Monday | Wednesday | Friday |
---|---|---|---|---|---|---|
1 | Jan 09-13 | Overview, C++ review | 1.1-1.6 | Project 0 assigned | Homework 0 assigned | Project 1 assigned |
2 | Jan 16-20 | Algorithm analysis | 2 | MLK Jr. Day | ||
3 | Jan 23-27 | Algorithm analysis | Homework 1 assigned | Project 2 assigned | ||
4 | Jan 30-Feb 03 | ADTs, lists, stacks, queues | 3.1-3.3, 3.6, 3.7 | |||
5 | Feb 06-10 | Trees | 4 | Homework 2 assigned | Project 3 assigned | |
6 | Feb 13-17 | Trees | ||||
7 | Feb 20-24 | Heaps | 6 | Homework 3 assigned | Project 4 assigned | |
8 | Feb 27-Mar 02 | Heaps | Midterm exam | |||
9 | Mar 05-09 | Hashing | 5 | Homework 4 assigned | Project 5 assigned | |
10 | Mar 12-16 | Spring Break | Spring Break | Spring Break | Spring Break | Spring Break |
11 | Mar 19-23 | Hashing | ||||
12 | Mar 26-30 | Sorting | 7 (skip 7.4) | Homework 5 assigned | Project 6 assigned | |
13 | Apr 02-06 | Sorting, Graphs | 9.1-9.5 | Easter Break | ||
14 | Apr 09-13 | Graphs | Easter Break | |||
15 | Apr 16-20 | Graphs | ||||
16 | Apr 23-27 | Disjoint set, Algorithm design | 8, 10 | Last day of class | ||
17 | Apr 30-May 04 | Study Day | Study Day | |||
18 | May 07-11 | Final (2:00) |
The final exam will be Monday, May 7 @ 2:00. The latest university finals information is available here.
Textbooks & resources
Required text: we will be using Mark Weiss' textbook Data Structures and Algorithm Analysis in C++ (3rd Edition). An older edition might be okay, but you are responsible in case there are differences between the editions. You can purchase this book from the Baylor bookstore or amazon, among other places.
Further online resources:
- We will use Blackboard for keeping records of assignment grades.
- Bruce Eckel, Thinking in C++ (2nd edition)
- the Standard Template Library (STL) reference
- Project submission guidelines and coding style guidelines for this course.
Grading
Grades will be assigned based on this breakdown:
- midterm exam: 20%
- final exam: 25%
- projects: 35% (including 5% for milestones)
- homework: 20%
Important: Each project not completed by the end of the semester will result in a drop of one letter grade. For example, if you would have received a 'B', but you did not complete two of the projects, then your letter grade will be a 'D'.
Different projects and assignments may have different point values. In-class exams are closed-book. The final will be comprehensive.
Homework is due at the beginning of class; homework turned in after it has been collected but before the end of class will receive a 20% penalty. Homework will not be accepted after class on the due date.
Final letter grades will be assigned at the discretion of the
instructor, but here is a minimum guideline for letter grades:
A: 90-100, B+: 88-89, B: 80-87, C+: 78-79, C: 70-77, D: 60-69, F:
0-59
Policies
- This website contains the official course information. Please check it regularly for updates.
- All work in this course is strictly individual, unless the instructor explicitly states otherwise. While discussion of course material is encouraged, collaboration on assignments is not allowed. Collaboration includes (but is not limited to) discussing with anyone (other than the professor) anything that is specific to completing an assignment. You are encouraged to discuss the course material with the professor, preferably in office hours, and also by email.
- Exams may be made up with prior arrangement (made at least one class before to the exam) or due to illness, with a note from a health care professional.
- Bring any grading correction requests to your professor's attention within 2 weeks of receiving the grade or before the end of the semester, whichever comes first.
- Class should be a place you are glad to go. After all, you signed up for the class, and we get to talk about data structures! To incent you further, there will be a bonus of 3% added to the final grade for any student who has "pristine" attendance — that is, no absences (excused or unexcused), no tardies.
- In order to facilitate keeping attendance, please choose a seat that you will use for the rest of the course.
Academic honesty
I take academic honesty very seriously. Many studies, including one by Sheilah Maramark and Mindi Barth Maline have suggested that "some students cheat because of ignorance, uncertainty, or confusion regarding what behaviors constitute dishonesty" (Maramark and Maline, Issues in Education: Academic Dishonesty Among College Students, U.S. Department of Education, Office of Research, August 1993, page 5). In an effort to reduce misunderstandings, here is a minimal list of activities that will be considered cheating in this class:
- Using a source other than the course textbook, the course website, or your professor to obtain credit for any assignment, project, or exam.
- Copying another student's work. Simply looking over someone else's source code is copying.
- Providing your work for another student to copy.
- Collaboration on any assignment, unless the work is explicitly given as collaborative work. Any discussion of an assignment or project is considered collaboration.
- Using notes or books during any exam.
- Giving another student answers during an exam.
- Reviewing a stolen copy of an exam.
- Plagiarism.
- Studying tests or using assignments from previous semesters.
- Providing someone with tests or assignments from previous semesters.
- Taking an exam for someone else.
- Turning in someone else's work as your own work.
- Studying a copy of an exam prior to taking a make-up exam.
- Providing a copy of an exam to someone who is going to take a make-up exam.
- Giving test questions to students in another class.
- Reviewing previous copies of the instructor's tests without permission from the instructor.
Copyright © 2012 Adam Sealey, based
largely on a syllabus by Greg Hamerly .
Computer
Science Department
Baylor
University