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
| 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 | Tuesday 12-1 PM, Tuesday 3:45-4:45 PM | Malone 122 (Ugrad Lab) |
| Taha Baig | CA | Monday 1:45-2:45 PM, Wednesday 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 1 - 2 PM, Sunday 4 - 5 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.
- 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
- Syllabus and Policies
- Piazza Discussion Board
- Gradescope Entry Code: MDJYER
- Instructor materials (Authorized users only)
-
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.
-
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
checkstylethat 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
| # | 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 | More Lists | ||
| 6. | Wed 9/12 | Iterators | ||
| 7. | Fri 9/14 | Junit and Complexity Analysis | HW 2 Assigned | |
| 8. | Mon 9/17 | Sorting | ||
| 9. | Wed 9/19 | Stacks | ||
| 10. | Fri 9/21 | Stacks and Queues | 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 | More Trees | ||
| 16. | Fri 10/5 | Graphs | ||
| 17. | Mon 10/8 | Midterm Review 1 | ||
| 18. | Wed 10/10 | Midterm Review 2 | ||
| 19. | Fri 10/12 | Midterm! | ||
| 20. | Mon 10/15 | Graph Searching | ||
| 21. | Wed 10/17 | Sets | 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 and BSTs | ||
| 26. | Wed 10/31 | 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 | Advances Hash Tables | HW8 Assigned | |
| 31. | Mon 11/12 | Suffix Arrays | ||
| 32. | Wed 11/14 | Burrow Wheeler Transform | ||
| 33. | Fri 11/16 | Burrow 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! | ||
| TBD | Final Exam |