CSCI325: Data Structures

Updated 2021-12-15

Syllabus        Download Java        Download IntelliJ IDE        Setting the JKD in IntelliJ         printf reference        Java Tutorial        Java Collections Tutorial        Interpreting Java compile errors        Finals Schedule        Academic Calendar

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

Final Test is Wednesday, 12/15/21 at 10:00.

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

Earlier classes are below…

 

 

 

 

Day 29. Tuesday, 12/07/2021

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

·         Interesting article. More. More.

·         Merry Christmas

·         Chapter 28: Hashing. Notes.

Homework due Thursday:

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

·         Read chapter 28: Hashing.

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

·         Test #2. Download the program shell.

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

·         Read chapter 21: Generics.

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

·         Read Chapter 20--Recursion.

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

·         Read about strings Liang9, chapter 9.

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.

·         Read about strings Liang9, chapter 9.

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

Optional extra credit (also due next class)

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

Day 29. Thursday 12/09/2021

   x

   x

Homework due next class:

 

Day 30. Thursday, 12/11/2021

EXTRA.

 

Final Test

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Optional (Fun) Extra Credit

Notes. Notes

 

 

Homework