In nearly every software application, data must be stored and managed to meet the needs (i.e. time and space efficiency) of the user. This course introduces basic data structures and their application using the Java programming language. We introduce a mathematical framework for evaluating the efficiency of Java code, and develop implementations of basic data structures such as lists, stacks and queues. We study searching and sorting algorithms and introduce recursion as a strategy for improving the running time of these algorithms. This leads us to study more advanced data structures that are defined recursively, such as trees and heaps. We cover several advanced topics, such as hash tables and the storage and exploration of graphs.
At the end of this course, you should be able to:
- Use the object-oriented programming paradigm to write understandable and maintainable Java programs.
- Given a specification, design and implement an algorithm in Java that correctly satisfies the specification.
- Rigorously analyze the time and space efficiency of a Java program.
- Compare and contrast the relative merits (in terms of efficiency) and applicability of standard data structure
There are two types of class meetings held for this course:
- Lectures will be held three times a week by Professor Wolf. The main goal of the lectures is to present and discuss the main content that is covered in this course. It is expected that you have worked through the assigned reading and that you are familiar with the topic of the lecture. Lectures are not intended and cannot be a replacement for reading assignments and practicing coding.
- Discussion sessions are held weekly by Professor Tessier. The goal of the discussion session is to reemphasize the topics covered in the lecture and illustrate the concepts using specific code examples. The discussion sessions are held in smaller groups to encourage questions and discussion. You are expected to have studied the topics covered in lecture and to prepare questions that might have arisen.
These components of the course are designed to provide ample opportunity for you to clarify reading assignments, ask questions, and practice your skills. You are encouraged to seek any additional help you need from the instructors and TA’s during their office hours.
Your final grade will be derived from your performance in three areas:
- Homework consists of sets of theoretical problems and short coding assignments. Homework will be graded using a nonlinear "A/B" grading system that encourages both thoroughness and correctness. Each homework assignment will receive two separate scores:
- A-Grade: The grade reflects the fraction of assigned problems for which complete solutions were submitted.
- B-Grade: The grade is the score achieved on a subset of the assigned problems that are selected for full grading.
- Projects are larger coding assignments that require the development of solutions to more practical problems.
- Exams consist of two exams during the semester and one final exam. The exams are closed-book, closed-notes and evaluate how well you retained and understood the course content as well as how well you can apply the course concepts to new problems. For each exam, an in-class review session will be held to provide time for resolving issues regarding the content and procedure of the exam.
Homework and projects are assigned according to the schedule posted on the course website. Solutions to homeowrk and project assignments must be submitted on Moodle. Late submissions will not be accepted. In case of a medical emergency, late submission or a make-up exam can be requested if a note from a medical professional is provided. Midterms are held according to the schedule on the course website. The final exam is scheduled by the university.
The final grade will be norm-referenced (i.e., graded “on a curve”) with the following weighting:
- Homework: 10%
- Projects: 20%
- Exam I: 20%
- Exam II: 20%
- Final Exam: 30%
You are encouraged to track your scores on Moodle to ensure that you have received the appropriate credit for each of your assignments and exams. No extra credit or “make-up” assignments will be given (with exception to the cases stated in the examination policy below).
Attendance and Punctuality
You are expected to attend the all of the lectures and discussion sessions for which you are enrolled. You are expected to come to lectures, discussions, and examinations on time; arriving late and/or leaving early is disrespectful and disrupts the entire class.
Late / Make-Up Policy
Assignments are due as posted on the course web page. Late submissions will not be accepted. Scheduling conflicts regarding exams should be reported to the instructor immediately. In case of a medical emergency, late submission or a make-up exam can be requested if a note from a medical professional is provided. The note must indicate that the student was medically incapable at the time of the exam. If advanced notice is possible and not given, the instructor may refuse the request.
Consultation with fellow students is encouraged. However, directly copying another student's work (past or present) defeats the purpose of the assignments and exams and is an honor code violation. Unless otherwise noted, you are expected to complete all assignment individually. Violations will result in serious penalties including course failure and possible disciplinary action. If in doubt, please consult the instructor or the official UMass guidelines regarding academic honesty.