CST-370 Week 1

 This week I learned what Algorithms are, important problem types in Algorithms, fundamental data structures, and analysis of algorithms.

Algorithm: A sequence of clear instructions for solving a problem. Algorithms produce output in a finite amount of time. It is advised to solve a problem by choosing the right algorithm first before coding the solution.

Euclid's Algorithm: An algorithm used to calculate GCD (Greatest Common Devisor). The GCD is the largest integer that divides both m and n evenly, with a remainder of zero. m and n can't be 0 at the same time. If one of the two values m or n is 0, the other non-zero input is the answer. (e.g. gcd(60,0) = 60)

Ex: 

• gcd(0,0): 0/0 = Invalid
• gcd(6, 4) Numbers that can divide evenly between both: 1, 2, 3 (Can't divide 4), 4 (Can't divide 6)
• Largest is 2, so answer is 2.

Euclid's algorithm is: gcd(m, n) = gcd(n, m mod n) until n becomes 0. At that point, m is the answer.

Ex:

gcd(60, 24)

• = gcd(24, 60 mod 24)
• = gcd (24, 12) *Note: 60 mod 24 is 12 (60 / 24 = 2 -> 60 - (24*2) = 12)
• = gcd (12, 24 mod 12) *Note 24 mod 12 = 0)
• = gcd (12, 0)
• = 12

Important points for algorithms: Input has to be specified carefully, several algos for solving the same problem may exist, algos for the same problem can be based on very different ideas and can be solved at different speed.

Pseudocode: An important tool for describing and analyzing algos. Represents logic in plain English.

-----------------------------------------------------------------------------------------------------------------------------

Important problem types: 

Sorting and Searching

Sorting: The process of arranging items in either ascending or descending order. Sorted data enables efficient searching, such as binary search.

Properties for sorting algorithms:

1. In-place sorting: A sorting algorithm that does not require much extra memory, except for a few memory units.
2. Stable sorting: A sorting algorithm that keeps the relative order of equal elements in its input.

Stable sorting algos: Merge sort, insertion sort, bubble sort

Unstable sorting algos: Quick sort, heap sort, selection sort

Unweighted Graphs

Graph: Composed of nodes (vertices) and edges (lines). Used for modeling real-life applications.

Formal definition: A graph G = <V, E> is defined by a pair of two sets: a finite nonempty set V of items called vertices and a set E, edges. A graph is undirected if there is a connection between two nodes. (e.g. a -> c, c -> a). A graph is directed if there is a connection to one point from another but no connection back. 

V must contain vertices while E can be empty. E cannot contain duplicate edges, and V cannot contain duplicate vertices.

Most common problem: Traveling Salesman Problem

Example graph problem. Find shortest path back to a, starting at a, using all permutations of the nodes b, c, and d

Undirected Graphs can be represented as an Adjacency Matrix

Not ideal when we have billions of nodes.

Ex:

Directed graphs can be represented by an Adjacency List (Linked List)

Weighted Graph

A weighted graph is a graph with weights, such as costs or distances, assigned to its edges.

Represented as an Adjacency matric:

Tree

A tree is a special type of graph: a connected acyclic graph (There can be no cycles in the graph). The number of edges in a tree is always equal to one less than the number of vertices: |E| = |V| - 1