DIRE DAWA UNIVERSITY
INSTITUTE OF TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE
Group Assignment Of Design and
Analysis Of Algorithm
Group Members: ID
1. Asmamaw Abeba -----------------------------------------------1401399
2. Yosef Mulugeta-------------------------------------------------1403303
3. Tibebe Tadesse--------------------------------------------------1403110
4. Mikiyas Sime---------------------------------------------------- 1402570
5. Yikuraw Lale ----------------------------------------------------1403246
Page 1 of 5
CONTENTS:
1. Describe a scenario where time complexity is more critical than
space complexity
2. How do parallel algorithms improve computational efficiency?
3. What are some applications of parallel algorithms in real-world
scenarios?
4. How does graph coloring demonstrate backtracking principles?
5. Explain how the Hamiltonian cycle problem can be solved with
backtracking. (draw flowchart)
6. What is the knapsack problem, and why is it challenging?
7. How is the shortest path problem solved with a greedy approach?
8. Describe how a priority queue is used in Prim’s algorithm.
9. Compare the time complexities of merge sort and quicksort.
10. What are the different types of hash functions, and which would
you use for a large dataset
10.
Page 2 of 5
1. Scenario where time complexity is more critical than space complexity:
In real-time systems like video games or high-frequency trading platforms, where processing
speed is crucial for providing a seamless user experience or making split-second decisions, time
complexity becomes more critical than space complexity. In these scenarios, algorithms need to
be optimized to run efficiently within strict time constraints to ensure responsiveness and real-
time performance.
2. Parallel algorithms and computational efficiency:
Parallel algorithms improve computational efficiency by breaking down complex problems into
smaller tasks that can be executed simultaneously on multiple processing units. By leveraging
parallel processing, these algorithms can reduce overall computation time and increase throughput
by distributing the workload across multiple cores or machines.
3. Applications of parallel algorithms in real-world scenarios:
Real-world applications of parallel algorithms include:
Scientific simulations and modeling
Big data processing and analytics
Image and video processing
Genetic sequencing and bioinformatics
Cryptography and security algorithms
Machine learning and artificial intelligence tasks
4. Graph coloring and backtracking principles:
Graph coloring is a problem-solving technique that demonstrates backtracking principles by
attempting to assign colors to vertices of a graph in such a way that no two adjacent vertices have
the same color. If a coloring is not possible, backtracking involves undoing the current assignment
and trying a different color until a valid solution is found.
Page 3 of 5
5. Solving the Hamiltonian cycle problem with backtracking:
The Hamiltonian cycle problem involves finding a cycle in a graph that visits each vertex exactly
once and returns to the starting vertex. To solve this problem using backtracking:
Start at a vertex.
Try all possible paths from the current vertex that haven't been visited yet.
Backtrack if a path does not lead to a solution.
Continue until all vertices are visited and a cycle is formed.
Fig 3.1 Hamiltonian Cycle by Backtracking Algorithm
6. Knapsack problem and its challenges:
The knapsack problem involves selecting a subset of items with specific weights to maximize the
total value while not exceeding a given weight capacity. It is challenging because it is an NP-
Page 4 of 5
hard problem, meaning that no efficient algorithm can guarantee finding the optimal solution in
polynomial time for large datasets.
7. Greedy approach in solving the shortest path problem:
In the shortest path problem, a greedy approach selects the locally optimal choice at each step with
the hope of finding a global optimum. Algorithms like Dijkstra's algorithm use a greedy strategy
by iteratively selecting the vertex with the smallest distance from the source vertex until the
destination is reached.
8. Priority queue in Prim's algorithm:
In Prim's algorithm for finding the minimum spanning tree of a graph, a priority queue is used to
store vertices along with their corresponding key values (minimum edge weights). The priority
queue helps in efficiently selecting the next vertex with the minimum key value to expand the tree.
9. Time complexities of merge sort and quicksort:
Merge sort: O(n log n) in the worst, best, and average cases.
Quicksort: O(n log n) in the average case, O(n^2) in the worst case. However, with a
good pivot selection strategy, the worst-case complexity can be reduced.
10. Types of hash functions and their application for large datasets:
Division method: Hash function h(k) = k mod m, where m is the size of the hash table.
Multiplication method: Hash function h(k) = floor(m * (k * A mod 1)), where A is a constant in
(0, 1).
Universal hashing: Hash function selected randomly from a family of hash functions.
Page 5 of 5
