reachsagaya/datastructures2018

Materials for JHU Data Structures 2018

JHU EN.600.226: Data Structures

Prof: Michael Schatz (mschatz @ cs.jhu.edu)
Head TA: Tim Kutcher (tkutche1 @ jhu.edu)
Class Hours: Monday + Wednesday + Friday @ 1:30p - 2:45p in Mudd 26

Office Hours

Contact	Title	Office Hours	Location
Michael Schatz	Professor	Wednesday 3-4 PM, and by appointment	Malone 323
Tim Kutcher	Head TA	Tuesday 6-7 PM, Thursday 12-1 PM	Malone 122 (Ugrad Lab)
Brandon Lim	CA	Mondays 11 AM - 1:30 PM	Malone 122 (Ugrad Lab)
Joanna Guo	CA	Sunday 4:15-6:15 PM	Malone 122 (Ugrad Lab)
Taha Baig	CA	Wednesday 9:55-10:55 AM, Friday 9:55-10:55 AM	Malone 122 (Ugrad Lab)
Julia Oppenheim	CA	Thursday 4:30 - 5:30 PM, Friday 10 - 11 AM	Malone 122 (Ugrad Lab)
Randy Kuang	CA	Thursday 10:30 AM - 11:30 AM, Friday 11 AM - 12 PM	Malone 122 (Ugrad Lab)
Anil Palepu	CA	Tuesday 2 PM - 4:30 PM	Malone 122 (Ugrad Lab)
Darius Irani	CA	Thursday 7 PM - 9 PM	Malone 122 (Ugrad Lab)
Youngsoo Sung	CA	Tuesday 10 AM - 12 PM	Malone 122 (Ugrad Lab)
William Ruppenthal	CA	Wednesday 12 - 1 PM, Friday 12 - 1 PM	Malone 122 (Ugrad Lab)

---

The primary goal of the course is for students to be grounded in theory and leave the course empowered to understand and implement a variety of key data structures. This course covers the design and implementation of data structures including arrays, stacks, queues, linked lists, binary trees, heaps, balanced trees (e.g. 2-3 trees, AVL-trees) and graphs. Other topics include sorting, hashing, memory allocation, and garbage collection. Course work involves both written homework and Java programming assignments.

• Upon successful completion of this course, you should be able to:
  • Evaluate and compare the time complexity of functions using mathematical techniques.
  • Design an algorithm that produces the correct results according to specified inputs and time or space complexity constraints.
  • Understand the operation of common data structures and algorithms.
  • Use analysis techniques to choose the data structure/implementation appropriate for a given problem.
  • Write advanced object-oriented solutions in Java to significant problems, by implementing appropriate data structures and algorithms.

Prerequisites

• Class Prerequisities (Programming in Java is required)
  • EN.600.120 OR EN.601.220 OR EN.600.107 OR EN.601.107 or equivalent with C+ or better grades.
• Recommended Prerequisites
  • Code academy's Intro to Unix
  • Command line bootcamp

Course Resources:

• Syllabus and Policies
• Piazza Discussion Board
• Gradescope Entry Code: MDJYER
• Instructor materials (Authorized users only)

Recommended Readings

• Algorithms and Data Structures

  • Shaffer, Cliff: OpenDSA. Interactive online text. (An older version is available in print if you prefer that.)
  • Sedgewick, Wayne: Algorithms. Fourth Edition, Pearson, 2011. Also available online at JHU.
  • Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms. Third Edition, MIT Press, 2009. Also available online at JHU. (This text is often required for 600.363 / 463: Introduction to Algorithms.)
  • Weiss: Data Structures and Algorithm Analysis in Java Third Edition, Pearson, 2012.

