Datastructures&algorithms

Front 1

what is a priority queue

Back 1

a data structure that has operations such as insert, and deleteMIN

Front 2

What are some uses for a priority queue

Back 2

operating system scheduling,

Front 3

how do you implement a priority queue

Back 3

-linked list, performing insertions at the front in O(1) and traversing the list, which requires O(N) time, to delete the min
-or keep the list sorted; which makes insertions expensive (O(N)) and deleteMins cheap (O(1))
-binary search tree. Gives O(log N) average running time for deleteMin and insertions
-Binary Tree Heap

Front 4

what is a heap

Back 4

-a binary tree that is full except for the lowest level which is full left->right a complete binary tree. (2^h + 2^h+1 -1 nodes)
-can be represented as an array (left child = 2 * I; right child 2 * I + 1)

Front 5

what is a heap-order property

Back 5

-allows operations to be performed quickly
-keeps minimum at the root
-to insert begin at next available leaf and if parent is smaller, swap...percolate up
-to delete swap the empty spot with the smaller child

Front 6

Typically what is the Big O of simple sorting algorithms...what about more complex ones

Back 6

N^2
NLogN
-generally measured by the number of comparisons and the number of swaps

Front 7

what is insertion sort good for

Back 7

almost sorted data

Front 8

when is quick sort at its worst

Back 8

for reverse sorted data

Front 9

what effects efficiency of a sort algorithm

Back 9

the number of inversions

Front 10

how do you measure efficiency in a sort algorithm

Back 10

-check the results of the algorithm of various data such as reversed, almost sorted, etc....
-count the number of comparisons (except for radix sort)

Front 11

how do you perform selection sort.
what is the Big O

Back 11

-find smallest then swap.
-i++
-O(N^2)

Front 12

What is the advantages of a heap sort

Back 12

-n-place and non-reccursive
-doesnt use multiple arrays
-best time to use is for extremely large data sets

Front 13

what are the disadvantages of a heap sort

Back 13

-slower than merge and quick sorts
-memory requirement is doubled when a second array is used to hold the sorted elements

Front 14

what is the Big O of the heap sort

Back 14

-heap sort is logn
-building a binary heap of n elements takes n time
-deleteMin takes logn time
-total running time is NLogN

Front 15

who created radix sort

Back 15

Harold H. Seward in MIT in 1954

Front 16

what is the Big O of radix sort

Back 16

O(N)

Front 17

what is one of the fastest sorting algorithms when implemented correctly

Back 17

radix sort

Front 18

advantages of radix sort

Back 18

-stable
-works in linear time unlike most sorts
-can handle large amounts of data without sacrificing time

Front 19

disadvantages of radix sort

Back 19

-can take up more space than other algorithms bc of additional sublist needed
-takes more time to write bc the code needs to be re-written for each type of data

Front 20

who developed the quicksort algorithm and why

Back 20

-C.A.R. Hoare in 1962 Soviet Union-sort words to be translated for easier matching between alreaded sorted Russian-to-English dictionary that was sorted on magnetic tape

Front 21

advantages of quicksort

Back 21

-best case is nlogn
-one of the fastest sorting algorithms that does not need additional memory
-simplicity

Front 22

who created merge sort

Back 22

-John von Neumann in 1945
-based on divide and conquer
-

Front 23

advantages of merge sort

Back 23

-worst case nlogn
-stable
-easily works with linked lists

Front 24

disadvantages of merge sort

Back 24

-may require an array up to size n

Front 25

how do you perform merge sort

Back 25

-combining sublists together

Front 26

what is a graph

Back 26

a set of vertices, V and a set of edges, E

Front 27

what are directed graphs called

Back 27

digraphs

Front 28

vertices w and v are adjacent if

Back 28

(v, w) 0 E

Front 29

an acyclic path is

Back 29

a directed graph that has no cycles

Front 30

the length of a path is

Back 30

the number of edges on the path

Front 31

what are some uses for graphs

Back 31

-utilities planning
-routing
-flowcharts
-computer networks
-electrical circuits

Front 32

what is the first known graph problem

Back 32

-konigsberg
-inspired by whether it is possible to walk with a route that crosses each bridge exactly once
-Euler proved it wasnt true in terms of graph theory.

Front 33

what does BFS stand for

Back 33

-Breadth First Search

Front 34

How do you perform BFS

Back 34

-begin with first node; list all adjacent
-return to first adjacent node; list all adjacent that have not been listed
-continue until all nodes are visited

Front 35

What does DFS stand for

Back 35

-Depth First Search

Front 36

how do you perform DFS

Back 36

-Preorder traversal
-visit a node; go to the next adjacent node;continue
-if you come to a dead-end, back-track, until there is a path to visit an unvisited node
-continue until everything is visited or no paths are available to unvisited nodes

Front 37

Time for DFS

Back 37

O(e)

Front 38

What is SSSP

Back 38

-Single Source Shortest Paths
-Dijkstra

Front 39

What is MST

Back 39

-Minimum Spanning Tree
-Prim
-Kruskal
-Both greedy algorithms

Front 40

What is APSP

Back 40

-All Points Shortest Path
-Floyd

Front 41

What is Dijkstra and the Big O

Back 41

-shortest path from a vertex to all other vertices in a weighted graph
-O(E + V^2)

Front 42

What is Prim and Big O

Back 42

-connect to the next shortest edge that doesnt form a cycle
-O(V^2)

Front 43

Compare Prim and Kruskal

Back 43

-Prim is best when many edges && does not depend on the # of edges
-Kruskal good for sparse graphs with few edges

Front 44

What is Kruskal and the Big O

Back 44

-sort edges, take the shortest that doesnt create a cycle
-O(ElgE)