CSCI-UA 102 (Data Structures)

GTG = Data Structures and Algorithms in Java, Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser,
ODSA = Open DSA

end of chapter problems to look at

Date
Material Covered, Notes, Handouts and Links
Readings, Assignments, Homework


Wed., May 14

Final exams:

May 14, Monday, 8:00-9:50 am, room 109 CIWW


Class #28
Monday, May 7

Q & A for the final exam.

Topics covered:

  • advanced Java topics
    • inheritance and polymorphism
    • interfaces and abstract classes
    • exception handling
    • generics
  • lists (array based and reference based implementation)
  • stacks and queues (array based and reference based implementation)
  • algorithm analysis (big-O notation)
  • recursion
  • general trees (node structure, abstract view of the tree and the actual linkage between nodes, implementation of methods that traverse all or part of the tree)
  • binary trees
  • search trees
    • binary search tree
    • AVL trees
  • sort algorithms: mergesort, quicksort
  • priority queues and heaps (how it works, no implementation)
  • hash tables (how it works, no implementation)


Class #27
Wednesday, May 2

Hash maps, hash tables, how come they give us O(1) performance. General overview.

Lecture notes

Rec # 14
Tue, May 1

Problem sets


Class #26
Monday, April 30

Priority queues - overview

Lecture notes


Class #25
Wednesday, April 25

Quicksort

Quicksort visualization

Rec # 13
Tue, April 24


Class #24
Monday, April 23

Review of quadratic sorts. Merge sort.

Sort - lecture notes

Merge sort visualization


Class #23
Wednesday, April 18

Calculating heights and balance factor for the AVL tree. Node definition for an AVL tree. Performing rotations to restore balance.

Rec # 12
Tue, April 17


Class #22
Monday, April 16

Binary search trees: code for removing a node, using traversals to print the tree in a "tree format".

Balanced binary trees: AVL.

Project 5 (due April 28):


Class #21
Wednesday, April 11

Quiz: BST traversal

Binary search trees: adding a new node to the tree (recursive implementation), removing a node from the tree - three cases.

Rec # 11
Tue, April 10

Binary trees practice


Class #20
Monday, April 9

Binary search trees: searching for a node (iterative and recursive implementation), performance of the search algorithm, adding to the tree.


Class #19
Wednesday, April 4

Binary trees, tree traversals, intro to BST.

Introduction to trees - lecture notes

Binary search trees (BST) - lecture notes

Reading: chapters 8, 11

Rec # 10
Tue, April 3

Interview Questions


Class #18
Monday, April 2

Tree data structure.

Project 4: due April 11 at 11:55pm
Familiarize yourself with the following code. Once you decide that you understand the code (how it works, what it does, how the particular abstract data types are implemented, what the performance is, …), you will take a quiz on NYU Classes that is based on the code. You should use the Javadoc documentation as well as the source code files for Java API that you downloaded at the beginning of the term. (For the purpose of the quiz, you will use the line numbering in the PDF documents of the code.)

Classes that implement stack and queue ADTs in Java API:

Code provided as application examples for stack and queues in the textbook:

  • The source code for solving matching parentheses and HTML tags in section 6.1.5 in the textbook.
  • The source code for Josephus class in section 6.2.4 in the textbook.


Class #17
Wednesday, March 28

Queue ADT, array-based and reference-based implementation of queues.

Reading: chapter 8 (followed by chapter 11).

Rec # 9
Tue, March 27

Test driven development (TDD) and JUnit - activity.

Number.java


Class #16
Monday, March 26

Stack ADT, array-based and reference-based implementation of stacks.

Stacks/queues lecture notes


Class #15
Wednesday, March 21

snow day

Rec # 8
Tue, March 20

Exam 1 and project 3 discussion.


Class #14
Monday, March 19

Finish recursion: generating sequences.

Recursion lecture notes

Algorithmic performance analysis: how efficient is an algorithm.

Project 3 (due March 29):

Class #13
Wed., March 7

Midterm exam.

Rec # 7
Tue, March 6

Review for the exam.


Class #12
Monday, March 5

Q&A for the exam.

Class #11
Wed., Feb. 28

More on recursion.

Rec # 6
Tue, Feb 27

Magic of Recursion

Class #10

Monday, Feb. 26

Q&A about the project: equals method for a list, clone method for a list.

Starting with recursion: what makes a function recursive, base case, recursive case, special cases (error handling), wrapper methods, actual recursive methods. Examples: factorial, calculate the sum of elements in an array, revers an array/string, compute x^y.

Reading: chapter 5 (lightly on performance, we will come back to it after spring break).

