Programming Final Review

Front 1

AVL Tree v.s. Sorted Array

Back 1

Insertion and deletion in Search Array is O(n) and finding is O(log(n)). TVL Tree is worst case scenario O(n).

Front 2

What is Recursion?

Back 2

Basic programming technique used in java where a method calls itself to solve some problem.

Front 3

What is a recursive validity check, base case and recursive case?

Back 3

Validity check - If program is in fact recursive

Base Case - Case for which the solution can be stated non-recursively.

Recursive Case - The case for which the solution is expressed in terms of a smaller version of itself.

Front 4

How does bubble sort work?

Back 4

A stable sort. Considered a sinking sort. Compares adjacent object and the swaps so that the larger object is moved up. O(n^2).

Front 5

What is Selection Sort and how does it work?

Back 5

Combination of searching and sorting. While passing through the array the unsorted element is moved into its proper position. Selection sort is unstable. O(n^2).

Front 6

What is insertion sort and how does it work?

Back 6

In-Place comparison sorting algorithm. Sub-list is maintained which is always sorted. O(n^2).

Front 7

What is heap sort and how does it work?

Back 7

Comparison based sorting algorithm based on Binary Heap. Similar to selection sort. O(n log n).

Front 8

What is Big O notation?

Back 8

Used to describe the performance or complexity of an algorithm. Describes worst-case scenario and used to describe execution time required or space used by an algorithm.

Front 9

Big O measure of asymptotic complexity.

Back 9

Big O measure of asymptotic complexity.

Front 10

List.

Back 10

The order of data items is significant. Duplicate items are permitted. Abstract data type that represents a countable number of ordered values.

Front 11

Set.

Back 11

The order of the data items does not matter but duplicate items not permitted.

Front 12

Bag.

Back 12

A collection of objects where you can keep adding objects to the bag but you cannot remove objects once added.

Front 13

Generics.

Back 13

Generics enable types to be parameters when defining classes, interfaces, and methods.

Front 14

Benefits of generics.

Back 14

-Stronger type check at compile time.

-Elimination of casts.

-Enable programmers to implement generic algorithms.

Front 15

Can a generic be a primitive data type?

Back 15

No. Generic needs to be abstract data type.

Front 16

Difference between single and double link list.

Back 16

-Single link list has a pointer to the next node only.

-Double link list has a pointer to the previous and next node.

Front 17

What is a queue?

Back 17

A queue is a FIFO sequence (First In First Out). Insertion takes place only at the tale and removal takes place only at the head.

Front 18

What is a stack?

Back 18

A stack is a LIFO sequence (Last In First Out). Addition takes place only at one end called the top.

Front 19

What are the basic operations of a queue?

Back 19

-insert(x): add item at tail.

-remove(): remove the item at the head.

-peek: return the item at the head.

-size: return the number of items in the queue.

-isEmpty(): return whether the queue has no items.

Front 20

What are the basic operations of a stack?

Back 20

-push(x): add an item to the top.

-pop(): remove the item at the top.

-peek: return the item at the top.

-size: return the number of items in the stack.

-isEmpty: return whether the stack has no items.

Front 21

Tree:

Node.

Back 21

A data element in the tree.

Front 22

Tree:

Parent.

Back 22

The converse notion of a child.

Front 23

Tree:

Root.

Back 23

The top node in a tree.

Front 24

Tree:

Child.

Back 24

A node directly connected to another node when moving away from the root.

Front 25

Tree:

leaf.

Back 25

A node with no children.

Front 26

Tree:

Depth.

Back 26

The depth of a node is the number of edges from the tree's root node to the node.

Front 27

How to navigate a tree.

Back 27

Breadth-First: Goes level by level but requires a lot of storage.

Depth-First: Goes out as far as possible and backtracks, only requires as much storage space as the tree's depth.

Front 28

How to create an array.

Back 28

Array = new dataType[arraySize];

Front 29

How to declare array.

Back 29

dataType[] array;

Front 30

How to instantiate array.

Back 30

array[1] = 2.

Front 31

Difference between array and arraylist.

Back 31

-Resizable: Array is static in size while arraylist is dynamic in size.

-Primitives: ArrayList cannot contain primitive data types(int, float, double) it can only contain Object. Array can contain both primitive and objects.

-ArrayList is always single dimensional.

-ArrayList slow in comparison to array.

Front 32

O() of Array v.s. Linked List.

Back 32

Add:

Linked List - O(1)

Array - N/A

Remove:

Linked List - O(1)

Array - N/A

Front 33

Difference between Array and Linked List.

Back 33

-Linked List is dynamic in size and easy to insert and delete.

-Array is static in size.

-Linked List has to access elements sequentially starting from first node.

-Extra memory space for linked list pointer.

--Array has better cache locality that makes better performance.