CSC300: Syllabus

Course homepage: https://fpl.cs.depaul.edu/jriely/ds1/

• Lecture slides may not be available before the class.
• Lecture slides may change after class.

We will use zoom for live discussion during class hours. To join a meeting, use the link listed on the D2L calendar of events.

We will use discord as a discussion forum for class.

• Download the native discord app for your computer and/or mobile device.
• Click here to join the class server: Discord Discussion Forum
• Change your nickname to be your first and last name. Use whatever firstname you prefer, but be sure that your last name is the same as it is in DePaul's Campus Connect.
• We have all types of students in class. Be sure to use appropriate language.
• Don't troll.

The discussion forum is an extension our time in class. This is particularly great for students that miss the live lecture. If you are watching the class online, you should write down any questions that arise, including the time from the recording for reference. Then send the list of questions to me, and I will post a reply to the group.

This is the first course in a two-course sequence on data structures using Java. The course introduces basic Java programming, reviews recursion, introduces asymptotic notations, and focuses mainly on linear data structures including arrays, linked lists and their variants, stacks and queues, and data structures supporting disjoint-set operations. The implementation of the basic operations on each data structure are discussed and analyzed in terms of their efficiency. The applications covered highlight and exploit the unique characteristics of the data structures, and emphasize problem solving and recursive thinking.

Programs are not just for computers: We use them to communicate to other people.

• Ability to code without typing (on paper/whiteboard)
• Understanding correctness of programming
• Understanding performance characteristics of programs
• Competence with iterative and recursive solutions to problems
• Basic object-oriented programming
• Use of debuggers
• Use of testing

Plus

• Understanding of linked lists and resizable arrays
• Understanding of stacks, queues, dequeues
• Understanding of heaps
• Understanding of union-find

A data structure is a concrete implementation of an abstract type

• For example, linked lists and resizable arrays are data structures that could be used to represent the list type in python
• Which does python use? Why?

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

• Class 1: [2022/03/28-30] Arrays and Loops (1.1)
• Class 2: [2022/04/04-06] Recursion (1.1)
• Class 3: [2022/04/11-13] Linked Structures (1.2, 1.3)
• Class 4: [2022/04/18-20] Mutating Linked Structures (1.3)
• Class 5: [2022/04/25-27] Counting and Intro to Analysis (1.3, 1.4)
• Class 6: [2022/05/02-04] Midterm (Monday)
• Class 7: [2022/05/09-11] More Analysis, Union Find (1.4, 1.5)
• Class 8: [2022/05/16-18] Elementary Comparison-Based Sorting (1.2, 2.1, 2.5)
• Class 9: [2022/05/23-25] Priority Queues and Heaps (2.4, 6.1)
• Class 10: [2022/06/01] Review
• Class 11: [2022/06/08] Final exam

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

A prior programming class.

If you are delayed in getting the texts, you can view them online at O'Reilly.

Required Books

Core Java SE 9 for the Impatient, 2nd Edition [Amazon, Indiebound] by Cay Horstmann (Addison-Wesley, 2017) Available as Ebook (Online version) Companion site. Older edition is fine.

Algorithms 4e [Amazon, Indiebound] by Robert Sedgewick and Kevin Wayne (Addison-Wesley, 2011) Available as Ebook (Online version) (Author videos) These are also for sale as an Ebook Companion site. Do not get an older edition. They are completely different books.

Recommended Books

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

More Books

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.

Effective Java 3e [Amazon, Indiebound] by Joshua Bloch (Addison-Wesley, 2008) Available as Ebook (Online version)

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" (Online version)
• 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" (Online version)
• Cay Horstman's "Big Java" (Online version)

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.

Getting the homework correct is not enough. More Later.

You must attend class!

• 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 https://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 https://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 https://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.

• 20% Online quizzes
• 25% Programming assignments
• 55% Exams

Programming assignments that do not compile will receive zero points.

Exams will be given on paper, in person. There are no online exams. You must appear physically in front of a proctor (either teh instructor or someone else, as described in the policy linked below.)

• Students in the in-person section must be vaccinated and must take the exam on the chosen day and time, as announced on the course schedule.
• Students in online sections (synchronous or asynchronous) must register with a proctor for both exams. In order to register, use the CDM Proctored Exams section of the course homepage on D2L. You must register at least a week before the exam. Please do it ASAP. For further information, see here

You must pass the final exam in order to pass the course.

DePaul's academic integrity policy

All students are expected to abide by the University's Academic Integrity Policy which prohibits cheating and other misconduct in student coursework. Publicly sharing or posting online any prior or current materials from this course (including exam questions or answers), is considered to be providing unauthorized assistance prohibited by the policy. Both students who share/post and students who access or use such materials are considered to be cheating under the Policy and will be subject to sanctions for violations of Academic Integrity.

On exams, you must work alone, without any external resources.

It is your responsibility to ensure that you can complete any given homework or quiz question in about five minute, working alone, without using external sources.

To solve the weekly homeworks and quizzes, you may find it useful to consult external resources at first. That's fine. However, it is then incumbent on you to repeat those problems until you can do them yourself, starting from scratch, in a reasonable amount of time (about five minutes).