mertziya/algorithms

Algorithms

Overview

Welcome to my GitHub repository containing coursework from the Algorithms course (CS 301) at Sabanci University. This repository features a range of homework assignments and a final project, demonstrating my understanding and application of various algorithmic concepts.

Homework Assignments

Homework 1

• Topics Covered: Questions on algorithm complexity, worst-case and best-case behaviors of insertion sort, and the ranking of functions based on their growth rates.

Homework 2

• Question 1: Algorithm design for selecting students for a scientific visit based on their grades in CS301.
• Question 2: Optimization and decision problem formulation for messaging friends on a special day without repeating messages to friends who know each other.
• Question 3: Analysis of red-black tree insertions, including rotations and node recoloring.
• Question 4: Understanding NP problems, with definitions and examples.

Homework 3

• Question 1: The Longest Palindromic Subsequence (LPS) problem using dynamic programming.
• Question 2: The 0-1 Knapsack problem - both dynamic programming and greedy solutions.
• Question 3: Greedy solution for a variation of the 0-1 Knapsack problem.

Homework 4

• Question 1: Designing flow networks with non-unique max-flow functions.
• Question 2: Proving the uniqueness of max-flow functions in certain flow networks.
• Question 3: Analysis of summing flow functions in networks.

Final Project: Graph Partitioning

Problem Description

The project tackles the Graph Partitioning problem, an NP-complete problem, with applications in various fields like parallel computing and social network analysis.

Algorithms Implemented

• Brute Force Algorithm: A complete but inefficient solution with a complexity of O(2^(2n)).
• Heuristic Algorithm: A greedy heuristic providing a more efficient, though not always optimal, solution.

Algorithm Analysis

• Brute Force Algorithm: Correctness proof and complexity analysis.
• Heuristic Algorithm: Explanation of the heuristic's approach and its efficiency, including a polynomial-time complexity.

Technologies Used

• Programming Language: C++
• Tools and Libraries: Standard programming libraries and tools for algorithm implementation and analysis.

Author

• Mert Ziya