CSCI325: Data Structures

Updated 2019-12-09

Syllabus        Java Tutorial        Java Collections Tutorial        Interpreting Java compile errors        Java Tutorial        Book source code        Finals Schedule        Academic Calendar

Final Test is Monday, 12/09/2019 at 10:00.

30 days in 2015   29 in 2017   28 in 2019 (1 snow day, 1 funeral)

Final test

Day 28. Thursday, 12/05/2019

·         Interesting article: Microsoft and 4K sector hard drives.

·         Java Collections review.

·         Data structure: B-trees. Notes. Another B-tree link

·         Final test topics to know.

·         Practice test. Solution.


Earlier classes are below…









Day 27. Tuesday, 12/03/2019

·         Interesting web site: Project Euler

·         Interesting article

·         Chapter 28: Hashing. Notes.

Homework due Thursday (part 2)

·         Program #23: Topological Sort, Part 2: Finish the program by implementing the topological sort algorithm

·         Optional extra credit due Monday at 9:30 a.m. Counting Sundays.

Tuesday, 11/26/2019: Snow day

Day 26. Thursday, 11/21/2019

·         Graphs quiz. Image.

·         Chapter 30: Graphs. Notes.

·         Discuss Liang's graph implementation. GraphDemo program.

·         Discuss topological sort program.

Homework due Tuesday (part 1)

·         Program #22: Topological Sort. Part 1. Use the GraphDemo program above as your starting point. You will have to delete most of the main program, but will use the Graph, AbstractGraph, and UnweightedGraph files (which are all included). Part 1: Write the code in main to create the graph from the data file. You may work with a partner (one) if you wish.

Day 25. Tuesday, 11/19/2019

·         Binary search trees: Notes

Assignment due next class

·         Program #21: Binary search trees and Morse Code. Instructions. Data files: MorseCode.txt. Message.txt.

·         Read chapter 30: Graphs. Expect a quiz.

Day 24. Thursday,.11/14/2019. Sorting,

·         How Quicksort works

·         How Heapsort works

·         Sorting: Notes.

·         Comparison in Java.

·         Visualization 1. Visualization 2. Visualization 3 (15 in 6 minutes). Visualization 4

Assignment due next class:

·         Read chapter 27: Binary search trees. Expect a quiz.

Day 23. Tuesday, 11/12/2019. Efficient algorithms

·         How to code like a NASA programmer.

·         Chapter 24. Developing Efficient Algorithms. Notes. Sort demo.

·         1,000,000 sorted. 1,000,000 unsorted.

Homework due next class:

·         Read Liang chapter 25: Sorting.

·         Program #20: TreeMaps, TreeSets: A Java cross-referencer. Java reserved words. Short Java program. Answers. Long Java program without comments. Answers

Day 22. Thursday, 11/07/2019

·         Test #2 shell

Day 21. Tuesday, 11/05/2019

·         Chapter 23. Sets and Maps. Notes.

Homework due the class AFTER the test (11/12/2019)

·         Test will be next class. Things to know. Practice test.

·         Program #19: Counting word frequencies in text. Description. Data file. Java file.

·         Read chapter 24: Developing Efficient algorithms.

Day 20. Thursday, 10/31/2019

·         Chapter 22. Comparators, Queues, Priority Queues. Notes.

·         Sample programs:

·         22.7

·         22.8

·         22.9 Notes

Homework due next class:

·         Program #18: Queue simulation: Bank tellers.

·         Read chapter 23: Sets and Maps.

Day 19. Tuesday, 10/29/2019

·         Test a week from Thursday through chapter 22

·         Chapter 22. Java Collections continued: Lists and Stacks. Notes.

Homework due Thursday:

·         Program #17: Mazes, robots, and stacks, part 2. Part 2 involves writing the stack of Direction class and writing the algorithm for stepping through the maze. Instructions. Data file. Maze and Robot classes.

Day 18. Thursday, 10/24/2019

·         Chapter 22. Java Collections, Lists and Stacks. Notes.

·         TestCollections: Listing 22.1

·         TestIterator: Listing 22.2

·         Abstract class explanation

·         Interface explanation

Homework due next class:

·         Program 16. Mazes, robots, and stacks, part 1. Part 1 involves writing the Maze class and the Robot class. Part 2 is the remainder of the program and the next assignment. It will be due one week from today. Instructions. Data file. Direction enumeration. Maze interface. Robot interface.

Day 17. Tuesday, 10/22/2019

·         Jobs in IT: Guest speaker from Interstates

·         Arraylists and a generic stack class: Notes. Examples.

·         Create an ArrayList of strings, ints.

·         Create a generic stack class.

Homework due next class:

·         Program #15: Write a generic removeDuplicates to return a new ArrayList that has all of the elements in the original ArrayList, but with no duplicate elements. Problem description.

·         Read chapter 22: Lists, Stacks, Queues, and Priority Queues

Day 16. Thursday, 10/17/2019. Chapter 21: Generics & ArrayLists

·         Code that changed the world

·         Chapter 21. Generics: Notes Make notes available after class. Write code from scratch in class.

·         Create an IntStack class, a StringStack class, and an ObjectStack class.

Optional Extra Credit due next class:

·         You should get used to reading Java documentation. Read about Java's BigInteger class before writing Mersenne primes. You can use this to take the place of your lowest score.

Day 15. Tuesday, 10/15/2019. Chapter 20: Recursion

·         Chapter 20: Recursion. Notes.

·         Problem that lends itself to a recursive solution: Towers of Hanoi