Rec # 5
Wed, Feb 21

Recitation during the regular lecture time.

Going over project 2.

Finding Code Responsible for Behavior - OPTIONAL, not submitted.

Class #9
Tuesday, Feb. 20

Lecture during the regular recitation time

Reference-based implementation of a list ADT: removing from the list, searching through the list. Other flavors of linked lists.

Project 2 (due March 3):


Monday, Feb. 19

No classes

Class #8
Wednesday, Feb. 14

Reference-based implementation of a list ADT: generic node structure, adding elements to the list.

Rec # 4
Tue, Feb 13

[ArrayList - case study](https://docs.google.com/document/d/1rUy8rThU8nRmDRfWL2KpCoJFodczJ5hGWWpR1fuUMuM/edit?usp=sharing)

Download source code fore Java OpenJDK 8.

Class #7
Monday, Feb. 12

Finish with array-based implementation of a list ADT: searching.

Reference based implementation of a list ADT.

Class #6
Wednesday, Feb. 7

Array-based implementation of a list ADT: adding and removing elements.

Rec # 3
Tue, Feb 6

  • project 1, part 2 overview - you should read the project specification before the recitaton
  • using debugger with Java programs

Class #5
Monday, Feb. 5

Review of advanced Java topics: inheritance, polymorphism continued.
Finish with the code examples.

List ADT. list lecture notes

Read chapter 7 (lightly)

Project 1, part 2:

Class #4
Monday, Jan. 31

Review of advanced Java topics: inheritance, polymorphism continued.

Goving over the code examples.

Rec # 2
Tue, Jan. 30

Bullet Proof Code.

Class #3
Monday, Jan. 29

Review of advanced Java topics: inheritance, polymorphism.

Code samples:

Start reading chapter 3 in GTG.

Continue working on chapter problems for chapters 1 and 2 (see above the table for the listing).

Project 1, part 1:
Familiarize yourself with the following code. The three files provide a simple implementation of a color converter (CSS named colors, RGB values, hex-representation). Once you decide that you understand the code (how it works, what it does, how the three classes interact, how the user interaction happens, how the file I/O works, …), you will take a quiz on NYU Classes that is based on the code. (For the purpose of the quiz, you will use the line numbering in the PDF documents of the code.)

Class # 2
Wednesday, Jan. 24

Review of advanced Java topics: code documentation - javadoc, classes, objects, references, inheritance and polymorphism.

PythonTutor visualization of the code examples

Rec # 1
Tue, Jan. 23

Warm-up activity.

Once you complete the activity, download it in PDF format: File -> Download As … -> PDF Document (pdf)

The completed PDF file should be submitted to Gradescope for grading (only one person from your group needs to submit the activity; you will have a chance to enter the names of all group members once you upload the file).

Here are quick steps for uploading to Gradescope:

  • Go to gradescope.com and log in with you NYU email address (the version that contains your NetID).
  • On your Courses page, select the course for which you’re submitting work.
  • On your Courses page, you will see all of your current assignments. Click on the assignment you are turning in.
  • Click Submit PDF > Click Select PDF > locate the correct file on your computer > Click Upload PDF
  • (When activity has multiple parts) Tell us which pages correspond to each part/question on the assignment. You will see a list of all the assigned parts/questions, and images of all your document pages. For each question click the page(s) that contains your answer.
  • Finally, add the group members to the submission: on the right hand side under the name of the person who submitted the assignment, you should see "Add Group Members" link. Use it to add up to 3 more student names to the submission. (If you skip this step the other group members won't get credit for their work.)

(If you did not receive email from Gradescope with an invitation to join the class, or if you happened to delete that email, you can join the class by creating an account and using 9WY62K as a class code.)

Submitting work on Gradescope

Make sure that you add all of your group members to the submission on Gradescope - it is not enough to have their names in the pdf.

Class # 1
Monday, Jan. 22

Introduction to the class: syllabus.
Review of advanced Java topics: definitions and examples of data structures and algorithms, software development process.

Code conventions for cs102

Lecture 1 notes

PythonTutor visualization of the code examples

Read chapters 1 and 2 in GTG.

Work on chapter problems for chapters 1 and 2 (see above the table for the listing).

If you do not have them already, install Java JDK 8 and Eclipse (the latest version is Neon). You must have Java JDK version 7 or 8. The prior version may lead to problems with your submissions and potential zero grade on projects. To see which version of JDK is installed on your machine:

  • in Eclipse: Window → Preferences → Java → Installed JRE's
  • in a terminal: javac -version should show "javac 1.8…." or "javac 1.7…"

Read the Code conventions document.