CSCI-UA 102 (Data Structures)

Q&A for the final exam.

Come with questions.

Problem sets:

These problem sets are for the purpose of review for the final. You should attempt the problems before looking at the solutions.

• advanced Java topics, solutions
• recursion, solutions
• lists, stacks, queues, solutions
• searching and sorting, solutions
• trees, solutions
• more trees, solutions

Topics to review for the final:

• 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)
• 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
• priority queue, heap (how it works, no implementation)
• search trees
  • binary search tree
• iterators for lists and trees
• sort algorithms: mergesort, quicksort
• basics of hash tables (how it works, no implementation)
• performance results for all the discussed data structures and algorithms, big-O notation

Book sections that you are responsible for:

(Note, there may be parts in these sections that we did not discuss in class explicitly, or for which we used a different implementation.)

• chapter 1: all sections
• chapter 2: all sections
• chapter 3: all sections
• chapter 4: only parts related to big-O notation, no proofs
• chapter 5: sections 2 through 5
• chapter 6: sections 1, 2
• chapter 7: sections 1, 2, 4, 5, 6
• chapter 8: all sections (skip array-based representation of binary tree, and breadth-first traversal)
• chapter 9: sections 1-3 (you are not responsible for knowing how to implement it, but you should be able to read the code that implements it)
• chapter 11: section 1
• chapter 12: sections 1, 2
• chapter 10: sections 1, 2 (very lightly)

Hash tables.

hash tables notes

Sorting: quicksort (algorithm, implementation, performance).

Sorting: review of quadratic sorts, merge sort (algorithm, implementation, performance).

sort notes

Finish with binary search trees.

Project 6 - discussion.

Implementation of the remove operation for the binary search tree.

Adding elements to the binary search tree: recursive and iterative implementations.

Removing elements from the binary search tree: how does it work for leaves, nodes with one child, nodes with two children.

Introduction to binary search trees. Searching for a value in a binary search tree (algorithm, recursive vs iterative implementations, performance analysis).

BST notes

Priority queues, heaps, heap properties (invariants), adding values to a binary heap, removing values from a binary heap.

Introduction to tree and binary tree data structure. Node structure for a binary tree. Writing functions that calculate the size of a binary tree (recursive and iterative algorithms).

tree notes

Finish with recursion. Calculating size of a linked list recursively. Designing a recursive method to add a node to a linked list.

Basics or recursive backtracking: generating all binary sequences with a given length, generating binary sequences with a given length that meet a particular restriction (ex., no zero bit in the second position).

Think about: how to generate decimal sequences?, how to generate alphabetic sequences?

Introduction to recursive functions. What makes a function recursive? Base case. Error handling / parameter validation in recursive functions. Examples of recursive functions: calculating sum of digits in a positive number, calculating a^n using O(n) and O(long n) algorithms, factorial calculation, Fibonacci sequence calculation (and why it is very inefficient to do it using recursion), determining if a string is a palindrome.

recursion notes

Finish with array-based and linked-based implementation of a queue.

Look at the sample code providing array-based implementation of stack and queue ADTs.

Stacks: abstract data type, operations: add/push, remove/pop, top.

Queues: abstract data type, operations: add/enqueue, remove/dequeue.

Efficient array based implementation for stack and queues (all operations should be O(1)).

Efficient reference (linked-list) based implementation for stacks.

Algorithmic analysis: big-O notation. Array based list and linked-list performance analysis.

Q&A for midterm exam.

Come with questions.

Legislatie day: classes follow Monday schedule

Equivalence testing and cloning data structures.

Iterators.
Collection and List interfaces in Java.

list notes

Linked list: adding / removing elements, retrieving elements stored at a particular "index", efficiency concerns.

Linked lists. Node structure and node manipulation. Calculating size of a linked list; iterating over a list; recognizing the end of a linked list; special case of an empty list.

Continue with an array-based implementation for the List ADT. Case study of ArrayList<E> class.

Input stream buffering. How do nextLine(), next(), nextInt(), … functions of the Scanner class differ. How to handle not well behaved users.

List ADT. How is ArrayList<E> implemented.

Continue with code examples.

Polymorphism, dynamic binding, abstract classes.

Quiz 1.

Continue with advanced Java topics: inheritance, constructor chaining, overloading vs. overriding.

Review of code examples.

Advance Java concepts: reference variables vs. objects, inheritance, this vs. super, constructor chaining, …

Lecture 1 notes

PythonTutor visualization of the code examples

Introduction to the class. Syllabus. What do software engineers do.