Syllabus

In this course, each voice in the classroom has something of value to contribute. Please take care to respect the different experiences, beliefs and values expressed by students and staff involved in this course. My colleagues and I support UMass’s commitment to diversity, and welcome individuals regardless of age, background, citizenship, disability, sex, education, ethnicity, family status, gender, gender identity, geographical origin, language, military experience, political views, race, religion, sexual orientation, socioeconomic status, and work experience.

View this syllabus as a guide to the course. It provides important information regarding the course, its assignments, policies, grading, and available university resources.

You should read it once, thoroughly, at the start of the semester. However, this document should be considered a working document. It is possible throughout the semester that a topic may take more time than expected, topics or assignments may change, or a class may be canceled due to a snow day or another emergency. If that is the case, the syllabus and schedule will be updated and a revised version will be posted on the course web site.

Course Overview

Description: This course introduces foundational abstract data types and algorithms. The main focus is on the use of data structures in designing and developing programs to solve problems in a variety of domains. Specific topics include lists, sets, maps, graphs, stacks, queues, searching, and sorting. There will be weekly programming assignments, programming and written exercises in discussion sections, regular quizzes, and a cumulative final exam.

Prerequisites: C or better in COMPSCI 121 (or transfer credit, or appropriate score on the placement exam). This course is not a substitute for COMPSCI 187. If unsure of whether this course or COMPSCI 187 is more appropriate, contact instructor. 4 credits.

Objectives: COMPSCI 186 requires students to engage in extensive problem solving and critical thinking. In particular, through a project-based curriculum, students expand their ability to design, reason about, and implement non-trivial algorithms and data structures in a general-purpose programming language.

As the course progresses, project scope expands, and the amount of explicit guidance that students are given is decreased – to succeed, students must incrementally improve their programming ability. Thinking in abstractions, planning large (multi-file) programs, and learning to understand why a program does (or doesn’t!) work as expected are activities that require significant critical thinking and problem solving.

In addition to programming projects, students complete both in-class and take home exercises, about six half-hour quizzes and a final exam. Among other things, these activities serve to evaluate other aspects of critical thinking and problem solving that are better assess in a written format. For example, students might be asked to determine the asymptotic running time of a snippet of code; to show (on paper) how a particular algorithm would operate on a given data set (such as a graph traversal algorithm); to identify logical errors in code; or to compare how operations defined by set theory and by a programming language’s set implementation differ.

Prerequisites

COMPSCI 121 (or equivalent experience) and Basic Math Skills (R1). This course is not a substitute for COMPSCI 187. If unsure of whether this course or COMPSCI 187 is more appropriate, contact instructor.

Learning Outcomes

After completing this course, students should be able to:

Design and write methods using the basic tools of imperative programming: variables and branches, loops over counters and linear data structures.
Design and write methods using simple recursion for control flow.
Analyze problems best solved with multiple classes, implement object-oriented solutions given some scaffolding or design advice, and determine which (if any) of the existing implementations of the List, Set, Map, Stack, and Queue ADTs are appropriate when solving these problems.
Use, design and implement test methods to exercise both single methods and whole programs.
Use both formal debuggers and program output to determine the cause of logical program errors.
Explain the concept of worst-case running time analysis, and classify simple examples of linear, quadratic, and constant-time code.
Categorize the worst-case running time of operations on arrays and on the List, Set, Map, Stack, and Queue ADTs, given information about their underlying implementation.
Explain the O(n^2) sorting algorithms.
Explain and implement breadth-first search, given an existing implementation of graphs.
Explain the implementation details of array- and linked-list-backed Stacks and Queues.

Week-By-Week Schedule of Topics

Week 1 - Introduction & Reviewing Java Control Flow
Week 2 - Developing with the Eclipse IDE
Week 3 - Classes, Object, and Namespace & Array-Backed Lists
Week 4 - Linked Lists
Week 5 - Comparators & Sets
Week 6 - Hashsets, Treesets & Maps
Week 7 - Introduction to Program Running Time
Week 8 - Searching and Sorting & Graphs
Week 9 - Graph Search & Stacks and Queues
Week 10 - Implementing Stacks & Queues
Week 11 - Introducing Recursion
Week 12 - Problem Solving with Recursion
Week 13 - Problem Solving with Graphs

Course Structure

