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:
- 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.
- 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.
- 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.
- 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:
- Data Structures and Algorithms in Java 5th (2010) or 6th (2014) edition, by Goodrich, Tamassia (and Goldwasser)
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:
| 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:
| 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:
| Tues:
Thurs:
Lab 1 (cont) |
Feb 06 | |
4 | Feb 11 | | Linked Lists
- Linked list data structure
Reading:
| Tues:
Thurs:
Lab 2: ArrayLists
Pre-lab exercises
Tagging Lab 1 movie |
Feb 13 | |
5 | Feb 18 | | Time Complexity
Reading:
| Tues:
Thurs:
Lab 3: Linked Lists
Pre-lab exercises |
Feb 20 | |
6 | Feb 25 | | Stacks and Queues
Reading:
| Tues:
Thurs:
Lab 3 (cont) |
Feb 27 | Last day to pass/fail (Feb 28) |
7 | Mar 03 | | Review and Midterm
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:
| Tues:
Thurs:
Lab 4: Stacks and Queues |
Mar 19 | |
9 | Mar 24 | | Binary Trees
Reading:
| Tues:
Thurs:
Lab 5: Binary Trees |
Mar 26 | |
10 | Mar 31 | | Priority Queues
Reading:
| Tues:
Thurs:
Lab 6: Heaps |
Apr 02 | |
11 | Apr 07 | | Maps and Hash Tables
Reading:
| Tues:
Thurs:
Lab 6 (cont) |
Apr 09 | |
12 | Apr 14 | | Sorting and selection
Reading:
| Tues:
Thurs:
Lab 7: Deduplication |
Apr 16 | |
13 | Apr 21 | | Search trees and union-find
Reading:
| Tues:
Thurs:
Tues:
Midterm 2 (take-home)
Final Project: Project Options |
Apr 23 | |
14 | Apr 28 | | Review and Midterm
Reading
- Review chapters 7-12, 14.2, and 14.7.3
|
Apr 30 | |