CSCI325: Data Structures

Updated 2021-12-15

# Final Test. Wednesday, 12/15/2021

·         Test shell

# Day 30. Thursday, 12/09/2021

·         More history

·         More programming language popularity

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

·         Java interview questions

·         The Joys of the Craft

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

·         Java Collections review.

·         Final test topics to know.

·         Practice test. Solution.

·         Topological sort solution

·         Complete online evaluations

# Day 29. Tuesday, 12/07/2021

·         Saving the world. Saving the world, part 2.

·         Interesting article. More. More.

·         Merry Christmas

·         Chapter 28: Hashing. Notes.

·         None.

# Day 28. Thursday, 12/02/2021

·         Interesting

·         More graphs

·         Chapter 30: Graphs. Notes.

·         Discuss Liang's graph implementation. GraphDemo program.

·         Discuss topological sort program. We will do part 1 of the Topological Sort problem in class today.

#### Homework due Tuesday:

·         Program #27: Topological Sort. Data file. 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).

# Day 27. Tuesday, 11/30/2021

·         Prediction. Clean code. Traveling salesman problem.

·         Chapter 30: Graphs. Notes.

·         Discuss Liang's graph implementation. GraphDemo program.

·         Discuss topological sort program.

#### Homework due Thursday (part 1):

·         Program #26 deadline has been extended to Thursday.

# Day 26. Tuesday, 11/23/2021

·         Binary search trees: Notes

#### Assignment due next class

·         Program #26: Binary search trees and Morse Code. Instructions. Data files: prog26--morsecode.txt. prog26--message.txt.

·         Read chapter 30: Graphs. Expect a quiz.

# Day 25. Thursday, 11/18/2021. Sorting, efficiency

·         JDK is free

·         New version of TypeScript

·         Run-time complexity

·         Correction to search run-time numbers: Search demo code. Test results.

·         Sorting: Notes. Sort demo code.

·         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.

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

# Day 24. Tuesday, 11/16/2021. Efficient algorithms

·         How to code like a NASA programmer.

·         Finish Chapter 23. Maps. Notes.

·         Chapter 24. Developing Efficient Algorithms. Notes.

·         Sample files for searching: Random100000.txt, Random200000.txt, Random400000.txt, Random800000.txt, Random1000000.txt

#### Homework due next class:

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

# Day 23. Thursday, 11/11/2021

#### Homework:

·         Read chapter 24: Developing Efficient algorithms.

# Day 22. Tuesday, 11/09/2021

·         Chapter 23. Sets and Maps. Notes.

#### Homework:

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

·         Program #24 (postponed—not due until 11/18): Counting word frequencies in text. Description. Data file. Java file.

# Day 21. Thursday, 11/04/2021

·         Queues, bank simulation

#### Homework due 11/09:

·         Program #21: Queue simulation: Bank tellers.

·         Read chapter 23: Sets and Maps.

# Day 20. Tuesday, 11/02/2021

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

·         Sample programs:

·         22.7 TestQueue.java

·         22.8 PriorityQueueDemo.java

·         22.9 EvaluateExpression.java.

#### Homework due next class:

·         Program #20: Sundays

·         Read chapter 23: Sets and Maps.

# Day 19. Thursday, 10/28/2021

·         Remove Duplicates code with errors

·         Test 2 will be Tuesday, November 9, through chapter 22

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

#### Homework:

·         Program #19: 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. Tuesday, 10/26/2021

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

·         TestCollections: Listing 22.1

·         TestIterator: Listing 22.2

·         Abstract class explanation

·         Interface explanation

#### Homework:

·         Program 18. Mazes, robots, and stacks, part 1. Part 1 involves writing the Maze class and the Robot class and is due Thursday. 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. Thursday, 10/21/2021

·         Files and Exceptions programs. File.

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

·         Create an ArrayList of strings, ints.

·         Create a generic stack class.

#### Homework due next class:

·         Program #17: 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. Tuesday, 10/19/2021. Chapter 21: Generics & ArrayLists

·         Bogus missing return statement error message

·         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/12/2021. 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

·         Program #15: Recursion.

# Day 14. Thursday, 10/07/2021

·         News: Programming language popularity

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

#### Homework

·         Program #14: Text files and exceptions.

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

# Day 13. Tuesday, 10/05/2021

·         Chapter 10: Thinking in Objects. Notes.

#### Homework due next class:

·         Program #13: MyInt wrapper class.

# Day 12. Thursday, 9/30/2021

·         More Chapter 9: Strings. Notes.

·         Input files: YankeeNames.txt, Numbers.txt, YankeeNamesAndNumbers.txt

·         Hangman

#### Homework due next class:

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

·         Read chapter 10: Thinking in Objects

# Day 11. Tuesday, 9/28/2021

·         Chapter 9: Strings. Notes.

·         Converting int to hex

·         The Character class

#### Homework due next class:

·         Program #11: Strings: ISBN numbers.

·         Read chapter 10: Thinking in Objects

# Day 10. Thursday, 9/23/2021

·         Test #1. Chapters 1-8

·         Main program file for test. Copy this text file into your main program.

#### Homework due next Tuesday:

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

# Day 9. Tuesday, 9/21/2021

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

·         Test #1 will be next class, 9/23/2021. Objectives. Practice Test. Solution (code). Video 1, Video 2, Video 3.

#### Homework due AFTER the test (due next Tuesday)

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

# Day 8. Thursday, 9/16/2021

·         Chapter 8, part 2: Static variables and methods and the Rational class. Notes.

#### Homework due next class

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

# Day 7. Tuesday 9/14/2021

·         Java interview questions: Find missing element in an array

·         Chapter 8, part 1: Objects. Notes

·         Objects: Write a Fraction 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 #8: Create a RegularPolygon class.

# Day 6. Thursday, 9/09/2021

·         First test will probably be 9/23 over chapters 1-8.

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

#### Homework due next class

·         Program #7 (Chapter 7—2D arrays): Tic-Tac-Toe

·         Read Chapter 8 (Objects and classes).

# Day 5. Tuesday 9/07/2021

·         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).

·         Watch the sorting algorithms. Another

#### Homework due next class

·         Read chapter 7, 2D arrays

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

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

# Day 4. Thursday 9/02/2021

·         30 Software Engineering Skills that Employers Everywhere Want

·         Methods. Chapter 5 notes: methods.

#### Homework due next class

·         Program #5 (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/31/2021

·         Chapter 3 notes. Selection.

·         Chapter 4 Notes. Repetition.

·         In class: Fizz Buzz

#### Homework due next class:

·         Read chapter 5. Be prepared for a quiz.

·         Program #3—selection: Day of week. Zip the folder and put it in the drop box.

·         Program #4—repetition: Loan comparison. Zip the folder and put it in the drop box.

# Day 2. Thursday 8/26/2021

·         Chapter 2 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/24/2021. 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