Description: This course introduces foundational abstract data types and algorithms. The main focus is on the use of data structures in designing and developing programs to solve problems in a variety of domains. Specific topics include lists, sets, maps, graphs, stacks, queues, searching, and sorting. There will be weekly programming assignments, programming and written exercises in discussion sections, regular quizzes, and a cumulative final exam.

Prerequisites: C or better in COMPSCI 121 (or transfer credit, or appropriate score on the placement exam). This course is not a substitute for COMPSCI 187. If unsure of whether this course or COMPSCI 187 is more appropriate, contact instructor. 4 credits.

Objectives: COMPSCI 186 requires students to engage in extensive problem solving and critical thinking. In particular, through a project-based curriculum, students expand their ability to design, reason about, and implement non-trivial algorithms and data structures in a general-purpose programming language.

As the course progresses, project scope expands, and the amount of explicit guidance that students are given is decreased – to succeed, students must incrementally improve their programming ability. Thinking in abstractions, planning large (multi-file) programs, and learning to understand why a program does (or doesn’t!) work as expected are activities that require significant critical thinking and problem solving.

In addition to programming projects, students complete both in-class and take home exercises, about six half-hour quizzes and a final exam. Among other things, these activities serve to evaluate other aspects of critical thinking and problem solving that are better assess in a written format. For example, students might be asked to determine the asymptotic running time of a snippet of code; to show (on paper) how a particular algorithm would operate on a given data set (such as a graph traversal algorithm); to identify logical errors in code; or to compare how operations defined by set theory and by a programming language’s set implementation differ.

What, when, where, who

COMPSCI 186: Using Data Structures

Class Meeting Times: TBA

Zoom

Instructor: Peter F. Klemperer (please call me “Peter”)

Email: pklemperer@umass.edu (though see note below about Piazza)

Office: Computer Science

Office hours: TBA - see Moodle.

TAs: TBA - see Moodle.

Email: TBA - see Moodle.

Office hours: TBA - see Moodle.

UCAs:

Please see our Piazza site for the full list of UCA office hours.

Required material

Most technical material will be presented in lecture or on the course website.

For students who want additional references, I suggest several optional resources:

The Java Tutorials, likely already familiar to you from COMPSCI 121 or the equivalent, are guides to the Java language. I’ll note in the schedule specific “trails” that you may find helpful.
Similarly, the Java Platform API provides a comprehensive description of all classes Java Platform; we’ll make extensive use of some of them, and they are fully documented by Oracle.
Think Java: How to Think Like a Computer Scientist, 1st edition, by Allen B. Downey and Chris Mayfield. Think Java is an alternative to the COMPSCI 121 textbook, and covers about the same material. It primarily focuses on the craft and science of problem solving with computers, with a secondary focus on Java. You may find this book useful to review before the start of the semester or during the first few weeks of this course.
Learning Java, 4th edition, by Patrick Niemeyer and Daniel Leuck. This book is aimed at working programmers, not computer scientists, and focuses much more on use of Java, tooling in the Java ecosystem, and practical considerations than Think Java. You may find it useful when using some of the tools we require in this course, and when completing some of the advanced (and optional) parts of later programming assignments.
Java Precisely, 3rd edition, by Peter Sestoft. If you want to know something about the Java language – syntax or semantics – this book is a great reference. Note that it is not a textbook or a how-to manual, but a reference book that explains what specific part of the language mean. It also provides some explanation of important parts of the Java standard library (also known as the class library or Java Platform API).
Eclipse IDE Pocket Guide, by Ed Burnette. You might find it helpful to have a guide to Eclipse, the Integrated Development Environment we’ll be using in this course. The Pocket Guide is not comprehensive, but it is a valuable reference to the most commonly-used parts of the IDE.

Code of conduct

