Data-Structures-and-Algorithms

This project is meant to help beginners understand and code Data Structures and Algorithms in C. This project strictly follows the book `Introduction to Algorithms` by Thomas H. Cormen. Any beginners strugling with Data Structures and Algorithms are highly recommended to follow the book. Most of the code is documented properly for beginner audiences to understand easily. Minimum utilities and libraries are used in case the targeted audience ins't familiar with them.

This project is still in development stage and needs more contributors.

Read contributing guidelines in case you want to contribute to this project.

Algorithms Implemented

Algorithms have been mostly implemented in C++ and partially documented. The algorithms implemented are:

1. Insertion Sort. (location: Algorithms.cpp, line on:[150-165])
2. Heap Sort (location: Algorithms.cpp, line no:[331-342])
3. Quick Sort (location: Algorithms.cpp, line no:[368-378])
4. Randomized Quick Sort (location: Algorithms.cpp, line no:[360-366])
5. Counting Sort (location: Algorithms.cpp, line no:[392-408])
6. Merge Sort (location: Algorithms.cpp, line no:[410-467])
7. Selection Sort (location: Algorithms.cpp, line no:[484-500])
8. Bubble Sort (location: Algorithms.cpp, line no:[474-482])
9. Linear Search (location: Algorithms.cpp, line no:[133-143])
10. Binary Search (location: Algorithms.cpp, line no:[111-124])
11. Maximum Subarry Problem solved using brute forse, devide and concour and linear methods. (location: Algorithms.cpp, line no:[582-691])
12. Infix to Reverse Polish (postfix) using STACK in C (location: infix_to_postfix/main.c)
13. Infix to Polish (prefix) using STACK in C (location: infix_to_prefix/main.c)
14. Reverse Polish (postfix) to Polish (prefix) using STACK in C (location: postfix_to_prefix/main.c)
15. Reverse Polish (postfix) to Infix using STACK in C (location: postfix_to_infix/main.c)
16. Polish (prefix) to Reverse Polish (postfix) using STACK in C (location: prefix_to_postfix/main.c)
17. Polish (prefix) to Infix using STACK in C (location: profix_to_infix/main.c)

All the algorithms will be fully documented and implemented in C soon!

Data Structures Implemented

All the Data Structures have been implemented in C. The implemented Data Structures are:

1. Stack (fully documented) (C implementation: stack_as_static_array.c, C++ implementtation: stack/stack/headers/Stack.h)
2. Queue (documented) (C implementation: queue_using_static_array.c, C++ implementtation: queue/queue/headers/Queue.h)
3. Heap (documented) (location: Algorithms.cpp, line no:[168-342])
4. Priority Queue (documented) (C implementation: priority_queue.c, C++ implementation: Algorithms.cpp, line no:[168-342])
5. Circular Queue (undocumented) (location: circular_queue_uaing_static_array.c)
6. Binary Search Trees (undocumented) (location: binary_tree.c)
7. Doubly Linked List (fully documented) (location: doubly_linked_list.c)
8. Direct Address Tables (undocumented) (location: direct_address_tables.c)
9. Hash Tables (fully documented) (location: hash_tables.c)

Dynamic Programming

Currently under devlopment, some of the Dynamic and Greedy Algoruthms have been implemented in this section. The implementations include:

1. Fibonacci Series
2. Rod Cutting Problem
3. Matrix Chain Multiplication Problem
4. Longest Common Subsequence Problem

When does Dynamic Algorithm apply?

1. optimal substructure.
   • Property of independence holds.
   • Property of linearity holds.
   • Choices hold both for subproblems and problems.
2. overlapping subproblems.

Elements of Dynamic Programming:

1. Optimal Substucture.
2. Overlapping Subproblems.
3. Reconstructing a optimal solution.
4. Memoization for top-down approach.

Attack plan:

1. Characterize the stucture of an optimum solution.
2. Recursively define the value of an optimum solution.
3. Compute the value of optimum solution.
4. Construct an optimal solution from computed information.

Examples:

1. Rod cutting Problem.
2. Matrix Chain Multiplication.
3. Shortest Path in unweighed directed graph.
4. Longest Common Sub-Sequence.

Where it doesn't apply:

1. Longest Path in unweighed directed graph.
2. Rod cutting with limit of cuts.

Thank you!

Please read the contributing guidelines if you wish to contribute!