CSCI 570 episode 1
Preface : I have had a love hate relationship with algorithms, loved it but was quite intimidated (thanks codechef) by it, hated it come interview season and then again started loving it. This series of medium stories is going to be an attempt at a succinct run down of the weekly lectures and discussions of USC’s graduate algorithms course that I am taking this fall.
**Disclaimer**- I am by no means an expert in this subject.
Big thanks to Professor Victor Adamchik for the materials , the first lecture was delightful, understood most of it :P
Meat of the lecture
Course semantics , exam schedule , grades, syllabus, TAs etc….
Runtime Complexity
- used to study performance of algorithms
- we usually use only big oh because it gives us the worst case but there is exist other types too, one of which I heard for the first time in this lecture amortized complexity
- worst case O, o
- best case Ω, ω
- average case θ
- amortized complexity
Insertion Sort
- best case complexity = O(n), which occurs only 2 / (n!) times which is very rare
Quick Sort
- worst case complexity of O(n²), average case O(n log n)
f(n) = Θ(g(n)) iff f(n) = O(g(n)) and f(n) = Ω(g(n))
One really interesting True / False question about complexities
(1/3)^n + 100 = O(1) => ?
Graphs Review
- G(V, E) => V vertices, E edges
- simple graphs => no multiedges and self loops
- directed / undirected
- weighted
- path / simple path
- cycle / acyclic ( eg. trees )
- connected / disconnected
degree of a vertex ( in an undirected graph is the number of edges associated with it )
Handshaking theorem
- Undirected graph => 2 E = ∑ deg(V)
- Directed graph => ∑ indegree(V) or ∑ outdegree(V)
Representing Graphs
- Adjacency List / Adjacency Matrix
- In Adjacency list it takes linear time to determine adjacency but takes up less space
- In Adjacency Matrix determining adjacency takes constant time but more space
- Adjacency List is used for representation of sparse ( O(V) ) graphs and Adjacency Matrix is used for representation of dense ( Ω(V²) ) graphs
Intuition for proving theorems => use induction when numbers (integers) are involved, use contradiction in other cases — Prof Victor Adamchik
- DFS uses stack for backtracking
- BFS uses queue for bookkeeping
- Runtime complexity = O( V + E)
Topological sort for DAG
Linear Time Algorithm => we get vertices in reverse order
Strongly Connected graphs
- brute force => run dfs from every vertex , complexity O(V(V + E))
- better algorithm
- pick a vertex, run dfs, if some vertices are unreachable stop, if not construct transpose of the graph run dfs from the same vertex, if some vertices are unreachable, stop else the graph is strongly connected
Planar Graphs
- V -E+ F = 2
- The proof is by induction on edges
Color Theorem — graph coloring (didn’t quite understand this)’
Bipartite graphs
- graph is bipartite if vertices can be partitioned into 2 disjoint sets X and Y
- bipartite matching — a subset of edges is matching if no 2 edges have a common vertex
Rook attack
- Particularly interesting problem leveraging the concept of bipartite matching where we are asked to place rooks on a chessboard with some squares cut off, such that they don’t attack each other
- can’t put 2 rooks in the same row or column because they will attack each other
- the most critical piece of intuition required to solve the problem => what do we consider the nodes of the bipartite and what the edges ?
- Since we can place rooks only in the non forbidden squares they must be considered to be edges of the graph and the rows and columns of the chess board must be considered the vertices ( my understanding was that a graph can be missing some edges but all vertices are compulsory, hence non forbidden squares as edges)