CSC301/CSC403: Syllabus

We will use Piazza for online discussion.

You should have received an invitation to join the class. If you have not, please contact me.

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.

• Basic OO programming techniques
• Use of debuggers
• Use of testing
• Understanding correctness of programming
• Understanding performance characteristics of programs
• Competence with iterative and recursive solutions to problems

Plus

• Understanding of trees.
• Understanding of hash tables.
• Understanding of graphs.
• Understanding of string algorithms.

The following lecture plan is tentative and subject to change as the course progresses.

• Class 1: [2014/01/06-09] Symbol Tables (3.1, 3.5)
• Class 2: [2014/01/13-16] Binary Search Trees (3.2)
• Class 3: [2014/01/20-23] Balanced Search Trees (3.3)
• Class 4: [2014/01/27-30] Hash Tables (3.4)
• Class 5: [2014/02/03-06] Undirected Graphs (4.1)
• Class 6: [2014/02/10-13] Midterm
• Class 7: [2014/02/17-20] Directed Graphs (4.2)
• Class 8: [2014/02/24-27] MSTs (4.3) and Shortest Paths (4.4)
• Class 9: [2014/03/03-07] String sorts (5.1) and Tries (5.2)
• Class 10: [2014/03/10-13] Data Compression (5.5)
• Class 11: [2014/03/17-20] Final exam

Lecture slides will be available after each lecture. They will not normally be available before the lecture.

CSC300/402 C- or better.

If you are delayed in getting the texts, you can view them online via Safari.

Required Books

Algorithms 4e [Amazon, AddAll] by Robert Sedgewick and Kevin Wayne (Addison-Wesley, 2011) The book has a great companion site. Do not get any prior edition! Available as Ebook Available online via Safari

How to Think Like a Computer Scientist by Allen B. Downey. Free! An good introduction to Java. Skip the GridWorld chapters, which are intended to help with the AP exam in CS. See also these lecture notes from MIT. The first three lectures are particularly useful.

Java for Python Programmers by Brad Miller. Free! See also here.

Introduction to Programming in Java (Chapter 1) by Robert Sedgewick and Kevin Wayne Free! This is the first chapter of the introductory text written by the authors of our primary textbook. It presents the same material as section 1.1 of the primary text, but at a slower pace.

Recommended Books

Schaum's Outline of Data Structures with Java 2e [Amazon, AddAll] by John Hubbard (Schuams, 2009) This book is a good source of example problems with solutions. Available as Ebook

Effective Java 2e [Amazon, AddAll] by Joshua Bloch (Addison-Wesley, 2008) Available as Ebook Available online via Safari

The algorithms text describes all of the Java that is required for the class. The discussion is terse, making it an excellent reference. If you would like a longer discussion of Java, you might want a supplementary text. In this case, you might consider one of the following.

• Kathy Sierra and Bert Bates's "Head First Java" (on Safari)
• Bruce Eckel's "Thinking in Java" (3e available for free for download online and fine for our purposes)
• David Flanagan's "Java in a Nutshell" (on Safari)
• Cay Horstman's "Core Java I" (on Safari)
• Cay Horstman's "Big Java" (on Safari)

We will discuss concepts in class.

You will have weekly programming assignments.

• You do not have to do it alone, but you must be self-motivated.
• You can ask me and other members of the class.
• You must start assignments early.

• Incomplete Grades

  An incomplete grade is defined in the Student Handbook as follows (note that the policy in the undergraduate student handbook applies to both undergraduate and graduate students): A temporary grade indicating that the student has a satisfactory record in work completed, but for unusual or unforeseeable circumstances not encountered by other students in the class and acceptable to the instructor is prevented from completing the course requirements by the end of the term. Please see http://www.cdm.depaul.edu/Current%20Students/Pages/Grading-Policies.aspx for additional information.

• Retro-Active Withdrawal

  CDM understands certain extenuating circumstances can hinder one's ability for academic success and completion of course work. Please see http://www.cdm.depaul.edu/Current%20Students/Pages/Enrollment-Policies.aspx for additional information.

• Absence Notifications

  In order to petition for an excused absence, students who miss class due to illness or significant personal circumstances should complete the Absence Notification process through the Dean of Students office. The form can be accessed at http://studentaffairs.depaul.edu/dos/forms.html. Students must submit supporting documentation alongside the form. The professor reserves the sole right whether to offer an excused absence and/or academic accommodations for an excused absence.

Grades will be determined as follows.

• 5% Online attendance quizzes (Due friday midnight)
• 10% Online reading quizzes (Due Wednesday 3pm)
• 15% Online mastery quizzes (Due Wednesday 3pm)
• 25% Homework programming assignments (About one per week, overlapping)
• 45% Exams

DePaul's academic integrity policy