CSCI-UA 102 (Data Structures)

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

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

Final exams:

section 5: Dec. 18, Monday, 2:00-3:50 pm, room 109 CIWW

section 3: Dec. 19, Tuesday, 10:00-11:50 am, room 101 CIWW




Wed, Dec. 13 (sec. 5)
Thu, Dec. 14 (sec. 3)

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
  • binary trees
  • priority queues and heaps
  • search trees
    • binary search tree
    • AVL trees
  • hash tables



Tue, Dec. 12 (both classes)

Mixed problems - review exercises activity

Extra problem sets for practice (if you find any errors in the solutions, post a comment about it on Piazza):


Mon, Dec. 11 (both classes)

Finish with basics of hash tables.

Lecture 9: Hash tables

Reading: chapter 10


Wed, Dec. 6 (sec. 5)
Thu, Dec. 7 (sec. 3)

Introduction to hash tables



Mon, Dec. 4,
Tue, Dec. 5

Finish with O(N logN) sorts. .


  • start reading chapter 10

Recitation
Mon, Nov. 27
Tue, Nov. 28

Sorts - practice activity



Wed, Nov. 29 (sec. 5)
Thu, Nov. 30 (sec. 3)

Quick sort

Quicksort visualization



Mon, Nov. 27,
Tue, Nov. 28

Merge sort.

Merge sort visualization



Lecture 8 notes


Reading: chapter 12

Recitation
Mon, Nov. 27
Tue, Nov. 28

Quadratic sorts - review activity



Wed, Nov. 22 (sec. 5)
Thu, Nov. 23 (sec. 3)

No Classes



Mon, Nov. 20,
Tue, Nov. 21

Balance factor calculation, rebalancing the tree using RR, LL, RL and LR rotations, incorporating rotations into add/remove functions.

AVL tree visualization


  • start reading chapter 12

Project 5 (due Dec. 7 at 11:55pm)

Recitation
Mon, Nov. 20
Tue, Nov. 21

BST - Analyzing Incorrect Solutions to Problems activity



Wed, Nov. 15 (sec. 5)
Thu, Nov. 16 (sec. 3)

Balanced binary search trees, methods for balancing an ordinary BST, introduction to AVL trees, calculating height of nodes in a tree, AVL tree node definition.



  • chapter 11 problems to work on (not submitted): 11.1-6, 11.8-9, 11.11, 11.13, 11.28, 11.29, 11.33

Mon, Nov. 13,
Tue, Nov. 14

Adding, removing nodes from a binary search tree.

Lecture 7 notes


Recitation
Mon, Nov. 13
Tue, Nov. 14

Practice Problems: Binary Search Trees activity



Wed, Nov. 8 (sec. 5)
Thu, Nov. 9 (sec. 3)

Binary search trees, definition, finding items in the tree, adding/removing from the tree.



  • start reading chapter 11 in GTG

Tue, Nov. 7 (both sections)

Heap-sort - first O(n logn) sort. Review of selection sort.

Starting with binary search trees.


Project 4 (due Nov. 14 at 11:55pm)

Recitation
Mon, Nov. 6 (both sections)

Priority Queues and Interview Questions activity,


Wed, Nov. 1 (sec. 5)
Thu, Nov. 2 (sec. 3)

Priority queue: definitions, applications and implementation considerations.
Heaps as implementation of a priority queue: max-heap, min-heap, order property, shape property, adding, removing, building a heap.

Lecture 6 notes



  • start reading chapter 11 in GTG

Mon, Oct. 30 (sec. 5)
Tue, Oct. 31 (sec. 3)

Binary trees. Definitions for a node in a binary tree and in a general tree. Counting number of nodes in trees (recursive implementation). Tree traversals.


  • finish reading chapter 8 in GTG

  • chapter 8 problems to work on (not submitted): 8.1, 8.2, 8.5, 8.7, 8.8, 8.10, 8.11, 8.18, 8.19, 8.22, 8.36, 8.37, 8.41, 8.42, 8.45, 8.52, 8.59, 8.62, 8.65

  • start reading chapter 9 in GTG

  • chapter 9 problems to work on (not submitted): 9.1, 9.3-7, 9.9-11, 9.13-15, 9.17, 9.19-20, 9.23, 9.25-27, 9.33, 9.38-39, 9.44, 9.46, 9.50, 9.55

Recitation
Mon, Oct. 30 (sec. 4)
Tue, Oct. 31 (sec. 6)

Binary Tree Traversals activity ,



Wed, Oct. 25 (sec. 5)
Thu, Oct. 26 (sec. 3)

Introduction to trees, terminology and definitions.

Lecture 5 notes



Mon, Oct. 23 (sec. 5)
Tue, Oct. 24 (sec. 3)

Queue ADT. Array based and linked-list based implementation of the queue.


  • finish reading chapter 6 in GTG

  • chapter 6 problems to work on (not submitted): 6.1, 6.3-5, 6.7, 6.9, 6.12, 6.17-20, 6.26-29, 6.35-36, 6.38-39

  • start reading chapter 8

Project 3 (due Nov. 4 at 11:55pm)

Recitation
Mon, Oct. 23 (sec. 4)
Tue, Oct. 24 (sec. 6)



TestDrivenDevelopment activity ,

Number.java


Wed, Oct. 18 (sec. 5)
Thu, Oct. 19 (sec. 3)

Stack ADT. Array based and linked-list based implementation of the stack.

Lecture 4 notes


  • chapter 6 in GTG
  • chapter 9 in OpenDSA


