Course Description
Data Structures is a second semester continuation of CSCI 120, Introduction to Computing. The course covers the implementation and performance characteristics of common data structures, including linked lists, stacks, queues, and binary trees. Usage and implementation of recursion is also discussed, as is the elementary analysis of algorithms. The course is taught using the Java programming language, but no prior experience with Java is expected. The course uses Java to introduce concepts like program compilation and static type checking. The course helps students further develop their programming skills, introduces common programming building blocks, and helps students develop problem-solving skills by applying those building blocks.
Prerequisite
CSCI 120 Introduction to Computing
Textbooks
“Algorithms,” 4th edition, by R. Sedgewick and K. Wayne
Published April 3, 2011, by Addison-Wesley Professional
ISBN 978-0321573513
“Java for Python Programmers,” by Brad Miller
Creative Commons license, available for free at Runestone Academy
Course Content and Learning Objectives
- CS and Java Fundamentals: 9 lectures, 6 homeworks, 4 labs
- Primitive Data Types
- Conditionals and Loops
- Arrays
- Input and Output
- Static Methods
- Recursion
- Abstract Data Types (ADTs)
- User-Defined ADTs
- Software Development Fundamentals: 1 lecture, 8 labs
- Command-Line Interface
- Unit Testing
- Debugging Techniques
- Time and Memory Analysis: 2 lectures, 2 labs
- Importance of Efficient Solutions
- Experimental, Doubling Analysis
- Mathematical Models
- Big Theta, Big Oh, Big Omega Notation
- Linear Data Structures: 2 lectures, 5 homeworks, 4 labs
- Linked Lists
- Stacks and Queues
- Advanced Java: 2 lectures, 1 homework
- Inheritance
- Interfaces
- Generics
- Iterators
- Exceptions
- Sorting: 1 lecture, 1 lab
- Selection Sort
- Insertion Sort
- Symbol Tables (a.k.a. Dictionaries, Maps): 5 lectures, 2 homeworks, 2 labs
- Unordered Linked List and Ordered Array Implementations
- Separate Chaining and Linear Probing Implementations (Hash Tables)
- Binary Search Trees
- Balanced Search Trees
- Graphs: 2 lectures, 1 homework
- Undirected Graphs
- Directed Graphs
By the end of the course, students should develop a solid understanding of the topics listed above, improve their critical thinking, and computational problem solving skills, be more systematic and disciplined in their code development, and be better prepared for their further study in computer science. These learning objectives fit well with Clark’s LEEP learning outcomes and vision of liberal education.
Grading
The following percentages are tentative and may be changed at the instructor’s discretion:
- Attendance and Participation: 10%
- Assignments: 55%
- Midterm and Final: 35%
Time Expectations
Clark policy states that each course requires a minimum of 180 combined hours of engaged academic time for the student from time inside and outside the classroom. It is expected that you commit at least 12 hours to this class every week. Here is a general guideline for time expectations in this course:
- 2.5 hours: lecture attendance and participation
- 1.5 hours: lab attendance and participation
- 3.0 hours: studying the week’s materials
- 5.0 hours: completing assignments and attending office hours as needed
With a 15-week semester, this amounts to 15 * 12 = 180 hours.
Policies and Miscellaneous
The official administrative business of this class will be conducted by email
Grade questions, explanation of absence, etc. will be processed via email so that we both have a written record of what was agreed. Feel free to discuss in person but an email follow-up is required for the official record.
Use Piazza for questions about homework and lab
If you can’t make it to office hours or TA hours, using Piazza to ask questions is the next best thing. Piazza is designed to get you help fast and efficiently from classmates, the TA, and myself. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza. Questions clarifying assignment expectations can be asked publicly, since other students may have the same question. But if your question is about how to solve an assignment or includes your code, please ask the question privately.
Attendance and discussion/asking questions are expected
If you must be absent, please contact me in advance to let me know why you won’t be in class, and you must make up for the missed class and keep up with the course work.
Computer use policy
Computers and cell phones should be put away unless you are actively using them for class purposes with my permission. Do not use class time to work on other homework, play games, check email, check Facebook, or surf the web. Such activities can be distracting to other students.
Assignments are due on time
That is, at 11pm on the listed due date, with additional 59 minute courtesy time.
- Assignments received within 0-48 hours past the deadline will be accepted with a 20% penalty
- Assignments received more than 48 hours past the deadline will not be accepted or graded
Plan your work accordingly: work on each exercise and assignment as soon as possible, ask questions, and get help early. Students are responsible for ensuring that assignments are correctly submitted. Homework must be submitted as described in the instructions (e.g., uploaded to Gradescope), and cannot be submitted via emails to the instructor. If you have a question or problem, seek help from the instructor or a TA immediately.
No special make-up work will be accepted after the end of the semester
In the event of a documented major medical problem, a grade of Incomplete will be given pending the submission of complete work. However, make up work “to improve one’s grade” will not be accepted.
Grades are not negotiable
Please don’t ask for changes to your grades. Just do the work and you’ll get the grade you deserve. Of course, please bring any clerical grading errors to my attention and I will gladly fix them.
Pair Programming*
Some assignments allow pair programming. When partnering, both students work together (in the same room) and discuss, write, debug, test, analyze, document, and submit all elements of the assignment. In this case, only one partner (with the other partner present) submits their assignment code and report, identifying the other partner as a teammate on Gradescope. Both partners are responsible for understanding all parts of the submitted assignment and receive the same grade.
Collaboration policy*
Programming is an individual creative process much like composition. You must reach your own understanding of the problem and discover a path to its solution. Before you start coding, discussions with other people are permitted and encouraged. In fact, we recommend student cooperation in understanding programming concepts, algorithms and system features. You are encouraged to discuss lecture materials, textbook examples, labs, assignment problem specifications and expected outputs, and to seek and receive help with the programming language, IDE, and other tools. However, when the time comes to develop algorithms and write code that solves the problem, such discussions (except with course staff members) are no longer appropriate: the code must be your or your pair’s own work. For each assignment, you must specifically describe in your readme or report file, whatever help (if any) that you received from others and tell us the names of any individuals with whom you collaborated. This includes help from friends, classmates, lab TAs, and course staff members.
*Parts of the text are adapted from course webpages for “COS226: Data Structures and Algorithms”, R. Sedgewick and K. Wayne (Princeton)
Academic integrity: cheating and plagiarism
Academic integrity is a basic value for all higher learning. Simply expressed, it requires that work presented must be wholly one’s own and unique to that course. All direct quotations must be identified by source. Academic integrity can be violated in many ways: for example, by submitting someone else’s paper as one’s own; cheating on an exam; submitting one paper to more than one class; copying a computer program; altering data in an experiment; or quoting published material without proper citation of references or sources. Attempts to alter an official academic record will also be treated as violations of academic integrity.
To ensure academic integrity and safeguard students’ rights, all suspected violations of academic integrity are reported to the College Board. Such reports must be carefully documented, and students accused of the infraction are notified of the charge. In the case of proven academic dishonesty, the student will receive a sanction, which may range from an F in the assignment or course to suspension or expulsion from the University.
The complete academic integrity policy is available with Academic Advising at:
https://web.clarku.edu/policies/detailpolicy.cfm
Do not, under any circumstances, copy another person’s code or show your assignment code to other students. Incorporating someone else’s code into your program in any form, or allowing someone to do so with your code, is a violation of academic regulations. In addition to the definition of plagiarism in the handbook, with respect to this course, plagiarism is specifically defined to include (but is not limited to) the following:
- Copying any part of someone else’s assignment/program, even if you have permission and/or have modified the code
- Sharing or giving your assignment/code or even a subset of your assignment/code to another student
- Reviewing another student’s solution (including from past semesters)
- Reviewing solutions on the internet
- Using AI systems to generate solutions
You may not publish your solutions to this course’s programming problems in a way that could compromise their utility as pedagogical tools. I will run automatic plagiarism detection software on all coding assignments, and any similarities will be uncovered. Depending on the circumstances, the code’s original author may also be held responsible if another student copies their work.
If you have any questions about these matters, please consult the instructor.
If the scary consequences of failing the course or being expelled aren’t enough to convince you plagiarism is a bad idea, consider these points:
- Academic dishonesty dilutes the value of your degree. Would you rather hire a student who earned an A from a school where cheating is widespread, or hire a student who earned a B from a school where cheating is rare?
- If you cheat, you will learn less. Even if you somehow avoid getting caught, if you cheat you will be less prepared for job interviews and future jobs.
- Earning a low grade, or even failing, is better than passing by cheating. Grades are a function of your level of preparation and effort. If you fear a low grade, first talk to the instructor: there will be ways to improve your performance in the course (e.g., reading the textbook, attending office hours). But if you cannot earn a satisfactory grade despite devoting an inordinate amount of effort to the course, it is a signal that you should expect the same as you continue in the program: in this case, you should talk to your advisor about next steps. It would be terrible to “pass” a course by cheating, but not to have learned the skills along the way. How would you have a successful career in the field?
Welcoming class atmosphere
I strive to make this course welcoming and productive for all students. Please let me know what name and pronoun you prefer to be called. Please bring any issues or concerns to my attention.
Students with Disabilities
Clark University is committed to providing students with documented disabilities equal access to all university programs and facilities. Students are encouraged to register with Student Accessibility Services (SAS) to explore and access accommodations that may support their success in their coursework. SAS is located on the second floor of the Shaich Family Alumni and Student Engagement Center (ASEC). Please contact SAS at accessibilityservices@clarku.edu with questions or to initiate the registration process. For additional information, please visit the SAS website.
Title IX Reporting
Clark University and its faculty are committed to creating a safe and open learning environment for all students. Clark University encourages all members of the community to seek support and report incidents of sexual harassment to the Title IX office (titleix@clarku.edu). If you or someone you know has experienced any sexual harassment, including sexual assault, dating or domestic violence, or stalking, help and support is available.
Please be aware that all Clark University faculty and teaching assistants are considered responsible employees, which means that if you tell me about a situation involving the aforementioned offenses, I must share that information with the Title IX Coordinator, Brittany Rende (titleix@clarku.edu). Although I have to make that notification, you will, for the most part, control how your case will be handled, including whether or not you wish to pursue a formal complaint. Our goal is to make sure you are aware of the range of options available to you and have access to the resources you need.
If you wish to speak to a confidential resource who does not have this reporting responsibility, you can contact Clark’s Center for Counseling and Professional Growth (508-793-7678), Clark’s Health Center (508-793-7467), or confidential resource providers on campus: Prof. Stewart (als.confidential@clarku.edu), Prof. Palm Reed (kpr.confidential@clarku.edu), and Prof. Cordova (jvc.confidential@clarku.edu).
Disclaimer
The instructor reserves the right to make changes to any information contained in this syllabus at any time during the semester. Changes will be announced, and an updated version of the syllabus will be posted online.