|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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. |
|
|
|
|
Mop-up of the routines in static_dynamic_example.c .
An introduction to programming/coding discipline: HTML. Assignment 0 |
|
|
|
|
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. |
|
|
|
|
|
|
|
MS-Teams folder: video_fsm2_string1_17aug21.mp4, slides_fsm2_string1_17aug21.pdf, lecture_notes_fsm2_17aug21.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 .
|
|
|
MS-Teams folder: video_string2_linked1_18aug21.mp4, slides_string2_18aug21.pdf, lecture_notes_linked1_18aug21.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 .
|
|
|
MS-Teams folder: video_linked2_statemin1_21aug21.mp4, lecture_notes_linked2_21aug21.pdf, lecture_notes_statemin1_21aug21.pdf |
|
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.)
|
|
|
MS-Teams folder: video_statemin2_divide_conquer1_24aug21.mp4, slides_divide_conquer1_24aug21.pdf, lecture_notes_statemin2_24aug21.pdf |
|
Divide-and-Conquer, DFT and FFT, Sorting |
|
|
|
|
Description of two popular divide-and-conquer algorithms, mergesort and the FFT algorithm. |
|
|
MS-Teams folder: video_statemin3_divide_conquer2_25aug21.mp4, slides_divide_conquer2_25aug21.pdf, lecture_notes_divide_conquer2_25aug21.pdf |
|
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_recursion_divide_conquer3_27aug21.mp4, slides_divide_conquer3_27aug21.pdf, lecture_notes_divide_conquer3_27aug21.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.
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_31aug21.mp4, lecture_notes_heap1_31aug21.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! |
|
|
MS-Teams folder: video_heap2_01sep21.mp4, lecture_notes_heap2_01sep21.pdf |
|
heapify : (contd.)
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_heap3_03sep21.mp4, lecture_notes_heap3_03sep21.pdf |
|
delete_min ,
decrease_key and insert , and their
O(log n) time complexities.
|
|
|
MS-Teams folder: video_heap4_07sep21.mp4, lecture_notes_heap4_07sep21.pdf |
|
Implementation issues: decrease_key , delete_min and
insert . All these are in the two files on heaps,
available in the link above.
|
|
|
MS-Teams folder: video_heap5_greedy1_08sep21.mp4, lecture_notes_heap5_08sep21.pdf, |
|
Greedy Algorithms, Dijkstra's Single Source Shortest Paths Algorithm |
|
|
|
|
|
|
|
MS-Teams folder: video_heap5_greedy1_08sep21.mp4, slides_greedy1_08sep21.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 -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_greedy2_dp1_10sep21.mp4, slides_greedy2_dp1_10sep21.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 |
|
|
|
|
|
|
|
MS-Teams folder: video_greedy2_dp1_10sep21.mp4, slides_greedy2_dp1_10sep21.pdf |
|
Warshall's algorithm for transitive closure. The String Edit Distance Problem. The basic recursive definition, and base cases. 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_greedy3_dp2_14sep21.mp4, slides_dp2_14sep21.pdf |
|
Implementation issues: A self-contained file with an implementation of the string edit distance: string_edit_distance.c .
|
|
|
MS-Teams folder: video_dp3_15sep21.mp4, slides_dp3_15sep21.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_17sep21.mp4, slides_dp4_17sep21.pdf, lecture_notes_dp4_17sep21.pdf |
|
|
|
|
|
|
ELL781 Marks and Grades (Anonymised)