Basic Data Structures and Algorithms Flashcards
(97 cards)
What are the 5 steps for handling technical questions?
- Ask questions
- Design an algorithm
- Pseudocode
- Code
- Test
What are the 5 approaches to algorithms?
- Examplify
- Pattern Matching
- Simplify and Generalize
- Base Case and Build
- Data Structure Brainstorm
What is a linked list?
a data structure in which objects are arranged in linear order. Unlike an array (where order is determined by array indicies) the order is determined by a pointer in each object.
What is a singly linked list?
a linked list where the prev
pointer is omitted in each element
What is a doubly linked list?
a linked list with both a ‘prev’ and next
pointer in each element
What is a circular list?
a list where the prev
pointer of the head of the list (first item in the list) points to the tail of the list. And the next
pointer points to the head of the list.
What is a binary tree?
A binary tree is made of nodes, where each node contains a “left” pointer, a “right” pointer, and a data element. The “root” pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller “subtrees” on either side.
What’s are tries?
A trie is a tree structure, where each edge represents one character, and the root represents the null string.
Thus, each path from the root represents a string, described by the characters labeling the edges traversed. Any finite set of words defines a trie, and two words with common prefixes branch off from each other at the first distinguishing character. Each leaf denotes the end of a string.
When are tries useful?
Tries are useful for testing whether a given query string q is in the set.
We traverse the trie from the root along branches defined by successive characters of q. If a branch does not exist in the trie, then q cannot be in the set of strings
What is a suffix tree?
A trie of all the proper suffixes of S.
The suffix tree enables you to test whether q is a substring of S, because any substring of S is the prefix of some suffix.
The search time is again linear in the length of q.
What are 3 things a suffix tree can be used for?
Find all occurrences of q as a substring of S
Longest substring common to a set of strings
Find the longest palindrome in S
Define Big-O notation.
Big O notation is most commonly used by programmers as an approximate measure of how long a computation (algorithm) will take to complete expressed as a function of the size of the input set.
Big O is useful to compare how well two algorithms will scale up as the number of inputs is increased.
More precisely Big O notation is used to express the asymptotic behavior of a function. That means how the function behaves as it approaches infinity.
What is linear complexity in Big-O notation?
O(n)
ex.) counting the number of items in a linked list
What is quadratic complexity in Big-O notation?
O(n2)
ex.) bubble sort
What is logarithmic complexity in Big-O notation?
O(log n)
ex.) binary search tree
What is constant complexity in Big-O notation?
O(1)
ex.) accessing an array element by index
What is factorial or combinatorial complexity in Big-O notation?
O(n!)
ex.) traveling salesman problem brute-force solution
What is linearithmic complexity in Big-O notation?
O(n log n)
ex.) heap sort and quick sort
What is a stack?
a dynamic set with a LIFO (last in first out) policy.
Think of it as a stack of cafeteria trays, when adding new trays to the stack they go on top, when taking trays off of the stack they come from the top.
What is a queue?
a dynamic set with a FIFO (first in, first out) policy.
What happens when you try to pop an empty stack?
the stack underflows (normally resulting in an error)
What happens if you try adding an element to a stack when it is already holding the maximum amount of elements it can hold?
the stack overflows
what is the insert operation on a stack called?
push
what is the delete operation on a stack called?
pop