Week $2$: Introduction to Algorithms and Data Structures

Part $1$: Theoretical Questions $(25$ points$)$

Question $1$: Characteristics of Algorithms $(5$ points$)$

$($a$)$ What are the key characteristics of an algorithm? $(2$ points$)$

$($b$)$ Why is it important to analyze the time and space complexity of an algorithm?

$(3$ points$)$

Question $2$: Time Complexity $(5$ points$)$

$($a$)$ Define Big $O$ notation and explain its significance. $(2$ points$)$

$($b$)$ For each of the following time complexities, provide an example of an algorithm that exhibits that complexity:

$O(1)($Constant time$)$

$O(n)($Linear time$)$

$O(n^2)($Quadratic time$)(3$ points$)$

Question $3$: Common Data Structures $(10$ points$)$

$($a$)$ Briefly explain the following data structures and their typical time complexities for basic operations like insertions, deletions, and lookups: $(6$ points$)$

Arrays

Linked Lists

Hash Tables

Stacks

Queues

$($b$)$ When would you prefer using a hash table over an array and vice versa? $(2$ points$)$

$($c$)$ Explain the difference between a stack and a queue, giving an example of when each might be useful. $(2$ points$)$