Data Structures and Algorithms Quiz

Data Structures and Algorithms

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

Sorting Algorithms

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

Hash Table Operations

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

Graph Theory

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

Sorting Algorithms

• 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.

Hash Table Operations

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

Hash Table and Hash Function

• 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.

Open Addressing

• 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.

Linear Probing Example

• 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!).

Quicksort

• 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.

Topological Sort

• 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.

Shortest-Path Algorithms

• 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.

Coin-Changing (Greedy Algorithms)

• 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.

Simple Scheduling Problem (Greedy Algorithms)

• 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.