datastructures2018

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