CSC 301/Data Structures II
Syllabus
Version of August 8th, 2021
Course meeting details
As of the date of this syllabus, class will meet as usual. Section 402 will meet in person in CDM 200 from 11:50am to 1:20pm on Tuesdays and Thursdays. Our first class is Thursday, September 9th. Section 411 will view the class recording through COL. Students in section 402 should review DePaul's COVID-19 policies just prior to our first class. Students in section 411 should not attend class.
Course description
From the course catalog: "This is the second course in a two-course sequence on data structures using Java. The course focuses mainly on the following data structures, their analysis, and their applications: trees (search trees, balanced search trees), heaps, associative arrays, hash tables, 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. The applications discussed highlight and exploit the unique characteristics of the different data structures, and emphasize problem solving and recursive thinking. Prerequisite(s): CSC 300 (Data Structures I)"
More specifically, this is a fourth programming course, following the introductory courses, CSC 241 and CSC 242, and the first data structures course, CSC 300. I expect that you've learned enough Java to be able to write a program of medium complexity. I will make clear what I mean by that in the first assignment.
Course learning outcomes
Upon successful completion of this course, a student will be able to:
- write programs of medium complexity from scratch ("blank screen programming") that uses 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
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 300. There is a good companion site. An electronic version is available through DePaul's library. On their site, search for "Algorithms". One of the hits will list "Sedgewick" as the author. Follow that.
There are also two free textbooks, available on-line, that you should consult for Java. They are:
- Think Java: How to Think Like a Computer Scientist, by Allen B Downey;.
- Java for Python Programmers, by Brad Miller.
Grading
There will be numerous programming assignments. One grading criterion that will always be in effect is that a program that does not compile, that crashes, or that has an infinite loop will receive 0 points. Partial credit is possible but only if the program runs to termination and produces reasonably correct output. There will also be a final exam. Its form and timing will be announced during the quarter. The assignments will be worth a total of 75% of the final grade, with the final exam making up the other 25%. There will not be a midterm exam.
Final course grades will be assigned according to the following table.
| 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 |
Late assignment policy
An assignment loses 20% of the total score each day or part of a day it's late. This means that a 0 is automatically assigned five days after an unsubmitted assignment is due.
Topics and reading
Remember that during fall quarter, the class week begins on Wednesday and ends on the following Tuesday. This means that our course weeks begin with the Thursday class. For example, the week 1 classes are on Thursday, September 9th, and Tuesday, September 14th. This table tells you what reading you should do to prepare for each week.
| Week | Topic | Sections |
|---|---|---|
| 1 | Symbol tables, binary search trees | 3.1, 3.2 |
| 2 | Binary search trees, balanced BSTs (AVL trees) | 3.2, 3.3 |
| 3 | Balanced BSTs: AVL trees, 2-3 trees, Red-black trees | 3.3 |
| 4 | Balanced BSTs, Hash tables | 3.3, 3.4 |
| 5 | Hash tables | 3.4 |
| 6 | Undirected graphs | 4.1 |
| 7 | Undirected graphs, directed graphs | 4.1, 4.2 |
| 8 | Directed graphs | 4.2 |
| 9 | String sorts, Tries | 5.1, 5.2 |
| 10 | Data compression, course review | 5.5 |
Participation policy
Students in the in-class section are expected to attend. Missing more than four classes may result in the final letter grade being reduced. Students in the COL section are expected to view the recording within 72 hours of its posting.
Academic Integrity Policy
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.
Plagiarism is a constant problem in this course. Every course at DePaul is 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, especially the part about submitting other people's work as your own. The policy explains both your rights and your responsibilities as a student on matters of academic integrity.
Just to be clear: Posting a programming assignment on a site like Chegg.com is asking someone else to write your code. In which case, you would be submitting someone else's code as your own and that's plagiarism.
Communication
All communication will be done in one of three ways:
- Announcements in class. You are responsible for anything and everything I say when teaching.
- Email from me. You can send email to me at jrogers@depaul.edu.
- Announcements on the D2L web site.
Office hours
Please see BlueStar for my office hours, which will be held on Zoom.
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