·         Examples of recursion (videos): Flood-fill, fractal, Koch Snowflake

·         Examples of recursion (Java code): Directory size, Sierpinski triangles, Towers of Hanoi

Homework due next class

·         Read chapter 21: Generics.

·         Program #14: Recursion.

Day 14. Tuesday, 10/08/2019

·         Chapter 14: Exceptions and text I-O. Notes.


·         Program #13: Text files and exceptions.

·         Read Chapter 20--Recursion.

·         NOTE: We are skipping chapters 11-13, 15-19.

Day 13. Tuesday, 10/01/2019

·         What employers want.

·         Chapter 10: Thinking in Objects. Notes.

Homework due next class:

·         Program #12: 10.3 MyInteger object. Write the MyInteger class described on page 366 and a main program that thoroughly tests all of the methods. Note: My program to test the class was 26 printf statements. On all of the Boolean methods, be sure to test for both true and false.

Optional Extra credit homework due Friday, 10/13/2019 at midnight

Day 12. Thursday, 9/26/2019

·         More Chapter 9: Strings. Notes.

·         Input files

Homework due next class:

·         Program #11: Strings and files: Hangman. 3000-word data file. Sample session.

·         Read chapter 10: Thinking in Objects

Day 11. Tuesday, 9/24/2019

·         Chapter 9: Strings. Notes.

Homework due next class:

·         Program #10: Strings: ISBN numbers. Put in the drop box. Data file.

·Read chapter 10: Thinking in Objects

Day 10. Thursday, 9/19/2019

·         Test #1. Chapters 1-8

·         Main program file for test

Homework due AFTER the test (due next Tuesday)

·         Program #9: More objects: a date class.

·         Read about strings Liang9, chapter 9.

Day 9. Tuesday, 9/17/2019

·         Objects, continued: Create the Huge integer class. Write test code. Notes.

·         Test #1 will be next class, 9/19/2019. Objectives. Practice test. Solution. Video 1. Video 2.

Homework due AFTER the test (due next Tuesday)

·         Program #9: More objects: a date class.

·         Read about strings Liang9, chapter 9.

Day 8. Thursday, 9/12/2019

·         Objects!!! Static variables and methods and the Rational class. Notes.

·         Huge integer class. Notes

Homework due next class

·         Program #8: Create and test an Account class.

Day 7. Tuesday 9/10/2019

·         Java interview questions: Find missing element in an array

·         Chapter 8, part 1: Objects. Notes

·         Objects: Write a Rational number class in class.

·         NOTE: to add JavaDocs to a method that you write, you must put a comment on the line above the method that begins with the three characters: /**

Homework due next class

·         Program #7: Create a RegularPolygon class.

Day 6. Thursday, 9/05/2019

·         First test will probably be 9/19.

·         Bean machine in action (scroll down to the video)

·         Watch the sorting algorithms. Another

·         2D Arrays (Liang9, chapter 7). Notes

·         2D array practice

Homework due next class

·         Program #6 (Chapter 7—2D arrays): Weekly Hours. Data file. Finish the TicTacToe problem. You may assume that the user will always enter a valid row and column number (let's allow the user to enter 1-3 instead of 0-2) and that the cell specified by the user will be unused.

·         Read Chapter 8 (Objects and classes).

Optional extra credit (also due next class)

Optional extra credit due next class

Day 5. Tuesday 9/03/2019

·         Source of programming problems: Project Euler

·         Fascinating article on game programming

·         Programming language popularity

·         Arrays in Java. Array notes. Random numbers file (1-1,000,000). Sorted numbers file (1-1,000,000). Random numbers file (1-100,000).

Homework due next class

·         Read chapter 7, 2D arrays

·         Program #5 (for chapter 6—arrays): Bean Machine

Day 4. Thursday 8/29/2019

·         Methods. Chapter 5 notes: methods.

·         Parameter passage in Java

Homework due next class

·         Program #4 (for chapter 5—methods): Print a full-year calendar. Chapter 5 slides (go to slide 68).

·         Read chapter 6 (1-D arrays). Be prepared for a quiz.

Day 3. Tuesday 8/27/2019

·         Chapter 3 Notes (continued). Selection.

·         Chapter 4 Notes. Repetition.

·         In class: Fizz Buzz

Homework due next class

·         Read chapter 5. Be prepared for a quiz.

·         Program #3 (for Chapter 4--repetition): Loan comparison. Zip the folder and put it in the drop box.

Day 2. Thursday 8/22/2019

·         Chapter 2 notes

·         Chapter 3 notes

Homework due next class

·         Read chapters 3 & 4 of Liang. Be prepared for a quiz.

·         Program #2 (for Chapter 2--elementary programming): Wind chill. Zip the project folder and put it in the drop box.

Day 1. Tuesday 8/20/2019. Intro to Java.

·         Book example programs source code. Download these. We will look at them throughout the course.

·         Java program structure, console input/output, variables, identifiers, data types: Notes

Homework due next class

·         Program #1: Gross pay and net pay. printf reference. Zip the project folder and put the zipped folder in the drop box.

·         Read chapter 1 (Introduction) and chapter 2 (Variables/Assignments) of textbook.

·         Read, sign, and turn in: Assignment, Test, and Homework policies

















Optional (Fun) Extra Credit

Notes. Notes




Day 29. Thursday 12/05/2019

·         Java interview questions

Homework due next class:


Day 30. Thursday, 12/10/2019



Monday, 12/11/2019. Final Test