Data Structures II
Syllabus
Version of August 1st, 2019
Course meeting details
Our class meets every Thursday from September 12th to November 14th, 5:45pm to 9pm, with a 15-minute break at 7:15. At the moment the class is listed as meeting in room 1514 of the Lewis building (25 E. Jackson) but please check that shortly before the first class as room assignments sometimes change at the last minute.
Course description
From the course catalog: "This is the second course on data structures in Java for graduate students. The course covers trees, heaps, associative arrays, hash tables, tries, and data structures for representing graphs. The implementation of the basic operations on each data structure are discussed and analyzed in terms of their efficiency. Prerequisite: CSC 402 (Data Structures I)"
More specifically, this is a third programming course, following the introductory course, CSC 401, and the first data structures course, CSC 402.
Course web site
Except for the textbooks, all course materials will be available through DePaul's D2L web site.
Textbooks
There is one required textbook that comes in two forms. The book's title is Algorithms, 4th edition, by Robert Sedgewick and Kevin Wayne (Addison-Wesley, 2011). There is a version with videos (ISBN 978-0134384689) and one without (ISBN 978-0321573513). Many of you already have one of these as it's the same text as used in CSC 402. There is a good companion site. An on-line version is also available through Safari and that can be accessed through DePaul's library site.
There are also two free textbooks, available on-line, that you should consult. They are:
- Think Java: How to Think Like a Computer Scientist, by Allen B Downey;.
- Java for Python Programmers, by Brad Miller.
Course learning outcomes
Upon successful completion of this course, a student will be able to:
- write programs of medium complexity using basic object-oriented techniques
- implement repetitive algorithms using both iteration (loops) and recursion
- use a debugger to set breakpoints and to inspect variable values during execution
- test a program at the module (method) level
- analyze a simple program to detemine its running time in terms of the input size
- implement symbol tables using binary trees (balanced and unbalanced) and hash tables
- implement simple algorithms for processing graphs
- explain how string compression works
Assignments and grading
There will be up to eight assignments, for the nost part asking you to write code but there will also be some questions requiring written answers and diagrams. These will total 300 points. The take home final exam will be made available during the last class and will be due one week later (that is, 11:59pm on Thursday, November 21st). It will be worth 75 points.
An assignment may consist of several tasks and each task will have its own submission slot in D2L. Late submissions will lose 10% of the score for every 12 hours after the deadline, which means that they will be worth 0 points no matter what after five days. Most of the tasks will be to write programs. Programs that do not compile will receive 0 points. The final exam will be similar to the assignments in format. It must be submitted by the deadline.
Letter grades will be assigned as follows:
| Letter | Percentage range |
|---|---|
| A | 95-100 |
| A- | 90 - <95 |
| B+ | 87 - <90 |
| B | 83 - <87 |
| B- | 80 - <83 |
| C+ | 77 - <80 |
| C | 73 - <77 |
| C- | 70 - <73 |
| D+ | 65 - <70 |
| D | 60 - <65 |
| F | <60 |
Schedule of topics
| Week (date) | Topic | Textbook Sections |
|---|---|---|
| 1 (9/12) | Symbol tables, binary search trees | 3.1, 3.2 |
| 2 (9/19) | Binary search trees, balanced BSTs (AVL trees) | 3.2, 3.3 |
| 3 (9/26) | Balanced BSTs: AVL trees, 2-3 trees, Red-black trees | 3.3 |
| 4 (10/3) | Balanced BSTs, Hash tables | 3.3, 3.4 |
| 5 (10/10) | Hash tables | 3.4 |
| 6 (10/17) | Undirected graphs | 4.1 |
| 7 (10/24) | Undirected graphs, directed graphs | 4.1, 4.2 |
| 8 (10/31) | Directed graphs | 4.2 |
| 9 (11/7) | String sorts, Tries | 5.1, 5.2 |
| 10 (11/14) | Data compression, course review | 5.5 |
Dates and deadlines
The dates specific to our class are in bold.
- Wednesday, September 11th: Start of fall quarter
- Thursday, September 12th: Our first class
- Tuesday, September 24th: Last day to drop any class with no penalty
- Tuesday, October 29th: Last day to withdraw
- Thursday, November 14th: Our last class
- Tuesday, November 19th: End of fall quarter classes
- Wednesday, November 20th: Start of fall quarter finals week
- Thursday, November 21st: Take-home final exam due
- Tuesday, November 26th: End of fall quarter finals week
Participation policy
For students in the in-class section, attending every class is required. Students in the distance learning section must send me an email each week when they've finished viewing the class recording.
Academic Integrity Policy
This course will be subject to the academic integrity policy passed by our faculty. More information can be found at http://academicintegrity.depaul.edu/. I strongly recommend that you read this! It explains both your rights and your responsibilities as a student on matters of academic integrity.
Communication
All communication will be done in one of three ways:
- Announcements in class. You are responsible for anything and everything I say in class.
- Email from me. You can send email to me at jrogers@depaul.edu.
- Announcements on the D2L web site.
When you send me email, two requirements:
- Please have the subject line begin with
CSC 403: - Make sure your full name appears somewhere in the message.
Office location and hours
My office is room 747 in the CDM building, 243 S. Wabash. My office hours can be found through BlueStar, which can be accessed through your Campus Connect account. My phone number is 312-362-8334 (dial 2-8334 from the 7th floor lobby phone). If you call and do not leave a voicemail, I will not try to contact you. If you want a response, you must leave a message!
Plagiarism
The university and school policy on plagiarism can be summarized as follows: Students in this course should be aware of the strong sanctions that can be imposed against someone guilty of plagiarism. If proven, a charge of plagiarism could result in an automatic F in the course and possible expulsion. The strongest of sanctions will be imposed on anyone who submits as his/her own work any assignment which has been prepared by someone else. If you have any questions or doubts about what plagiarism entails or how to properly acknowledge source materials consult the instructor.
Incomplete
An incomplete grade is given only for an exceptional reason such as, for example, a death in the family or a serious illness. Any such reason must be documented. Any incomplete request must be made at least two weeks before the final and approved by the Dean of the College of Computing and Digital Media. Any consequences resulting from a poor grade for the course will not be considered as valid reasons for such a request.
Resources for Students with Disabilities
Students who feel they may need an accommodation based on the impact of a disability should contact the instructor privately to discuss their specific needs. All discussions will remain confidential.
To ensure that you receive the most appropriate accommodation based on your needs, contact the instructor as early as possible in the quarter (preferably within the first week of class) and make sure that you have contacted either the PLuS Program, for Learning Disabilities and/or AD/HD, or the Office for Students with Disabilities, for all other disabilities, at:
Student Center, LPC, Suite #370
Phone number: (773) 325-1677
Fax: (773) 325-3720
TTY: (773) 325-7296