|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Algorithms and Complexity |
|
|
|
|
State Machines and Strings, String Matching, State Minimisation |
|
|
|
|
A formal introduction to asymptotic time complexity, the Big-Oh notation. The physical significance of the Big-Oh. |
|
|
|
|
Implementation issues: Static and Dynamic allocation. What are pointers? Why are subroutines called functions? Mop-up of the routines in static_dynamic_example.c .
An introduction to programming/coding discipline: HTML. Assignment 0 |
|
|
|
|
|
|
|
|
|
|
|
|
MS-Teams folder: video_string_matching_06oct20.mp4, slides_string_matching_06oct20.pdf, lecture_notes_string_matching_06oct20.pdf |
|
Implementation issues: Completing a sample linked list implementation in C. Main file to be compiled: linked_example.c .
File with auxiliary routines called by this main code:
linked_list_utilities.c .
|
|
|
|
|
Divide-and-Conquer, DFT and FFT, Sorting |
|
|
|
|
The O(n^2) DFT. An introduction to the O(n log n) complexity FFT algorithm, which can also be performed in place i.e., without any extra space needed. The Cooley-Tuckey FFT (Decimation-in-Time: DIT) algorithm. Dividing the N point signal into even and odd indices. Splitting the computations into two parts: the basic mathematics. Getting a recurrence relation similar to the Mergesort recurrence. For self-study: how can bit-reversal help make the computations in-place? Implementation issues: The k-equivalence technique as a C program. The first cut. Reading in a Mealy machine from a file, and printing it. Please note that the implementation may not be that efficient, but should end up as a workable solution. Files: mealy_minimisation.c
(This is the main C program, which is to be compiled. The
compilation can be performed with gcc as:
gcc -g -Wall mealy_minimisation.c ).
mealy_example.txt
(This is the data file which stores the Mealy machine, with the
first line having the number of states, and the syntax of each
successive line being {state#} {state on x=0} {output on x=0}
{state on x=1} {output on x=1}. This is with respect to the
example done in class.)
mealy_utils.c
(This file contains data structures and utilities for the Mealy
machine implementation.)
linked_utils.c
(This file has the implementation of the linked
data structures for the state minimisation.)
|
|
|
|
|
Implementation issues: Files for a factorial example: factorial_example.c
(This is a self-contained main C program, which is to be compiled. The
compilation can be performed with gcc as:
gcc -g -Wall factorial_example.c ).
This file has two equivalent recursive sub-routines to compute
the factorial of a number, one without any explanations, and one
with explanations, as to how recursion takes place.
Files for a mergesort example: mergesort_example.c
(This is a self-contained main C program, which is to be
compiled. The
compilation can be performed with gcc as:
gcc -g -Wall mergesort_example.c ).
This file has two sub-routines to perform a mergesort
(recursively), and merge two sorted arrays.
|
|
|
|
|
heapify : O(log n). This is a small
subroutine that will be used in a few applications. Assumptions
about the structure. We will need a function to ensure this
structure, from scratch.
Implementation issues: Files for a binary tree example, implemented using pointers: test_binary_tree.c
(This is the main C program, which is to be compiled. The
compilation can be performed with gcc as:
gcc -g -Wall test_binary_tree.c ).
This uses routines from
binary_tree.c
Please note that the heap routines are much better implemented an
an ordinary array, not using a linked represetation!
Files for an implementation of routines related to heaps: heap_example.c
(This is the main C program, which is to be compiled. The
compilation can be performed with gcc as:
gcc -g -Wall heap_example.c ).
This uses routines from
heap_utils.c
|
|
|
MS-Teams folder: video_heap1_13oct20.mp4, lecture_notes_heap1_13oct20.pdf |
|
build_heap : O(n). Introduction.Observation#1: leaf nodes, in an array representation. A naive analysis of the complexity: disconcerting! Observations#2, 3: a new definition to get us a tighter bound: the height of a node. A better re-formulation of algorithm build_heap in terms of the height of a node.
Analysis of its time complexity: getting O(n).
Function heapsort : O(n log n). It is also
in-place: a nice trick with the array implementation.
(min-) Heaps for priority queues, which will be used in
what is possibly the best-known routing algorithm used in
communication networks namely, Dijkstra's Single Source
Shortest Paths algorithm.
|
|
|
MS-Teams folder: video_heap2_14oct20.mp4, video_heap3_14oct20.mp4, lecture_notes_heap2_14oct20.pdf |
|
delete_min ,
decrease_key and insert , and their
O(log n) time complexities.
A mere mention of the
state-of-the-art: Fibonacci heaps, with O(log n),
O(1) and O(1)
complexities, respectively (albeit amortised).
|
|
|
MS-Teams folder: video_heap4_greedy1_16oct20.mp4, lecture_notes_heap3_14oct20.pdf |
|
Greedy Algorithms, Dijkstra's Single Source Shortest Paths Algorithm |
|
|
|
|
|
|
|
MS-Teams folder: video_heap4_greedy1_16oct20.mp4, slides_greedy1_16oct20.pdf |
|
Implementation issues: Completing the heap example, with routines decrease_key , delete_min and
insert . The downloadable links to the required files
are the same as above.
A full example for Dijkstra's single source shortest paths algorithm. dijkstra_example.c ,
which is to be compiled with the command
gcc -g -Wall dijkstra_example.c -lm .
This reads the graph from an ASCII text file
dijkstra_example.txt .
This uses graph-related utilities from #include'd file
graph_utils.c .
This in turn, uses utilites from the previous code
heap_utils.c .
|
|
|
MS-Teams folder: video_heap5_greedy2_17oct20.mp4, slides_greedy2_17oct20.pdf |
|
Dynamic Programming, All-Pairs Shortest Paths for Communication networks routing, Dynamic Time Warping in Speech Processing, Trellis Codes/Convolutional Codes/Viterbi Algorithm, String Matching with Errors |
|
|
|
|
The All Pairs Shortest Paths Problem. Running Dijkstra on all O(n) vertices works, but there is a better algorithm for that, using Dynamic Programming! Intuition: running Dijkstra on all vertices seems to repeat computations for sub-paths. The Floyd-Warshall Dynamic Programming algorithm will avoid such wasteful computations. The same basic optimality of sub-paths property (simple and intuitive proof by contradiction, which is the same as what one saw from the Dijkstra algorithm). The novel Floyd-Warshall problem formulation: d^(k)[i, j] = cost of the path from node i to node j through a path where no vertex is numbered greater than k. This is a bottom-up formulation. Why? The base case is d^(0)[i, j]: the cost of the path from node i to node j through a path where no vertex is numbered greater than 0 i.e., there is no intermediate vertex at all. The cost is C[i, j], the weight of the edge between nodes i and j if there is one, and infinity, otherwise. An intuitive build-up starting from d^(0)[i, j], going to d^(1)[i, j], and so on. This is bottom-up! (Smaller units are being solved before the larger ones). The recursive problem formulation with a cost function involving the novel problem formulation. A simple triple loop O(n^3) algorithm! |
|
|
MS-Teams folder: video_dp1_20oct20.mp4, slides_dp1_20oct20.pdf |
|
Implementation issues: A small discussion on the implementation of Dijkstra's algorithm. |
|
|
MS-Teams folder: video_greedy3_21oct20.mp4, lecture_notes_greedy1_21oct20.pdf |
|
Implementation issues: A full example for the Floyd-Warshall all sources shortest paths algorithm. floyd_warshall_example.c ,
which is to be compiled with the command
gcc -g -Wall floyd_warshall_example.c -lm .
This reads the graph from an ASCII text file
floyd_warshall_example.txt .
This uses graph-related utilities from #include'd file
graph_utils.c .
|
|
|
MS-Teams folder: video_greedy4_27oct20.mp4, video_greedy5_27oct20.mp4, lecture_notes_greedy2_27oct20.pdf |
|
Warshall's algorithm for transitive closure. The String Edit Distance Problem. The basic recursive definition, and base cases. |
|
|
MS-Teams folder: video_dp2_28oct20.mp4, slides_dp2_28oct20.pdf, lecture_notes_dp1_28oct20.pdf, lecture_notes_dp2_28oct20.pdf |
|
Implementation issues: A self-contained file with an implementation of the string edit distance: string_edit_distance.c .
|
|
|
MS-Teams folder: video_dp3_31oct20.mp4, slides_dp3_31oct20.pdf, lecture_notes_dp3_31oct20.pdf |
|
Another Dynamic Programming problem: Matrix sequence multiplication. Individual matrix multiplication (multiplication of 2 matrices) has quadratic time complexity. An illustration of a simple triple-nested loop procedure. Matrix multiplication is associative, given a sequence of matrices to multiply. We need to split the problem into two parts (convenient!), in order to get a recursive problem formulation. The recursive problem formulation. Optimality: overlapping sub-problems. Now, we need a bottom-up approach. Have sub-problems of smaller length, solve them, store their solutuions. Use these to solve bigger problems. |
|
|
MS-Teams folder: video_dp4_03nov20.pdf, video_dp5_03nov20.pdf, slides_dp4_03nov20.pdf, lecture_notes_dp4_03nov20.pdf |
|
Winding-up discussion on negative weight edges in graphs. Dijkstra's Single Source Shortest Paths. The Bellman-Ford Algorithm. |
|
|
MS-Teams folder: video_dp6_04nov20.mp4, lecture_notes_dp5_04nov20.pdf |
|
|
|
|
MS-Teams folder: video_dp7_06nov20.mp4, lecture_notes_dp6_06nov20.pdf |
|
|
|
|
|
|
|
|