The course staff are committed to providing a friendly, safe and welcoming environment for all, regardless of level of experience, gender identity and expression, sexual orientation, disability, personal appearance, body size, race, ethnicity, age, religion, nationality, or other similar characteristic.
Please be kind and courteous. There’s no need to be mean or rude.
Respect that people have differences of opinion and that differing approaches to problems in this course each carry a trade-off and numerous costs. There is seldom a single right answer to complicated questions.
Please keep unstructured critique to a minimum. Criticism should be constructive.
We will informally warn you, once, if you insult, demean or harass anyone. That is not welcome behavior. After that we will report your behavior to the Dean of Students office. We interpret the term “harassment” as including the definition in the Citizen Code of Conduct under “Unacceptable Behavior”; if you have any lack of clarity about what might be included in that concept, please read their definition. In particular, we don’t tolerate behavior that excludes people in socially marginalized groups.
Private harassment is also unacceptable. No matter who you are, if you feel you have been or are being harassed or made uncomfortable by a member of this class, please contact a member of the course staff immediately (or if you do not feel safe doing so, you should contact the Chair of the Faculty of CICS, currently Prof. James Allan, allan@cs.umass.edu, or the Dean of Students office). Whether you’ve been at UMass for years or are a newcomer, we care about making this course a safe place for you and we’ve got your back.
Likewise any spamming, trolling, flaming, baiting or other attention-stealing behavior is not welcome.

(Partially drawn from the Rust Code of Conduct.)

Communication policy

Per the University Email Policy, you are expected to check your email regularly – at least once a day. I will use your UMass email address as your point of contact in all online tools we use (Moodle, Piazza, and Gradescope) and as my primary means to contact you individually outside of class. Group announcement will be posted to Piazza, which by default will send you via email whenever an instructor makes a post.

For course-content related questions (especially questions that other students might benefit from seeing the answers to), please use Piazza. For other questions (like unusual logistics stuff), email is best, but please check the syllabus and course web site before emailing the course staff. If you send me (or the TAs) email, please include “COMPSCI 186” in the subject line to make sure we answer them in a timely fashion.

Course staff typically respond to emails and Piazza questions within one to two business days, but I (Peter) do not typically respond to communications after about 5pm or on weekends. Course staff tend to get a higher volume of email when a deadline is approaching. If you contact the course staff (that is, at least one TA and the instructor) at least two full business days before a quiz or deadline, you are guaranteed a reply before the quiz or deadline. Otherwise we’ll do our best, but no guarantees.

Attendance

Attendance at lecture is not mandatory. Discussion sections will include quizzes which must be taken during your section time.

Piazza

Piazza is a online discussion management system. It will be used as the main hub for questions and answers in this course. Piazza is a great tool but it can be abused. Please follow these guidelines in your use of Piazza:

You should use Piazza to ask questions and get advice on assignments. But you may not use Piazza to step through each problem you encounter in an assignment.
You may not post assignment solutions to Piazza, either in questions or answers to others’ questions.
If you must post code you are working on, you should do so only through private posts to the course instructors.
You should not post code without a thoughtful and articulate question. Do not post code and ask only, “what is wrong with my code?” See, for example, http://stackoverflow.com/help/how-to-ask or https://jvns.ca/blog/good-questions/ for constructive advice on asking questions.
You are encouraged to help other students by answering questions.

The course staff will monitor Piazza and answer your questions in a timely manner (generally within a business day). But do not expect us to provide real-time answers on Piazza, especially in the last few hours before an assignment is due!

If a question has already been answered in a previous post we may not respond to you. If a question does not follow the guidelines above we may not answer it. If we find that a private question is relevant to a larger audience, we may make mark it public to help others in the course.

Time management and what to expect

As a general guideline, the university suggests that students spend an additional two to three hours outside of class time per credit hour. This is a four-credit course, therefore you should plan to spend eight to twelve hours a week on this class outside of lecture and discussion meetings.

In a typical week, you will attend discussion (where there will be either a self-contained activity or a quiz), attend two lectures (including in-class exercises), complete two short out-of-class assignments (due at the start of lecture) and one larger programming assignment (where you will spend the bulk of your time in this course), and complete the assigned reading.

Grading

The relative values of the various course components are approximately as follows:

30% programming assignments
30% homeworks / exercises
25% quizzes
15% final exam

The numerical cutoff for final course letter grade assignment will be made after all grading is completed. As a rough guide, expect the following:

100.00 % to 93.00 % A
92.99 % to 90.00 % A-
89.99 % to 87.00 % B+
86.99 % to 83.00 % B
82.99 % to 80.00 % B-
79.99 % to 77.00 % C+
76.99 % to 73.00 % C
72.99 % to 70.00 % C-
69.99 % to 67.00 % D+
66.99 % to 60.00 % D
59.99 % to 0.00 % F