Tue, Oct. 17

Midterm Exam.

sec. 3 at 11:00am in room 101 CIWW

sec. 5 at 12:30pm in room 109 CIWW


Mon, Oct. 16 (sec. 5 lecture)
(sec. 3 lecture instead of recitation)

Exam Q&A

  • come with questions/topics that you would like to be discussed. Post the questions on Piazza as a follow-up to the "Q&A for Exam" topic so we can prioritize more popular questions.



sample exam

Wed, Oct. 11 (sec. 5)
Thu, Oct. 12 (sec. 3)



More on recursion.

  • Coding Bat recursion 2 problems - short recursive practice problems with tests to check them (these are slightly more challenging than the ones in the first set)

Tue, Oct. 10 (sec. 3 lecture)
(sec. 5 lecture instead of recitation)

Recursion: simple examples, base case, recursive case, tracing recursion, iterative vs. recursive solutions

Lecture 3 notes
lecture 3 source code, processing library - for use with fractals


  • finish reading chapter 5

  • chapter 5 problems to work on (not submitted): 5.1-5, 5.7-10, 5.13, 5.16 (optional), 5.17, 5.18, 5.24-26

  • Coding Bat recursion 1 problems - short recursive practice problems with tests to check them


Mon, Oct. 9

FALL BREAK - no classes (no office hours, no tutoring hours)



Recitation # 4
Mon, Oct. 2 (sec. 4)
Recitaton # 5
Tue, Oct. 3 (sec. 6)



Debugging activity, debugging1.zip, Example.java

Class # 8
Thu, Sep. 28 (sec. 3)
Mon, Oct. 2 (sec. 5)

Asymptotic analysis: how fast is a function, String vs. StringBuilder performance, Big-O notation, examples of algorithms with different performance: O(logN), O(N), O(NlogN), O(N^2).

  • start reading chapter 5

  • chapter 4 problems to work on (not submitted):4.2, 4.3, 4.6, 4.8-13, 4.22, 4.28-33, 4.40, 4.42, 4.45, 4.46, 4.47, 4.55, 4.56.

Class # 7
Tue, Sep. 26 (sec. 3)
Wed, Sep. 27 (sec. 5)

Singly linked list implemetnation design and operations.

  • debugging methodologies and how to do it in Eclipse: OpenDSA, sec. 3.5, 3.6 (skip the Debugging A Memory Pool)

  • read chapter 4 in GTG

  • chapter 3 problems to work on (not submitted): 3.1, 3.5, 3.6, 3.8-12, 3.15, 3.16, 3.17, 3.18, 3.20, 3.23-29, 3.32, 3.35, 3.36, 3.39, 3.40

Recitation # 3
Mon, Sep. 25 (sec. 4)
Recitaton # 4
Tue, Sep. 26 (sec. 6)



Iterating Over Things activity.

Class # 6
Thu, Sep. 21 (sec. 3)
Mon, Sep. 25 (sec. 5)

List ADT, array-based implementation of a list, creating linked structures using nodes.

Lecture 2 notes

Project 2 (due Oct. 8 at 11:55pm)

Class # 5
Tue, Sep. 19 (sec. 3)
Wed, Sep. 20 (sec. 5)

Finish with Race examples, see lecture01.zip.

Recitation # 2
Mon, Sep. 18 (sec. 4)
Recitaton # 3
Tue, Sep. 19 (sec. 6)

Project 1 discussion.

Bullet Proof Code activity

Class # 4
Thu, Sep. 14 (sec. 3)
Mon, Sep. 18 (sec. 5)

Project 1 Q&A

Use of super keyword, inheritance, constructors accessible from subclasses (but not inherited), overriding methods of a superclass (how to access overriden methods), polymorphism - different types of reference and object (why do we do it).

Starting with Race code examples (see lecture01.zip ).

Start reading chapter 3 in GTG.

Class # 3
Tue, Sep. 12 (sec. 3)
Wed, Sep. 13 (sec. 5)

Review of file file IO.
Review (or introduction) to command line arguments and how to use them in your program.

Code samples:

Recitation # 1
Mon, Sep. 11 (sec. 4)
Recitaton # 2
Tue, Sep. 12 (sec. 6)

Project 1 discussion.

Download source code fore Java OpenJDK 8.

Finding code responsible for behavior activity

Class # 2
Thu, Sep. 7 (sec. 3)
Mon, Sep. 11 (sec. 5)

Lecture 1 continued: stages of software development, object oriented concepts, static vs. instance data fields and methods, composition, inheritance, this and super keywords.

Project 1 (due Sept. 18 at 11:55pm)

  • project specification
  • CSS color names data file - this is an example of a file that your program should accept as a command line argument (keep in mind that your program might be tested with a different file)

Rec # 1
Tue, Sep. 5 (sec. 6)

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
  • (Only if activity has multiple pars) 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 9R84E9 as a class code.)

Class # 1
Tue, Sep. 5 (sec. 3)
Wed, Sep. 6 (sec. 5)

Introduction to the class: syllabus.
Review of advanced Java topics.

Code conventions for cs102

Lecture 1 notes

PythonTutor visualization of the code examples we did in class

Read chapters 1 and 2 in GTG.

Chapter 1 problems to work on (not submitted): 3, 4, 7, 8, 9, 15, 19, 21, 23, 25, 27, 29 (and more if you can).
Chapter 2 problems to work on (not submitted): 1, 2, 7, 9, 10, 11, 12, 13, 17, 20, 21, 23, 25, 29, 30, 31, 32, 34, 35

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.