CMSC H106: Intro to Data Structures

(Spring 2020)

Course Info | Schedule | Grading
Academic Integrity | Piazza | Accommodations | Links
CMSC H106 Data Structures

Course Information

Course: TuTh 10–11:30am, KINSC H204
Professor: Sara Mathieson
Office: KINSC L302
Office hours: Tuesdays 4:30-6pm (in H110)
Lab Instructor: Suzanne Lindell
TAs: Emile Givental, Juvia Han, William Lawrence, Steve Lee, Gareth Nicholas, Lizzie Spano
TA Office hours: Sundays 7-9pm (Juvia) + TBD
Piazza: CMSC H106 Q&A forum

The prerequisite for this course is Introduction to Computer Science.

This course provides an introduction to the fundamental data structures of computer science: strings, lists, stacks, queues, trees, BSTs, graphs, sets and their accompanying algorithms. Principles of algorithmic analysis and object reasoning and design will be introduced using mathematical techniques for the notions of both complexity and correctness. We will also cover practical issues such as memory management and hashing. The programming language used to illustrate and implement these concepts will be able to support functional, imperative and object-oriented approaches. There are several course objectives beyond mastery of the course material:

  1. Right tool for the right job. By the end of this course, you should not only be able to understand the key data structures, but also apply them in a variety of contexts. Given a new problem, selecting an appropriate data structure or algorithm is an extremely important skill for software developers.
  2. Linking theory and programming. Throughout the course we'll be learning about data structures in a language-independent way, as well as implementing and applying them in Java. Learning to bridge theory and a specific language is an important skill for this course and afterwards.
  3. Learning a new language. Hopefully you will leave this course with a mastery of the Java programming language, while understanding that Java != computer science. You should leave this course with the confidence that you can learn how to use data structures in the context of a new programming language in the future.
  4. Good coding practices. These include an effective workflow (make a small change, then test, effective use of print statements, debugging) as well as proper coding style. Part of being a good software developer is writing code that other people (including yourself) can read and use later on.

The language for this course is Java.

Textbook:


See the Schedule for each week's reading assignment. The schedule is tentative and subject to change throughout the semester.

Schedule (Tentative)

WEEK DAY ANNOUNCEMENTS TOPIC & READING LABS
1

Jan 21

 

Introduction

  • Java basics and syntax
  • Documentation, Javadoc comments
  • Types and type conversion
  • Variable scope
  • Basics of classes
  • Programming style

Reading:

  • Chapter 1

Tues:

Thurs:

Lab 0: Java intro
In-lab exercises
Eclipse/GIT movie
In-lab notes

Jan 23

 
2

Jan 28

Registration ends (Jan 29)

Intro to Object Oriented Programming

  • Objects and Classes
  • Inheritance
  • Variable scope (cont)
  • Strings

Reading:

  • Chapter 2

Tues:

Thurs:

Lab 1: Data design
Understanding Propublica
Pre-lab exercises
StudentProfile.csv

Jan 30

 
3

Feb 04

 

Object Oriented Programming (cont)

  • Generics
  • Exceptions
  • Basics of arrays
  • ArrayLists

Reading:

  • Chapter 2, 3.1

Tues:

Thurs:

Lab 1 (cont)

Feb 06

 
4

Feb 11

 

Linked Lists

  • Linked list data structure

Reading:

  • Chapter 3

Tues:

Thurs:

Lab 2: ArrayLists
Pre-lab exercises
Tagging Lab 1 movie

Feb 13

 
5

Feb 18

 

Time Complexity

  • Big-O notation

Reading:

  • Chapter 4

Tues:

Thurs:

Lab 3: Linked Lists
Pre-lab exercises

Feb 20

 
6

Feb 25

 

Stacks and Queues

  • Stacks
  • Queues

Reading:

  • Chapter 6

Tues:

Thurs:

Lab 3 (cont)

Feb 27

Last day to pass/fail (Feb 28)