I reserve the right to relax the grade requirements, but promise not to tighten them. In other words, 87.99 % may be rounded to an A. However, 93.00 will not be reduced to an A-.

There are no unannounced opportunities for extra credit in this course; please do not ask.

Late work will not be accepted. If you need an extension for an assignment, contact me a reasonable amount of time — generally, at least a full business day — before the assignment is due. If you are incapacitated for one or more days up to and including the due date, I will require written documentation explaining your inability to work on course material in order to consider granting a retroactive extension, at my discretion.

Also: It’s 2021. Storage and bandwidth are virtually free, and the University has both computer labs and loaner computers available. “My computer crashed” won’t be acceptable as an excuse in this class.

I will retain all graded materials for this course until the end of next semester. If you wish to review them, please come to see me during office hours (or make an appointment).

You are responsible for monitoring your grades. Grades will be available through Moodle and you should check them regularly and review any provided feedback. If you encounter any issues with your grades, you will have one week past the first posting of a particular assignment’s grade to Moodle to contact the course staff so that we can investigate. Please contact us via a private message on Piazza. We will not generally accept questions about an individual assignment’s grade beyond this one week, so you must be prompt.

Programming assignments

I will post programming assignments about once a week, and you will typically have about one week to complete them. They will be posted to the course web site’s assignment page and must be submitted through Gradescope. Programming assignments must be completed individually, that is, you may not collaborate on code! See the course honesty policy, below, for more details.

You are responsible for submitting code that compiles and runs on the autograder; if you submit code that does not compile or that gets stuck in an infinite loop, you will receive no credit.

Attempts to manipulate, game, or otherwise incorrectly use the autograder will be treated as academic dishonesty.

Homeworks

There will usually be a short exercise (“homework”) due at the start of each lecture. They will be generally posted to the course web site’s assignment page by the end of the day of the preceding lecture. These will generally be submitted through Gradescope.

You may work with your classmates on homeworks.

Quizzes and exams

There will be about seven quizzes over the course of the semester. The quizzes will be announced, and given during discussion meetings. Each will consist of a few programming questions that you will answer on paper, and they may include a few other short-answer questions as well. They will be short: designed to be completed in about 25 minutes, though we will give you the entire 50 minute discussion period to complete them.

There will also be a cumulative final exam. It will be in the style of the quizzes, but it will be significantly longer. You must achieve a passing grade on the final exam to pass the class.

Please note (from the Academic Rules and Regulations):

…it is University policy not to require students to take more than two final examinations in one day of the final examination period. If any student is scheduled to take three examinations on the same day, the faculty member running the chronologically middle examination is required to offer a make-up examination if the student notifies the instructor of the conflict at least two weeks prior to the time the examination is scheduled. The student must provide proof of the conflict. This may be obtained from the Registrar’s Office, 213 Whitmore.

You may not bring supplemental material to the quizzes or final exam, that is, they are closed-book, and the use of notes, calculators, computers, phones, etc., is forbidden.

Quizzes and exams must be completed on your own: they are not collaborative!

Equality Statement

The professor is dedicated to establishing a learning environment that promotes diversity of the students, including race, class, culture, religion, gender, sexual identity, and physical ability. It is important that this is a safe virtual classroom environment. We will practice being generous and respectful members of our classroom and computer science community. Anyone noticing discriminatory behavior in this class, or who feels discriminated against, should bring it to the attention of the instructor immediately.

ACCOMMODATIONS

Accommodations are collaborative efforts between students, faculty, and Disability Services (DS). Students with accommodations approved through DS are responsible for contacting the faculty member in charge of the course prior to or during the first week of the term to discuss accommodations. Students who believe they are eligible for accommodations but who have not yet obtained approval through DS should contact DS immediately at (413) 545-0892. If you are a student with a documented disability and are registered with Disability Services, please contact me immediately to facilitate arranging academic accommodations. Reasonable arrangements will be made in accordance with your accommodations provided by DS in the context of this course.

COURSE INCOMPLETES

Students who are unable to complete course requirements within the allotted time because of severe medical or personal problems only may request a grade of Incomplete from the instructor of the course. Incomplete grades are warranted only if a student is passing the course at the time of the request and if the course requirements can be completed by the end of the following semester. Furthermore, an incomplete will be granted if at least 75% of the work has been completed for the course. Otherwise, the recommended course of action is to withdraw and retake the course in the future. Please see the Academic Regulations Section IV Grading System and Credit Guidelines for further details.

