|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Algorithms and Complexity |
|
|
|
|
|
State Machines and Strings, String Matching, State Minimisation |
|
|
|
|
|
|
|
|
|
|
|
Automata theory as a link between EE and CS. Introduction to Finite State Machines. State Machines: Moore and Mealy Models. Starting with a `Counter Example'. Fundamental models of automata: Moore/Mealy/DFA (`Finite State Machines'), and a mere mention of NFAs and NFA with epsilon transitions. FSM models: Fundamental models of automata: Moore/Mealy/DFA (`Finite State Machines'), and a mere mention of NFAs and NFA with epsilon transitions. Moore/Mealy (machines with outputs) and DFA/NFA/NFA-epsilon (machines without outputs). A working rule for equivalence of the two representative types of FSM models of the two types, Moore and DFA: DFA final states have an output of 1, others have an output of 0. The `Counter Example'. Example of a Moore/Mealy model for a 2-bit up/down counter, with one binary input line (x=0: downcounter, x=1: upcounter), and one output line (y=1 for maxcount, 0, otherwise.). This can be implemented on a bread-board with 2 flip flops and a suitable number of logic gates. Extension of this idea to multiple input and output lines, and considering a pair of 8 lines as an ASCII character, permitting us characters and other symbols in an alphabet (input/output). Implementation issues: An introduction to programming/coding discipline: HTML. Assignment 0 |
|
|
(Make-up class for the 06 Aug (Sat) class to be missed) MS-Teams folder: video_complexity_automata1_04aug22.mp4, lecture_notes_complexity_automata1_04aug22.pdf, slides_automata1_04aug22.pdf |
|
|
Naive string matching , the link with correlation/convolution. This has quadratic time complexity. Can we use FSMs to speed up string matching? String matching with FSMs, constructed manually, by hand: a DFA example, and a Moore machine. FSM models (contd). Formal definitions of Moore and Mealy Machines. Implementation issues: Why are subroutines called functions? |
|
|
[CLRS] MS-Teams folder: video_string1_automata2_05aug22.mp4, slides_string1_05aug22.pdf, lecture_notes_automata2_05aug22.pdf |
|
|
Can we use FSMs to speed up string matching? Two examples of pattern matcher FSMs, one with a binary input and output line, and another, a DFA with an input alphabet of 3 characters. String matching with an FSM is a linear-time operation, O(n), if we consider the effort to construct the FSM itself, an off-line operation. Construction of the DFA/Moore Machine with an (offline) complexity of O(m^3), leading to an overall time complexity of O(n + m^3) if the off-line part is also to be considered. A mere mention of the state-of-the-art KMP algorithm, which works in O(n + m) time, albeit amortised. Implementation issues: Static and Dynamic allocation. What are pointers? Mop-up of the routines in static_dynamic_example.c.
|
|
|
MS-Teams folder: video_automata3_string2_prog1_10aug22.mp4, slides_string2_10aug22.pdf, lecture_notes_automata3_string2_prog1_10aug22.pdf |
|
|
Implementation issues: Static and Dynamic allocation. What are pointers? Mop-up of the routines in static_dynamic_example.c.
|
|
|
MS-Teams folder: video_state_min_prog2_12aug22.mp4, lecture_notes_state_min_prog2_12aug22.pdf |
|
|
|
|
|
MS-Teams folder: video_prog3_16aug22.mp4, lecture_notes_prog3_16aug22.pdf |
|
|
linked_example.c.
File with auxiliary routines called by this main code:
linked_list_utilities.c.
|
|
|
MS-Teams folder: video_prog4_17aug22.mp4, lecture_notes_prog4_17aug22.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.
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.)
|
|
|
MS-Teams folder: video_prog5_divide_conquer1_23aug22.mp4 |
|
|
Divide-and-Conquer, DFT and FFT, Sorting |
|
|
|
|
|
Description of two popular divide-and-conquer algorithms, mergesort and the FFT algorithm. |
|
|
MS-Teams folder: video_prog5_divide_conquer1_23aug22.mp4, slides_divide_conquer1_23aug22.pdf, lecture_notes_divide_conquer1_23aug22.pdf |
|
|
An introduction to greedy algorithms: seeing the world with Myopic eyes. Complexity less, but optimality? Very few cases of optimal greedy algorithms. The Knapsack problem. Introduction to Dijkstra's Single Source Shortest Paths problem. 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.
|
|
|
MS-Teams folder: video_divide_conquer2_greedy_heaps1_24aug22.mp4, slides_divide_conquer2_greedy_heaps1_24aug22.pdf, lecture_notes_heaps1_24aug22.pdf |
|
|
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.
Building a heap from scratch: function build_heap: O(n). Introduction.Observation#1: leaf nodes, in an array representation. A naive analysis of the complexity: disconcerting! 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!
|
|
|
[Online-only class: MS-Teams: 08:00pm-09:00pm] (Make-up class for the 26 Aug (Fri) class to be missed) MS-Teams folder: video_heaps2_24aug22.mp4, lecture_notes_heaps2_24aug22.pdf |
|
|
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_heaps3_30aug22.mp4, lecture_notes_heaps3_30aug22.pdf |
|
|
delete_min,
decrease_key and insert, and their
O(log n) time complexities.
Implementation issues: 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_heaps4_dijkstra1_31aug22.mp4, slides_heaps4_dijkstra1_31aug22.pdf, lecture_notes_heaps4_dijkstra1_31aug22.pdf |
|
|
Greedy Algorithms, Dijkstra's Single Source Shortest Paths Algorithm |
|
|
|
|
|
|
|
|
MS-Teams folder: video_heaps4_dijkstra1_31aug22.mp4, slides_heaps4_dijkstra1_31aug22.pdf, lecture_notes_heaps4_dijkstra1_31aug22.pdf |
|
|
Implementation issues: (Heaps, contd.) decrease_key, delete_min and
insert. All these are in the two files on heaps,
available in the link above.
|
|
|
MS-Teams folder: video_heaps5_dijkstra2_02sep22.mp4, slides_dijkstra2_02sep22.pdf, lecture_notes_heaps5_02sep22.pdf |
|
|
Implementation issues: 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.
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.
An example for Dijkstra's single source shortest paths algorithm for maps, for actual distance between 5 places, from the point of view of a taxi operator in Gwalior, whose business lies in the following four places: the NCR, Agra, Kanpur, and Aligarh. Costs are based on the relative distances between the cities. This is a version `hacked out' from the previous code, specifically with lots of printf statements, to `pretty-print' the five places in consideration, and to look at actual shortest routes. dijkstra_map_example.c,
which is to be compiled with the command
gcc -g -Wall dijkstra_map_example.c.
This reads the graph from an ASCII text file
dijkstra_map_example.txt.
Like the previous example, this uses graph-related utilities
from #include'd file
graph_utils.c.
This in turn, uses utilites from the previous code
heap_utils.c.
|
|
|
[Online-only class: MS-Teams: 08:00am-09:00am] (Make-up class for the 06 Sep (Tue) class to be missed) MS-Teams folder: video_dijkstra3_03sep22.mp4, slides_dijkstra3_03sep22.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!
|
|
|
[Online-only class: MS-Teams: 08:00am-09:00am] (Make-up class for the 07 Sep (Wed) class to be missed) MS-Teams folder: video_dp1_04sep22.mp4, slides_dp1_04sep22.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_dp2_09sep22.mp4, slides_dp2_09sep22.pdf, lecture_notes_dp2_09sep22.pdf |
|
|
pred function.
The String Edit Distance Problem. The basic recursive definition, and base cases. Discussion on the string edit distance problem: the recursive formulation for the optimisation, a bottom-up implementation, where smaller sub-problems are computed and used for larger sub-problems. A discussion on some practical uses of the string edit distance problem for diverse problems such as music information retrieval, and computational biology. A reiteration of the fact that a recursive formulation does not necessarily imply a top-down formulation. Questions about modifying the original strings X_m and Y_n, insertion and deletion. The idea of a temporary string which starts empty, is based on X_m, and ends up being a copy of Y_n. Getting a possible path from X_m to Y_n. |
|
|
MS-Teams folder: video_dp3_13sep22.mp4, slides_dp3_13sep22.pdf, lecture_notes_dp3_13sep22.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. Implementation issues: A self-contained file with an implementation of the string edit distance: string_edit_distance.c.
|
|
|
MS-Teams folder: video_dp4_14sep22.mp4, slides_dp4_14sep22.pdf, lecture_notes_dp4_14sep22.pdf |
|
|
Winding-up discussion on negative weight edges in graphs. The Bellman-Ford Algorithm. |
|
|
[CLRS] MS-Teams folder: video_dp5_16sep22.mp4, lecture_notes_dp5_16sep22.pdf |
|
|
|
|
|
|
|
|
|
ELL781 Marks and Grades (Anonymised)