7

Mar 03

 

Review and Midterm

  • Review

Reading:

  • Review: chapters 1-4 and 6

Tues:

Midterm 1 (in-class)

Mar 05

 
 

Mar 10

Spring Break

Mar 12

8

Mar 17

 

Lists, iterators, interfaces, and graphs

  • Graph basics (nodes, edges, weights, neighbors, degree)
  • Directed vs. undirected graphs
  • Graph implementations

Reading:

  • Chapter 7, 8.1, and 14.2

Tues:

Thurs:

Lab 4: Stacks and Queues

Mar 19

 
9

Mar 24

 

Binary Trees

  • Binary trees

Reading:

  • Chapter 8

Tues:

Thurs:

Lab 5: Binary Trees

Mar 26

 
10

Mar 31

 

Priority Queues

  • Priority queues

Reading:

  • Chapter 9

Tues:

Thurs:

Lab 6: Heaps

Apr 02

 
11

Apr 07

 

Maps and Hash Tables

  • Maps
  • Hash tables

Reading:

  • Chapter 10

Tues:

Thurs:

Lab 6 (cont)

Apr 09

 
12

Apr 14

 

Sorting and selection

  • Sorting algorithms

Reading:

  • Chapter 12

Tues:

Thurs:

Lab 7: Deduplication

Apr 16

 
13

Apr 21

 

Search trees and union-find

  • Searching algorithms

Reading:

  • Chapter 11 and 14.7.3

Tues:

Thurs:

Tues:

Midterm 2 (take-home)

Final Project: Project Options

Apr 23

 
14

Apr 28

 

Review and Midterm

  • Review

Reading

  • Review chapters 7-12, 14.2, and 14.7.3

Apr 30

 

Grading Policies

Grades will be weighted as follows:
45% Lab assignments
40% Midterms (20% each)
10% Final Project
5% Participation

Quizzes and Exams

There will be occasional reading quizzes. These are graded largely on completion, not correctness. Reading quizzes count toward participation. If you have made a solid attempt at the reading and show up for class, you will likely receive full credit.

There will be two midterms, each during class (see Schedule). Let me know as soon as possible if you have a conflict with one of the exams. In lieu of a final exam, there will be a final project. You must pass at least one exam to pass the course overall.

Labs

Our labs are on Fridays. Lab assignments will generally be released Wednesday night and due the following Wednesday at midnight. You are expected to read/begin the lab before your lab section on Friday. Lab attendance is required, and missing labs will quickly affect your participation grade. There may be warm-up exercises as part of the lab, and lab in general is a time to build community around the course and the material. Note that Wednesday is my research day and I will be off campus and unable to answer lab questions. We encourage you to attend office hours and evening lab hours as much as possible, and to post questions on Piazza outside of office hours.

Weekly Lab Sessions
Lab A 9:30—10:30am Friday Lindell H110
Lab B 10:30—11:30am Friday Lindell H110
Lab B 11:30—12:30pm Friday Lindell H110

Handing in labs: Lab assignments are submitted electronically and managed using git. You may submit your assignment multiple times, but each submission overwrites the previous one and only the final submission will be graded. Some of the programming/lab assignments may be in pairs. There may also be some written assignments that will have specific instructions for handing in.


Late Policy: Each individual will be given 2 late days for the semester. A late day is a 24 hour extension from the original deadline. You can use one day on two assignments or both days on one assignment. This will encompass any reason - illness, interviews, many midterms in the same week, etc. Past these days, late assignments will not be accepted. You should budget your days to account for future illnesses or assignment deadlines for other courses. Even if you do not fully complete a lab assignment you should submit what you have done to receive partial credit. Late days count against both partners in a group lab.

For extensions beyond these 2 late days (in the case of an emergency or ongoing personal issue), please contact your Class Dean. The three of us will work together to arrange an appropriate accommodation.


Electronic Devices