• Programming in Java

  • Dean, Dean: Introduction to Programming with Java: A Problem Solving Approach. Second Edition, McGraw-Hill, 2013. (This text has recently served as the required text for 600.107: Introductory Programming in Java.)
  • Sestoft: Java Precisely. Third Edition, MIT Press, 2016.
  • Deitel, Deitel: Java How to Program. Ninth Edition, Pearson, 2012. Also available online at JHU.
  • Flanagan: Java in a Nutshell. Fifth Edition, O’Reilly, 2005.

Other Resources

• Algorithms and Data Structures

  • algoviz.org collection of visualizations for various data structures and algorithms

• Programming in Java

  • Java 8 API description of Java classes and methods
  • Code Examples from Intro Programming in Java (600.107); look in the sub-directories for examples of each topic.
  • Checkstyle Overview briefly discusses several issues around checkstyle that you may run into

• Unix and Linux

  • Joanne’s CS@JH Account Basics
  • Joanne’s Unix Overview describes key commands
  • An excellent Unix Tutorial
  • A printable Unix Reference Card
  • Learning emacs: Reference Card, Beginner’s Tutorial, GNU Emacs Tutorial, GNU Emacs Reference Card
  • Learning nano: Nano Tutorial, GNU Nano Website
  • Learning vi: Reference Card, Beginner’s Guide, Cheat Sheet Tutorial, Interactive Tutorial

Schedule

#	Date	Lecture	Readings & Resources	Assignment
1.	Th 8/30	Introduction		Sign Up for Piazza
2.	Fr 8/31	Interfaces	Java Interfaces	Set up VirtualBox
	Mon 9/3	Labor Day - No class
3.	Wed 9/5	Arrays, Generics, and Exceptions	Java Generics
4.	Fri 9/7	Lists	Java References	HW 1 Assigned
5.	Mon 9/10	Iterators	Nested Classes & Iterator Interface
6.	Wed 9/12	Complexity Analysis	Big O Cheat Sheet
7.	Fri 9/14	More Complexity		HW 2 Assigned
8.	Mon 9/17	Sorting	Sorting Algorithms Animations
9.	Wed 9/19	Stacks
10.	Fri 9/21	Stacks and JUnit	JUnit 4	HW3 Assigned
11.	Mon 9/24	Stacks, Queues, and Deques
12.	Wed 9/26	Lists
13.	Fri 9/28	More Lists		HW4 Assigned
14.	Mon 10/1	Trees
15.	Wed 10/3	Trees and Graphs
16.	Fri 10/5	Graph Search
17.	Mon 10/8	Midterm Review 1
18.	Wed 10/10	Midterm Review 2
19.	Fri 10/12	Midterm!
20.	Mon 10/15	Sets	Sets
21.	Wed 10/17	Midterm Discussion		HW5 Assigned
	Fri 10/19	Fall Break
22.	Mon 10/22	Ordered Sets
23.	Wed 10/24	Priority Queues and Heaps
24.	Fri 10/26	Sets of integers, bitsets		HW6 Assigned
25.	Mon 10/29	Maps
26.	Wed 10/31	BSTs and AVL Trees
27.	Fri 11/2	Treaps		HW7 Assigned
28.	Mon 11/5	Hash Tables
29.	Wed 11/7	More Hash Tables
30.	Fri 11/9	Advanced Hash Tables		HW8 Assigned
31.	Mon 11/12	Suffix Arrays
32.	Wed 11/14	Burrows Wheeler Transform & BWT Notes
33.	Fri 11/16	Burrows Wheeler Transform 2		HW9 Assigned
	Mon 11/19	Thanksgiving break
	Wed 11/21	Thanksgiving break
	Fri 11/23	Thanksgiving break
34.	Mon 11/26	Advanced sorting
35.	Wed 11/28	Linear time sorting, Topological sorting
36.	Fri 11/30	Shortest Path Problem		HW10 Assigned
37.	Mon 12/3	Minimum Spanning trees
38.	Wed 12/5	Union Find
39.	Fri 12/7	Last Day of Class - Review!
	Thr 12/13	Final Exam @ 9am - 12n -- Mudd 26