7ce974db-2ac3-4f60-b185-77d0d55ee103.jpeg

# Algorithmic Problem Solving ## Week 1: Introduction ### What is algorithmic problem solving? - **Algorithm**: A finite sequence of well-defined, computer-implementable instructions, typically to solve a class of specific problems. - **Problem**: - Informal: something we want to solve. -...

# Algorithmic Problem Solving ## Week 1: Introduction ### What is algorithmic problem solving? - **Algorithm**: A finite sequence of well-defined, computer-implementable instructions, typically to solve a class of specific problems. - **Problem**: - Informal: something we want to solve. - Formal: specification of the relationship between a set of inputs and a set of desired outputs. - **Problem instance**: A specific input to a problem. - **Algorithmic problem solving**: Transform a problem into an algorithm and implement the algorithm. ### Algorithm properties - Correct: Algorithm gives a correct output for every input. - Efficient: Resources used by the algorithm should be as little as possible. - Time - Memory - Easy to implement ### Program properties - Correct - Efficient - Readable - Maintainable - Reusable ### Algorithm design techniques - Brute force - Greedy - Divide and conquer - Dynamic programming - Search - Depth-first search - Breadth-first search ### Algorithm analysis - Correctness - Time complexity: How long does the algorithm take, as a function of the input size? - Space complexity: How much memory does the algorithm need, as a function of the input size? - Optimality: Is the algorithm the best possible? ### Complexity - How do we measure complexity? - In terms of input size - Worst case analysis - Asymptotic analysis - Big O notation - Big Omega notation - Big Theta notation ## Week 2: Data Structures ### Abstract Data Type (ADT) - A model of data, and the operations we can perform on that data. - Specifies *what* the data type can do, not *how* it will do it. - Examples: - List - Stack - Queue - Dictionary ### Data structure - A way of storing and organizing data in a computer so that it can be used efficiently. - Specifies *how* the data type will do it. - Examples: - Array - Linked list - Hash table - Tree ### Common data structures - List - Array - Linked list - Singly linked list - Doubly linked list - Circular linked list - Stack - Queue - Dictionary - Hash table - Binary search tree ## Week 3: Sorting Algorithms ### Sorting - Putting a set of items in order. - Input: A sequence of $n$ items $a_1, a_2,..., a_n$. - Output: A permutation (reordering) $a'_1, a'_2,..., a'_n$ of the input sequence such that $a'_1 \le a'_2 \le... \le a'_n$. ### Comparison-based sorting algorithms - Only access the input data by comparing two elements. - Bubble sort - Selection sort - Insertion sort - Merge sort - Quick sort - Heap sort ### Non-comparison-based sorting algorithms - Access the input data in other ways than comparing two elements. - Counting sort - Radix sort - Bucket sort ### Bubble sort - Compare each pair of adjacent items and swap them if they are in the wrong order. ### Selection sort - Find the minimum element in the unsorted part of the array, and put it at the beginning of the unsorted part. ### Insertion sort - For each item, insert it into the correct position in the sorted part of the array. ### Merge sort - Divide the array into two halves, sort each half recursively, and then merge the two sorted halves. ### Quick sort - Pick an element as pivot, partition the array around the pivot, and then sort the two partitions recursively. ### Heap sort - Build a heap from the input data, and then repeatedly extract the maximum element from the heap. ### Counting sort - Count the number of times each item appears in the input, and then use this information to put the items in the correct order. ### Radix sort - Sort the items by each digit, starting from the least significant digit. ### Bucket sort - Divide the input into a number of buckets, sort each bucket, and then concatenate the buckets. ## Week 4: Graph Algorithms ### Graph - A graph $G = (V,E)$ consists of a set of vertices $V$ and a set of edges $E$. ### Types of graphs - Directed graph: Each edge has a direction. - Undirected graph: Each edge has no direction. - Weighted graph: Each edge has a weight. - Unweighted graph: Each edge has no weight. - Simple graph: No self-loops and no multiple edges between two vertices. - Complete graph: Every pair of vertices is connected by an edge. - Connected graph: There is a path between every pair of vertices. - Disconnected graph: There is at least one pair of vertices that are not connected by a path. - Acyclic graph: No cycles. - Cyclic graph: At least one cycle. - Tree: A connected acyclic graph. - Forest: A disconnected acyclic graph. - Bipartite graph: The vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. ### Graph representation - Adjacency matrix - Adjacency list - Edge list ### Graph traversal - Depth-first search (DFS) - Breadth-first search (BFS) ### Shortest path algorithms - Dijkstra's algorithm - Bellman-Ford algorithm - Floyd-Warshall algorithm ### Minimum spanning tree algorithms - Prim's algorithm - Kruskal's algorithm ## Week 5: Dynamic Programming ### Dynamic Programming - An algorithm design technique for solving optimization problems - Applicable when the problem exhibits: - Overlapping subproblems: The problem can be broken down into subproblems which are reused several times - Optimal substructure: The optimal solution to the problem contains within it optimal solutions to the subproblems ### Dynamic Programming approaches * Top-down with memoization * Bottom-up with tabulation ### Example problems * Fibonacci numbers * Binomial coefficients * Longest common subsequence * Edit distance * Knapsack problem * Matrix chain multiplication * Shortest paths ## Week 6: Greedy Algorithms ### Greedy Algorithms * An algorithm design technique for solving optimization problems * Build up a solution incrementally, optimizing a single decision at each step * Decisions are based on local information, and are not reconsidered later * Applicable when the problem exhibits: * Optimal substructure: The optimal solution to the problem contains within it optimal solutions to the subproblems * Greedy choice property: The optimal solution can be built by repeatedly selecting the locally optimal choice ### Example problems * Fractional knapsack problem * Activity selection problem * Huffman coding * Minimum spanning tree algorithms * Prim's algorithm * Kruskal's algorithm * Shortest path algorithms * Dijkstra's algorithm ## Week 7: String Algorithms ### Useful string operations * Calculating the length of a string * Comparing two strings * Concatenating two strings * Extracting a substring from a string ### String matching algorithms * Brute force algorithm * Knuth-Morris-Pratt (KMP) algorithm * Boyer-Moore algorithm * Rabin-Karp algorithm ### Other string algorithms - Longest common subsequence - Edit distance - String compression - Huffman coding - Lempel-Ziv ## Week 8: Geometric Algorithms ### Basic geometric objects * Point * Line * Line segment * Polygon * Circle ### Basic geometric algorithms * Distance between two points * Intersection of two lines * Area of a polygon * Point in polygon test ### Convex hull algorithms * Graham scan * Jarvis march ### Other geometric algorithms * Closest pair of points * Line segment intersection * Voronoi diagram * Delaunay triangulation