[go: up one dir, main page]
Scribd
Upload
29 views1 page

Final Exam Preparation Guide

Uploaded by

Ibm Fatty
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
29 views1 page

Final Exam Preparation Guide

Uploaded by

Ibm Fatty
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Final Exam Preparation Guide

The final exam will encompass all topics discussed throughout the semester. It is crucial to
revisit your mid-exam questions as part of your review.
Algorithm Analysis:
 Recursive Algorithms: Analyze recursive algorithms to determine their running time
functions and solve recurrence relations.
 Master’s Theorem: Apply the Master’s Theorem to find the asymptotic time complexity
for both dividing and conquering functions.
 Big-Oh Notation: For any two functions, identify the constants and the values of ‘n’ that
validate the given relationship.
Dynamic Programming:
 Understand the concepts, properties, advantages, and disadvantages.

 Study examples and their mechanics, including:


o Knapsack Problem
o Longest Common Subsequence (LCS): For two given strings, determine the
value of LCS[i][j] in their LCS table.
Greedy Algorithms:
 Grasp the concepts, properties, advantages, and disadvantages.

 Review examples and their mechanics, such as:


o Coin Change Problem
o Activity Selection Problem
o Huffman Encoding: Be prepared to determine the binary bit representations and
calculate the total number of bits required in the compressed message.
Minimum Spanning Tree Algorithms:
 Using the weight adjacency matrix of an undirected graph, practice applying Prim’s or
Kruskal’s algorithm.
Shortest Path Algorithms:
 Study Dijkstra, Bellman-Ford, and Floyd-Warshall algorithms, including the concept of a
negative weight cycle.
 Specifically, for the Bellman-Ford algorithm, be able to determine the shortest distance to
each vertex from a source vertex ‘vn’ after a specified number of edge relaxations.
Note: It is essential to understand the underlying mechanics and be able to apply these concepts
practically.
Good luck with your exam preparations!

You might also like