Welcome to my repository where I solve and document exercises from the subject Algorithms & Data Structures. This repository will serve as a progressive record of my work, including code, explanations, and analyses for each exercise.
-
-
Elementary data structures and their processing
- Exersize 1 - List Abstract Data Type and Linked List
- Exersize 2 - Implementing a Stack Using an Array
- Exersize 3 - Queue Using Stack(s)
- Exersize 4 - Hash Table Operations with Chaining, Linear Probing, and Quadratic Probing
- Exersize 5 - Implement a Set Using a Queue, List, or Stack ADT
- Exersize 6 - Implement a Dictionary/Map Using STL Vector
- Exersize 7 - Old Exam Question
-
- Exercise 1 - Recursive Search and Min/Max Functions
- Exercise 2 - Triangle Pattern Printer
- Exercise 3 - Booklet Printing Function
- Exercise 4 - Maze Solver
- Exercise 5 - Recursive List Search
- Exercise 6 - Selection Sort Algorithm
- Exercise 7 - Counting Sort Algorithm
- Exercise 8 - IntroSort Implementation
This repository contains solutions and documentation for exercises from the "Algorithms & Data Structures" course, part of the Software Technology program at Aarhus University. The course, taken in the third semester of the program, covers a range of fundamental topics including programming, complexity analysis, and the implementation of various data structures and algorithms.
In this repository, you'll find my approach to solving different exercises, along with explanations and analyses for each one. The exercises are designed to deepen the understanding of key concepts in algorithms and data structures through practical coding and problem-solving.
The repository is structured to reflect the progression of the course, with updates as new exercises are completed.
Write a program that:
1. Generates M random integers and stores them in vector.
2. Generates another N random integers and counts how many of them are already present in the vector, using an iterator.
Estimate the worst-case complexity of the program.
What is the time complexity (Big-O) of myMethod?
int myMethod(int N)
{
int x = 0;
int y = 0;
for(int i = 0; i <N; i++)
for(int j = 0; j < N; j++)
for(int k = 0; k < N * sqrt(N); k++)
x++;
for(int i = 0; i < N * N; i++)
y++;
return x + y;
}For each of the following four program fragments:
- Give an analysis of the running time in Big-O notation.
- Implement the code inside a C function, and give the running time for several values of N.
- Compare your analysis with the actual running times.
- Does compiling/running programs with the -O optimization flag change anything in your analysis?
- program fragment:
sum = 0;
for (i = 0; i < n; i++)
sum++;- program fragment:
sum = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
sum++;- program fragment:
sum = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n * n; j++)
sum++;- program fragment:
sum = 0;
for (i = 0; i < n; i++)
for (j = 0; j < i; j++)
sum++;Write an implementation of the ADT MaxHeap described below. The implementation must be done by using the standard class vector from C++. If you need to iterate through the vector, you must use an iterator and its methods and operators begin(), end(), ++, and *.
class MaxHeap
{
public:
//is the heap empty?
virtual bool isEmpty() const = 0;
//number of elements in the heap
virtual int size() = 0;
//number of elements in the heap
virtual void insert(const int x) = 0;
//find the maximum element in the heap
virtual const int findMax() const = 0;
// delete and return the maximum element of the heap
virtual int deleteMax() = 0;
};What is the time complexity of the five operations of MaxHeap? You must argue for your answers
Make a new implementation of the MaxHeap using a List. Make sure to use the List interface where possible.
Create and implement a C++ class called Library that manages books. Each book (which should also be a class) has an identifier (an integer provided when creating the book) and a category (an integer between 0 and 15 inclusive, provided when constructing the book). The Library class should allow the following functionalities:
- Adding new books to the library.
- Borrowing books from the library.
- Returning borrowed books.
- Displaying all available books and borrowed books.
- A function that returns the number of books in a given category.
- When adding a new book, issue a warning (to
std::cout) if the number of books in any category exceeds twice the average number of books per category, to ensure the user maintains a balanced library.
A main function should test all features of the library. Below is the provided starting point for the code that you can modify to implement this:
int main() {
Library myLibrary;
// Adding books to the library
myLibrary.addBook(1, 3); // Book ID: 1, Category: 3
myLibrary.addBook(2, 7); // Book ID: 2, Category: 7
myLibrary.addBook(3, 3); // Book ID: 3, Category: 3
myLibrary.addBook(4, 15); // Book ID: 4, Category: 15
myLibrary.addBook(5, 3); // Book ID: 5, Category: 3 (Warning should trigger here)
myLibrary.addBook(6, 0); // Book ID: 6, Category: 0
// Display all books in the library
std::cout << "\nAll books in the library:\n";
myLibrary.displayAllBooks();
// Display available books in the library
std::cout << "\nAvailable books in the library:\n";
myLibrary.displayAvailableBooks();
// Borrow a book by ID
std::cout << "\nBorrowing Book ID 2:\n";
if (myLibrary.borrowBook(2)) {
std::cout << "Book ID 2 borrowed successfully.\n";
} else {
std::cout << "Failed to borrow Book ID 2.\n";
}
// Attempt to borrow the same book again
std::cout << "\nAttempting to borrow Book ID 2 again:\n";
if (myLibrary.borrowBook(2)) {
std::cout << "Book ID 2 borrowed successfully.\n";
} else {
std::cout << "Failed to borrow Book ID 2.\n";
}
// Display borrowed books
std::cout << "\nBorrowed books in the library:\n";
myLibrary.displayBorrowedBooks();
// Return a borrowed book by ID
std::cout << "\nReturning Book ID 2:\n";
if (myLibrary.returnBook(2)) {
std::cout << "Book ID 2 returned successfully.\n";
} else {
std::cout << "Failed to return Book ID 2.\n";
}
// Display available books after returning a book
std::cout << "\nAvailable books in the library after returning Book ID 2:\n";
myLibrary.displayAvailableBooks();
// Display the number of books in a specific category
int categoryToCheck = 3;
std::cout << "\nNumber of books in category " << categoryToCheck << ": "
<< myLibrary.countBooksInCategory(categoryToCheck) << std::endl;
return 0;
}Justify the choice of the data structures you chose to maintain the books in the library.
Provide the complexity of each operation in the library, and justify.
Implement the List ADT using a linked list that you implement from scratch. Your linked list should support the following operations:
- Insertion at the beginning, middle (given a position), and end of the list.
- Deletion of an element from the beginning, middle (given a position), and end of the list.
- Check if a given element exists in the list.
- Traverse the list to print all elements.
Additionally, add a function to reverse the list and test it.
Implement a stack using an ordinary array. The stack should be initialized with a size parameter that defines the initial size of the stack. The default constructor should create a stack with 100 elements as the initial size. When push(...) is called and the stack is full, a new array should be allocated with double the size. The content of the old array should be copied to the new one, and the old array should be deleted. Analyze the running time of the stack operations push and pop in terms of the number of elements N it stores.
Implement a queue using stack(s). The implementation must be a template and use the Stack ADT presented in the course. There is no requirement for the implementation to be efficient, but you cannot use the internal structure of the stack nor an iterator for the stack.
Let T be a hash-table of size 7 with the hash function h(x) = x mod 7. Write down the entries of T after the keys 5, 28, 19, 15, 20, 33, 12, 17, 33, and 10 have been inserted using:
- Chaining
- Linear probing
- Quadratic probing
Also, calculate the load factor (λ) in the three cases.
Implement a Set using either a Queue, List, or Stack ADT as presented in the course. There is no requirement for the implementation to be efficient, but you cannot use the internal structure of the ADT nor an iterator for the ADT.
Implement a Dictionary (or Map) using an STL vector. The elements of the vector (for the implementation) must be an STL pair representing the (key, value).
In this exercise, a hash table is implemented using quadratic probing to resolve collisions. The hash function used is: h(x) = x mod 11.
The table is populated with the values 22, 5, 16, and 27, inserted in that order.
-
Verify the Table:
Check that the values 22, 5, 16, and 27 are inserted correctly using the hash function and quadratic probing. Positions 1, 2, 3, 4, 7, 8, and 10 are available for new entries. -
Insert Additional Values:
Insert the following values into the table:- 1
- 12
- Age
- Student number
- The hash function
h(x) = x mod 11determines the initial position of each value. - If a collision occurs (the position is already occupied), quadratic probing is applied to find the next available position using the formula:
h(x, i) = (h(x) + i^2) mod table size.
- Insert the values 22, 5, 16, and 27, ensuring the correct application of the hash function and quadratic probing.
- Insert the additional values (1, 12, age, and student number), applying the same logic for handling collisions.
- After all insertions, verify the final state of the table and explain where each value is placed and why.
Implement recursive algorithms that, given an array A of N elements, will:
- Search for a given element x in A and return true if x is found, otherwise return false.
- Find the maximum and minimum elements in A.
State the time complexity for the worst-case scenario for both parts.
Implement a recursive algorithm triangle(int m, int n) that:
- Takes two integer inputs
mandn. - Prints a triangle pattern of lines using the '*' character. The first line will contain
mcharacters, the next line will containm+1characters, and so on, up to a line withncharacters. - After reaching
ncharacters, the pattern should reverse, going fromncharacters back tom. Example output fortriangle(4, 6):
****
*****
******
******
*****
****Many printers allow booklet printing of large documents. When using booklet printing, 4 pages are printed on each sheet of paper so that the output sheets can be folded into a booklet.
Implement a function bookletPrint(int startPage, int endPage) that outputs the pages on each sheet. You may assume that the total number of pages is a multiple of four.
Example for bookletPrint(1, 8):
Sheet 1 contains pages 1, 2, 7, 8
Sheet 2 contains pages 3, 4, 5, 6Write a recursive algorithm that accepts a ROWS x COLS array of characters representing a maze. Each position can contain either an 'X' or a blank space, and one position contains an 'E' marking the exit. Starting at position (1, 1), the algorithm must search for a path to the position marked 'E'. If a path exists, the algorithm should return true; otherwise, return false.
Example maze input:
char maze[ROWS][COLS] = {
{'X','X','X','X','X'},
{'X',' ',' ',' ','X'},
{'X',' ','X',' ','X'},
{'X',' ','X',' ','X'},
{'X','E','X','X','X'}
};Extend Week 3’s List ADT with a new function int search(const Object x) that searches the list for a specific value x using recursion. Use the Recursion Recipe to guide you and write down your answers to the four points. Test your implementation.
Note: It may be beneficial to create a recursive helper function that is called from the public search function.
Implement the Selection Sort algorithm, which works by finding the smallest element in the array and swapping it with the element at A[0], then finding the second smallest element and swapping it with A[1], and so on for the first N-1 elements.
Create a new template implementation of the selection sort algorithm so that it can handle vectors with any generic element type, similar to the provided Insertion Sort code.
Don't forget to test the algorithm thoroughly. Also, provide the best-case and worst-case time complexities for the algorithm.
Implement the Counting Sort algorithm for an array A of integers in the range `{0, ..., k}. This algorithm runs in O(N) time. Provide an analysis of the space complexity.
-
Modify the existing
quickSortimplementation into an IntroSort algorithm. Introduce a constantuseInsertionthat determines when to use quicksort and when to use insertion sort. -
Test your implementation using different input sizes. Measure the time used, and experiment with different values of the
useInsertionconstant. Discuss the results and what you conclude. -
Measure the time for
stlSort.cppusing the same input as in part 2 and compare the results with your implementation. Discuss the comparison.
-
Navigate to the folder corresponding to the desired exersize.
-
Each folder contains:
- The solution code
- A brief explanation and analysis in README.md
- Any additional resources or data files used
-
Clone this repository using:
git clone https://github.com/Miko58/Algorithms-and-Datatructures.git