Note: an incomplete means you are on your own to complete the material agreed upon by the instructor of this course. Do not expect additional help or one-on-one teaching of the material past the course completion date. It is your responsibility to complete the remaining material.

Academic honesty

General academic honesty statement

Since the integrity of the academic enterprise of any institution of higher education requires honesty in scholarship and research, academic honesty is required of all students at the University of Massachusetts Amherst. Academic dishonesty is prohibited in all programs of the University. Academic dishonesty includes but is not limited to: cheating, fabrication, plagiarism, and facilitating dishonesty. Appropriate sanctions may be imposed on any student who has committed an act of academic dishonesty. Instructors should take reasonable steps to address academic misconduct. Any person who has reason to believe that a student has committed academic dishonesty should bring such information to the attention of the appropriate course instructor as soon as possible. Instances of academic dishonesty not related to a specific course should be brought to the attention of the appropriate department Head or Chair. Since students are expected to be familiar with this policy and the commonly accepted standards of academic integrity, ignorance of such standards is not normally sufficient evidence of lack of intent.

In addition, you should read the UMass Academic Honesty Policy (ignorance of the policy is no excuse).

Course-specific academic honesty information

Academic dishonesty is usually the result of other problems in school. Please come see me or the TA if you are unable to keep up with the work for any reason and we will do our best to work something out. I want to see you succeed, but I will not tolerate academic dishonesty.

Investigating academic dishonesty is an unpleasant experience for both the instructor and the student. Please help me by avoiding any questionable behavior.

What is permitted and what is not? You may discuss material with others, but when collaboration is forbidden (as it is on programming assignments), your writing (code and prose) must be your own.

The surest way to avoid problems is as follows: When discussing problems with others, do not show any of your solution (code or otherwise) to others. In particular, do not sit down and start typing on a classmate’s laptop, do not allow a classmate to type on yours, and don’t act as a dictation machine (where a classmate sitting next to you tells you what to type).

When asking others for help, avoid taking detailed notes about the solution – you want to avoid doing a copy/paste, whether it be on a computer screen or using pen and paper.

When you ask for help, either in person or on Piazza, it’s good practice to ask your question by describing the problem you’re having, or using a small synthetic example that illustrates your difficulty. If you must include a large chunk of your code to ask your question on Piazza, mark it as a “private” question, and only the course staff will be able to see it.

When searching for the answer online: Don’t. Just don’t.

Do not provide your solutions to others, either directly or via some sort of public posting, except when collaboration is explicitly permitted and when both you and the other person are currently enrolled in this course. Publicly or privately redistributing solutions to exercises, homeworks, or assignments for this course is a violation of the University Honesty Policy’s prohibition against facilitating academic dishonesty.

Copying and pasting code from another student or a third party is a violation of academic honesty, and we will endeavor to detect this by any means available to us, including automated similarity analysis of submitted assignments. Be aware that if something looks like academic dishonesty to us, we will treat it as such, unless you can provide strong evidence to the contrary. When in doubt, it is your responsibility to contact the course staff about whether a potential action would be considered academic dishonesty.

A word about putting your solutions on GitHub, GitLab, BitBucket, etc.

Per the course-specific academic honesty policy, you are not permitted to make your solutions to the assignments in this class available to others. This includes reposting them to public GitHub repositories (or other service where another student might plausibly see them).

A word about copyrights

Most of the material (lecture notes, lectures, assignments, and so on) in this course is original work created by the Marc Liberatore; exceptions are clearly noted. While you are welcome to use the material for your own personal and educational use, you may not redistribute them to others outside the class. In particular, selling or otherwise redistributing your notes (or mine!), making or selling audio, video, or still recordings of course material, is not allowed without express written permission from m

I make this stuff available on the web for you to use easily and without the hassle of sign-ups, logins, and the like, not for you to abuse for a buck. As Carol Barr (Senior Vice Provost and Dean of Undergraduate Education) and Enku Gelaye (Vice Chancellor for Student Affairs and Campus Life) noted at the start of the Fall 2018 semester, usage of notes or in-class recordings without the faculty member’s permission is a violation of the faculty member’s copyright protection.