Data Structures and Algorithms Quiz

Study Notes

Hashing is a technique that uses a key to find or store an item in a data structure.

Arranging a group of items into a defined order based on a particular criteria is called sorting.

When a collision occurs, sequentially searching the table until an empty location is found is known as Linear Probing.

In a direct graph, if there is a path from every vertex to every other vertex, the graph is called Strongly Connected.

Mergesort has a worst-case running time of O(N log N).
Insertion sort is a solution that sorts a list of items by repeatedly inserting a new element into a sorted sublist.

Linear Probing is a solution that sequentially searches the table until an empty location is found when a collision occurs.

To insert an object in a hash table, compute its hash code, check if it exists in the appropriate list, and if not, insert it at the front of the list.
The need to use linked lists slows down the algorithm, and another data structure is required to be implemented.

Linear Probing: when a collision occurs, sequentially search the table until an empty location is found.
Quadratic Probing: uses a collision resolution technique to avoid primary clustering found with linear probes.
Double Hashing: when a collision occurs, a second hash function is used.

When a collision occurs, sequentially search the table until an empty location is found.
Example: the hash function hashes the key 343-567 (SEU Dammam Branch) into index #4, which is already occupied by the key 343-567 (SEU Medina Branch).
Solution: sequentially search for an empty location (index #5 is occupied!).

Steps to conduct the quicksort algorithm:
- Select one element in the list to be the partition element (pivot).
- Move all elements that are less than the partition element to the left, and all elements that are greater than the partition element to the right.
- Repeat steps 1 to 3 (recursively) on both partitions.
- Concatenate both partitions and the pivot until concatenating all list items.
Quicksort has an advantage over Mergesort, where no temporary array is needed.

In a directed acyclic graph, a topological sort is an ordering of vertices such that if there is a path from vi to vj, then vj appears after vi in the ordering.
If a graph has a cycle, a topological ordering is not possible.
To find a topological ordering:
- Find any vertex with no incoming edges.
- Print this vertex, and remove it and its edges from the graph.
Indegree of a vertex v is the number of edges (u, v).
findNewVertexOfIndegreeZero method: searches for a vertex with indegree 0, a vertex that has not already been assigned a topological number.

Examining various shortest-path problems:
- Input: a weighted graph with a cost ci,j associated with each edge (vi,vj) to traverse the edge.
- The cost of a path (v1v2...vN) is called the weighted path length.
Input: an unweighted graph:
- The cost of a path is called the unweighted path length, which is the number of edges on the path.
The shortest path is the least number of edges between the two vertices.

Making the exact change with the minimum number of coins.
Procedure to apply greedy algorithms:
- Add the largest coin possible into an empty set.
- Condition: the coin should not go over the required amount.
To make change of 2.72 SAR, start with the largest coin possible and add it into an empty set.

Suppose we are given jobs j1,j2,...,jN, all with known running times t1,t2,...,tN, respectively.
Our goal is to find the best way to schedule these jobs in order to minimize the average completion time.
Assumption: Once a job is started, it must run to completion (nonpreemptive scheduling).
The optimal schedule can be obtained by arranging the jobs in the order of their shortest running times.