Data Structures
CSCI 151, Fall 2022
This course builds upon the principles introduced in CSCI 150 and provides an algorithmic basis for further study in Computer Science. This is an introduction to the design and implementation of data structures (linked lists, stacks, queues, trees, heaps, hash tables, and graphs) and related algorithmic techniques (searching, sorting, recursion). It examines these ideas in the context of an object-oriented language, such as Java.
Students are expected to complete a number of programming projects illustrating the concepts presented.
Below you find the materials related to the course arranged according to the timeline. For up-to-date course announcements and information please refer to the blackboard course page.
Calendar
| Week 1 | Sept 2 | Introduction and Setup. Course mechanics.
Slides-intro. Class profiles: Section 10 AM. Section 11AM. |
| Hello, Java.
Read: Handout 1. DEMO Main program structure. Compiling and running Java programs. Code repo. |
||
| Week 2 | Sept 7,9 | Java Basics 1. Data Types. Variables. Arrays. Loops. Conditionals.
Slides 1.
DEMO Rolling a die. Sum. Code repo. |
| Homework 1 | Java for Python Programmers 1.
Watch: Converting a Simple Program. Conditional Execution and User Input. FOR Loops. Functions / Static Methods. Variable Scope. Read: Java for Python Programmers. Chapters 5-7. TASK Home Quiz 1: LINK. |
|
| Homework 2 | Java for Python Programmers 2.
Watch: Primitives, objects and references. Working with Strings. Creating classes. Adding methods to an object. Read: Java for Python Programmers: Chapter 8. TASK Home Quiz 2. LINK. |
|
| Week 3 | Sept 12 | Java Basics 2.
Static methods. Variable scope. Reference types. String and Scanner types (classes).
Slides 2.
DEMO Temperature Convertor. Delete Substring. Scanner. Code repo. |
| Sept 12, 13 | TASK Lab 0. Setup. Program Arguments. Eclipse IDE. LINK. | |
| Sept 14 | Classes and Objects. Defining new data types (classes). Data hiding and encapsulation. Constructors. Slides 3. | |
| Sept 16 | Reusing Objects 1/2.
Combining and extending existing classes: Composition. Inheritance.
Slides 4.
DEMO Designing with Composition: Hospital. Code repo. Designing with Inheritance: Animal Simulation. Code repo. |
|
| Week 4 | Sept 19 | Reusing Objects 2/2. Polymorphism. Abstract classes. Interfaces. Slides 4. |
| Sept 19, 20 | TASKLab 1. The First Cup of Java. Coding in Java. User input. LINK. | |
| Sept 20 | READ 1.1 - 1.3.* Due: Sept 20, 11:00 PM. | |
| Sept 21 | Basic data structures. Arrays and Linked Lists: 1/2. Array basics. Memory layout. Supported operations. Slides 5. | |
| Sept 22 | READ 2.1 - 2.5.* Due: Sept 22, 11:00 PM. | |
| Sept 23 | Basic data structures. Arrays and Linked Lists: 2/2. Linked List basics. Java Lists. Java Generics. Slides 6. | |
| Sept 23,24 | READ 2.6 - 2.8.* Due: Sept 25, 11:00 PM. | |
| Week 5 | Sept 26 | Algorithms: introduction. Input and output. Pseudocode. Slides 7. Running time as function of input size. Slides 8. |
| Sept 26, 27 | TASKLab 2. Object-oriented programming. Extending abstract classes. LINK. Due: Oct 2, 10:00 PM. | |
| Sept 27 | READ 3.1 - 3.5. Due: Sept 27, 11:00 PM. | |
| Sept 28 | Bounding functions. Asymptotic running time. Big-O. Rate of growth. Slides 9. | |
| Sept 29 | READ 3.6 - 3.8. Due: Sept 29, 11:00 PM. | |
| Sept 30 | Classifying algorithms by complexity. Practical and impractical algorithms. Complexity of operations on Array and Linked List. Slides 10. | |
| Sept 30 | READ 3.9 - 3.11. Due: Oct 2, 11:00 PM. | |
| Week 6 | Oct 3 | Recursive algorithms. Base case. Recursive step. Running time. Recursive data structures. Slides 11. |
| Oct 3, 4 | TASKLab 3. My ArrayList. Implementing ArrayList. Testing with JUnit. Javadoc comments. LINK. Due: Oct 9, 10:00 PM. | |
| Oct 3 | READ 3.12 - 3.16. Due: Oct 4, 11:00 PM. | |
| Oct 5 | Yom Kippur. No classes. | |
| Oct 7 | Recursive sorting. Merge Sort. Quick Sort. Slides 12. | |
| Oct 7 | READ 3.17. 4.1 - 4.3. Due: Oct 9, 11:00 PM. | |
| Week 7 | Oct 10 | Sorting in Java. Comparator and Comparable interfaces.
Slides 13.
DEMO Sorting Dogs using java comparators. Code repo [with bug fixed]. |
| Oct 10 | READ 5.3 - 5.11. Due: Oct 11, 11:00 PM. | |
| Oct 12 | Abstract Data Types (ADT) . List ADT. Implementing List ADT with Linked List. Slides 14. | |
| Oct 14 | TASKMidtern exam. Exam topics: LINK. Sample exam: LINK. | |
| Oct 15 | READ 5.12 - 5.17. Due: Oct 23, 11:00 PM. | |
| Week 8 | Oct 17-21 | Fall break: no classes |
| Week 9 | Oct 24 | More about Lists. Doubly-linked lists with sentinels. Iteration over general lists. Iterator pattern. Java Iterators. Slides 15. |
| Oct 24, 25 | TASKLab 4. My LinkedList. Implementing Linked Lists. Iterators. Experimenting with running time. LINK. Due: Oct 30, 10:00 PM. | |
| Oct 24 | READ W9. Stacks and queues. Due: Oct 25, 11:00 PM. | |
| Oct 26 | Stack and Queue ADT. Implementation using Arrays and Linked Lists. Slides 16. | |
| Oct 26 | READ W9. Introduction to trees. Due: Oct 27, 11:00 PM. | |
| Oct 28 | Introduction to trees. Motivation. Terminology. Tree traversals. Slides 17. | |
| Oct 28 | READ W10. Binary Search Trees. Due: Oct 30, 11:00 PM. | |
| Week 10 | Oct 31 | Binary Search Trees. Properties of Binary Search Trees (BSTs). Reading operations on BSTs. Slides 18. |
| O 31, N 1 | TASKLab 5.Simply A-Maze-ing!. Implementing Stack and Queue ADT using Linked List data structure. Maze traversals using Stack and Queue. LINK. Due: Nov 6, 10:00 PM. | |
| Oct 31 | READ W10. BST in Java. Due: Nov 1, 11:00 PM. | |
| Nov 2 | Update Operations on BSTs. Binary Search Trees: insertion and deletion. Slides 19. | |
| Nov 2 | READ W10. AVL trees. Due: Nov 3, 11:00 PM. | |
| Nov 4 | Balanced BSTs. Motivation. Tri-node restructuring (rotations). AVL trees. Slides 20. | |
| Nov 4 | READ W11. Set ADT. Due: Nov 6, 11:00 PM. | |
| Week 11 | Nov 7 | Idea of Hashing. Fast search with Direct Addressing.
Idea of a Hash table.
In search for a perfect hash function. Java String hashCode. Set and Map ADT.
Slides 21.
DEMO Fast set operations in Java. Code repo |
| Nov 7, 8 | TASKLab 6. Binary Trees. Implementing tree traversals. Implementing binary tree methods using recursion. LINK. Due: Nov 13, 11:00 PM. | |
| Nov 7 | READ W11. Hash Tables. Due: Nov 8, 11:00 PM. | |
| Nov 9 | Collision resolution techniques. Separate chaining. Open addressing: linear probing, quadratic probing and double hashing. Slides 21. | |
| Nov 9 | READ W11. Collisions. Priority Queue ADT. Due: Nov 10, 11:00 PM. | |
| Nov 11 | Priority Queue ADT. Supported operations. Slides 22. | |
| Week 12 | Nov 14 | Priority Queue ADT. Implementing Priority Queues using Binary Heaps. Storing Heap Tree in an Array. Slides 22. |
| Nov 14, 15 | TASKLab 7. My Tree Map. Balancing AVL trees: Tri-node restructuring (rotations). Map ADT with Balanced Binary Search Trees. LINK. Due: Nov 20, 11:00 PM. | |
| Nov 14 | READ W12. Binary heaps. Heapsort. Due: Nov 15, 11:00 PM. | |
| Nov 16 | Heap Sort. Sorting using heaps. Heapifying an array. Slides 23. | |
| Nov 16 | READ W12. Introduction to graphs. Due: Nov 17, 11:00 PM. | |
| Nov 18 | Graph ADT. Graph definitions. Slides 24. | |
| Week 13 | Nov 21 | Modeling with Graphs. Solving puzzles. Slides 24. |
| Nov 21 | READ W13. Graph traversals. Due: Nov 22, 11:00 PM. | |
| Nov 21, 22 | TASKLab 8. My Hash Map. Implementing a hash table with separate chaining. Million Monkeys with Typewriters: generating random texts. LINK. Due: Nov 30, 11:00 PM. | |
| Nov 23 | Subgraphs, paths and connectivity. Modeling with paths. Euler tour. Slides 25. | |
| Nov 25 | Thanksgiving break. No classes. | |
| Week 14 | Nov 28 | Implementing Graphs. Adjacency lists and adjacency matrices.
Slides 26.
Graph Traversals. Breadth-first search (BFS) and depth-first search (DFS) in graphs. Slides 27. |
| Nov 28 | READ W14. Topological sorting. Due: Nov 29, 11:00 PM. | |
| Nov 28, 29 | TASKLab 10. Everything is better with Bacon. Reading data from URL. Implementing Graph ADT. Breadth First Search. Shortest Path. Bacon Number. LINK. Due: Dec 9, 11:00 PM. | |
| Nov 30 | Minimum Spanning Trees. Algorithm by Prim. Algorithm by Kruskal. Slides 28. | |
| Nov 30 | READ W14. Min Spanning Trees. Due: Dec 1, 11:00 PM. | |
| Dec 2 | Shortest Paths. Shortest (min-cost) paths in weighted graphs. Dijkstra's algorithm. Slides 29. Activity: Dijkstra's algorithm. LINK. | |
| Dec 2 | READ W14. Dijksta's Shortest Path Algorithm. Due: Dec 4, 11:00 PM. | |
| Week 15 | Dec 5, 6 | TASKLab feedback. Please provide your feedback to the labs here: LINK. Due: Dec 3, 11:00 PM. |
| Dec 5 | TASKExam preparation. Exercises**: Graphs. Hash Tables. Priority Queues. Due: Dec 6, 11:00 PM. | |
| Dec 7 | Review 1. Graphs, hash tables, heaps. Play Game 1. | |
| Dec 7 | TASKExam preparation. Exercises**: Trees. Sequences. Algorithm basics. Due: Dec 8, 11:00 PM. | |
| Dec 9 | Review 2. Sequences, Queues, Trees. Play Game 2. | |
| Dec 9 | Exam preparation materials.
Abstract Data Types and Data Structures:
cheatsheet.
Exam topics and some notes: LINK. TASKSolve this sample final exam. Solutions to the sample final exam: LINK. | |
| *Unless specified otherwise, readings refer to the main course textbook. | ||
| **Auto-graded exercises are on Blackboard under the Exams. | ||