Problem Set: ECS 202 Data Structures and Algorithms
Last Updated: February 20, 2024
1. Define data structure and given examples of primitive data structure.
2. Write a program that takes as input an integer n, followed by an array of n integers, and
outputs a maximum element in it.
3. Write a program that takes as input an integer n, followed by an array of n integers, and
outputs a maximum possible product of two elements in it.
4. Write a program that takes as input an integer n and then outputs nth Fibonacci number.
5. For a function g(n) : N 7→ N, define sets O(g), Ω(g), Θ(g), o(g), and ω(g). Give examples
of at least two functions in each of this set.
6. In each of the following situations, indicate whether f ∈ O(g), or f ∈ Ω(g), or f ∈ Θ(g),
or f ∈ o(g), or g ∈ w(g).
(a) n − 100, n − 200 (i) n0.1 , (log n)10
(b) n1/2 , n2/3 (j) (log n)log n , n/ log n
√
(c) 100n + log n, n + (log n)2 (k) n, (log n)3
(d) n log n, 10n log(10n) (l) n1/2 , 5log2 n
(e) log(2n), log(3n) (m) 2n , 3n
(f) 10 log n, log(n2 ) (n) 2n , 2n+1
(g) n1.01 , n log2 n (o) n!, 2n
2
(h) n2 / log n, n(log n)2 (p) (log n)log n , 2(log2 n)
7. Write a program that takes as input an integer n, followed by an array of characters R, B,
and Y . You program should compute minimum number of swaps needed to arrange the
array such that all Bs appear before all Y s which appear before all Rs.
(Reference Chapter 4.3 in [1])
8. Write a pseudo code for (i) bubble sort, (ii) linear search, and (iii) binary search. In each
case, specify input and output.
9. Write a program that takes as input an integer n, followed by an array of n integers and
sorts it using bubble-sort. Your code should output the number of swaps for given input.
10. Write a program that takes as input an integer D, followed by two arrays of size D + 1.
Each array represents a polynomial of degree at most D, where ith entry in the array is
the co-efficient of xi in the polynomial. Your program should compute the product of
these two polynomial. The final output should be the sum of coefficients in the resulting
polynomial.
11. Write a program to read an array of n numbers and then find the smallest number using
pointers.
1
12. Write a program to interchange the largest and the smallest number in an array using
pointers.
13. Write a program to read, display, add, and subtract two complex numbers using struc-
tures.
14. Declare a structure that represents the following: information. Roll Number, Name,
Gender, Date of Birth Marks in English, Marks in Mathematics, and Marks in Computer
Science.
15. Write a program to add and subtract height 6’2” and 5’4”.
16. Write a program to find whether a number is even or odd using functions.
17. Write a program to add two integers and display their output using pointers and functions.
18. Write a program to print all prime numbers from m to n using function.
19. Write a program to read numbers until –1 is entered and display all the numbers.
20. Write a program that performs the following tasks.
(a) Create linked list (g) Delete the node at the beginning
(b) Display all the items in the linked list (h) Delete the node at the end
(c) Insert a node at the beginning (i) Delete the node with specific value.
(d) Insert a node at the end (j) Delete the node that comes after a spe-
(e) Insert a node before a node with spe- cific value
cific value (k) Delete the entire list (and free memory
(f) Insert a node after a node with specific space)
value (l) Sort the linked list (using bubble sort).
21. Write a program to implement a stack using linked list.
22. Write a program to check nesting of parentheses using a stack.
23. Write a program to convert an infix expression into its equivalent postfix notation.
24. Write a program to implement a circular queue.
25. Write a program to implement a priority queue.
26. Write a program that constructs a binary search tree and supports the following oper-
ations. You can assume that you are working only with positive integers and the input
values are unique.
(a) Insert Element (h) Count the total number of nodes
(b) Preorder Traversal (i) Count the total number of leaves
(c) Inorder Traversal (j) Count the total number of internal
(d) Postorder Traversal nodes (i.e. nodes that are not leaves)
(e) Find the smallest element (k) Determine the height of the tree
(f) Find the largest element (l) Find the mirror image of the tree
(g) Delete an element (m) Delete the tree
2
27. Write a program that constructs an AVL tree and supports the operations mentioned
above.
28. Write a program that constructs a Red-Blue tree and supports the operations mentioned
above.
References
[1] Seymour, Lipschutz, Data Structures with C, Publisher: Tata McGraw-Hill