Both lecture and lab classrooms are equipped with computers, and we will frequently use them for practice problems during class. We encourage you to use the lab machines, as the development environment has already been set up. However, you may use your own machine in a way that is directly related to the class (taking notes, working on a practice problem, etc). Please refrain from any other websites or non-class related activities, for the main reason that this is distracting to others sitting around you.

Academic Integrity

From the faculty:

"In a community that thrives on relationships between students and faculty that are based on trust and respect, it is crucial that students understand a professor's expectations and what it means to do academic work with integrity. Plagiarism and cheating, even if unintentional, undermine the values of the Honor Code and the ability of all students to benefit from the academic freedom and relationships of trust the Code facilitates. Plagiarism is using someone else's work or ideas and presenting them as your own without attribution. Plagiarism can also occur in more subtle forms, such as inadequate paraphrasing, failure to cite another person's idea even if not directly quoted, failure to attribute the synthesis of various sources in a review article to that author, or accidental incorporation of another's words into your own paper as a result of careless note-taking. Cheating is another form of academic dishonesty, and it includes not only copying, but also inappropriate collaboration, exceeding the time allowed, and discussion of the form, content, or degree of difficulty of an exam. Please be conscientious about your work, and check with me if anything is unclear."

Please also note the CS Department Collaboration Policy.

More details for this course:

Under no circumstances may you hand in work done with (or by) someone else under your own name. Your code should never be shared with anyone; you may not examine or use code belonging to someone else, nor may you let anyone else look at or make a copy of your code. This includes, but is not limited to, obtaining solutions from students who previously took the course or code that can be found online. You may not share solutions after the due date of the assignment.

Discussing ideas and approaches to problems with others on a general level is fine (in fact, we encourage you to discuss general strategies with each other), but you should never read anyone else's code or let anyone else read your code. All code you submit must be your own with the following permissible exceptions: code distributed in class, code found in the course text book, and code worked on with an assigned partner. In these cases, you should always include detailed comments that indicates on which parts of the assignment you received help, and what your sources were.


Piazza

This semester we’ll be using Piazza, an online Q&A forum for class discussion, help with labs, clarifications, and announcements. You should have received an email invitation to join CMSC H106 on Piazza. If you didn't, please let me know.

Piazza is meant for questions outside of regular meeting times such as office hours, class, and lab. Please do not hesitate to ask and answer questions on Piazza, but keep in mind the following guidelines:

  1. Piazza should be used for ALL content and logistics questions outside of class, lab, and office hours. Please do not email me your code or extended questions about the assignments.
  2. If there is a personal issue that relates only to you, please email me.
  3. We encourage non-anonymous posts, but you may post anonymously (to your classmates, not the instructors).
  4. Please avoid posting long blocks of code on Piazza - if you can distill the problem to 1-2 lines of code and an error message, that’s fine, but try to avoid giving out key components of your work.
  5. By the same token, when answering a question, try to give some guiding help but do not post code fixes or explicit solutions to the problem.
  6. Posting on Piazza counts toward your participation grade, both asking and answering!

Academic Accommodations

For details about the accommodations process, visit the Access and Disability Services website.

"Haverford College is committed to providing equal access to students with a disability. If you have (or think you have) a learning difference or disability – including mental health, medical, or physical impairment - please contact the Office of Access and Disability Services (ADS) at hc-ads@haverford.edu. The Coordinator will confidentially discuss the process to establish reasonable accommodations.

Students who have already been approved to receive academic accommodations and want to use their accommodations in this course should share their verification letter with me and also make arrangements to meet with me as soon as possible to discuss their specific accommodations. Please note that accommodations are not retroactive and require advance notice to implement.

It is a state law in Pennsylvania that individuals must be given advance notice if they are to be recorded. Therefore, any student who has a disability-related need to audio record this class must first be approved for this accommodation from the Coordinator of Access and Disability Services and then must speak with me. Other class members will need to be aware that this class may be recorded."