S.No.

Topics

Lectures

Instructor

References/Notes

1

Introduction:
Asymptotic Complexity, Iterative and Recursive Algorithms,
Basic C primer with arrays and linked lists

12

SDR


2

State Machines: the Hardware
and Software conjunction:
State Machines and Strings,
State Minimisation, String Matching

0305

SDR

String Matching: [CLRS]. Hardwarerelated algorithms: books on
Digital Electronics/Digital Logic/Digital Circuits e.g., [HP]
These will give the EE perspective on Automata models: the Mealy
and Moore models, and related algorithms. The CS perspective on
Automata models: DFAs can be found in books on the Theory of
Computation e.g., [HMU].


Asymptotic Complexity, the EE and CS
perspectives. 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. A mere mention
of more complicated automata models: PushDown Automata
(FSM+stack), and the ultimate: Turing Machines.

25 Jul (Tue) {lecture#01}

SDR



Continuing with the 2bit up/down counter,
hardware implementation of a synchronous machine (algorithmic),
extension of the state machine idea to arbitrary input and output
alphabets. Introducing strings and string matching.
grep and searching for strings.

26 Jul (Wed) {lecture#02}

SDR



Exact Pattern Matching in linear time with
automata. (We will cover inexact matching in the Dynamic
Programming part). A mere mention of the stateoftheart KMP
algorithm, which works in O(n + m) time, albeit amortised.

28 Jul (Fri) {lecture#03}

SDR

Early class 07:30am08:30am. Venue II241 (EE Committee Room)


C programming: functions, pointers, basic data
structures: arrays (static and dynamic), linked lists, trees

01 Aug (Tue) {lecture#04}

SDR

test_linked.c (the main program to be
compiled), and linked.c (useful subroutines)


Basic data structures (contd): graphs.
State Minimisation: the kEquivalence technique, with its O(n^2)
time complexity. Explanations, basic philosophy behind O(n^2). A
mere mention of the stateoftheart: Hopcroft's algorithm, which
is O(n log n).

02 Aug (Wed) {lecture#05}

SDR


3

FFT and Friends:
DivideandConquer, DFT and FFT, Sorting

0611

SDR



Recurrence relations and analysis.
Recurrence and a base case. O(n^2) sorting in Selection Sort or
Bubblesort. DivideandConquer algorithm design strategy.
Mergesort, DFT and FFT.
Halfandhalf split leads to log n steps.
O(n) merge of two sorted arrays.
O(n log n) algorithms using DivideandConquer.

04 Aug (Fri) {lecture#06}

SDR



The FFT algorithm: splitting the summation into even and odd indices.
(Decimation in time). Mathematical details, time complexity.
Heaps. The basic structure, linked and array implementations.

08 Aug (Tue) {lecture#07}

SDR



Function heapify : O(log n). This is a small
subroutine that will be used in a few applications.
Function build_heap : O(n). Introduction.

09 Aug (Wed) {lecture#08}

SDR

[CLRS]


Function build_heap : O(n). (contd)
A simple analysis gives O(n log n). The definition of height of a
node, and a tighter bound: O(n).

11 Aug (Fri) {lecture#09}

SDR

[CLRS]


Programming a tree: simple operations.
Function heapsort : O(n log n).

16 Aug (Wed) {lecture#10}

SDR

test_binary_tree.c (the main program to be
compiled), and binary_tree.c (useful
subroutines)

4

Network Routing: Dijkstra
Greedy Algorithms,
Dijkstra's Single Source Shortest Paths Algorithm

1112

SDR



(min) Heaps for priority queues, which will be used in
Dijkstra's Single Source
Shortest Paths algorithm. Functions delete_min ,
decrease_key and insert , and their
O(log n) time complexities. A mere mention of the
stateoftheart: Fibonacci heaps, with O(log n), O(1) and O(1)
complexities, respectively (albeit amortised).
Greedy algorithms: the Knapsack problem.
Introduction to Dijkstra's Single Source Shortest Paths problem.

18 Aug (Fri) {lecture#11}

SDR

[CLRS]


Dijkstra's Single Source Shortest Paths Algorithm: description,
the use of priority queues, and the overall complexity. Notes
about the applicablitiy of Dijkstra's algorithm.
Introduction to Dynamic Programming. Features of Dynamic
Programming visavis DivideandConquer, and Greedy Algorithms.
The connection to Dijkstra's Single Source Shortest Paths
problem: a similar optimisation function to minimise.
Another link: the optimal structure of a subproblem.
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!

19 Aug (Sat) {lecture#12}

SDR

This will be a makeup class in lieu of the 26 Aug (Sat) class
(IITD Academic Calendar: 26 Aug (Sat) will follow the Tue timetable)
08:00am09:00am. Venue: II241 (EE Committee Room)

5

Network Routing, DTW, Trellis/Viterbi:
Dynamic Programming,
AllPairs Shortest Paths for Communication networks routing,
Dynamic Time Warping in Speech Processing,
Trellis Codes/Convolutional Codes/Viterbi Algorithm,
String Matching with Errors

1220

SDR

[CLRS]


The All Pairs Shortest Paths Problem for routing in communication
networks. The d[i,j]^(k) formulation
leads to an efficient O(n^3) algorithm.
Illustration of the three main points in a Dynamic
Programmingbased solutions:
1. Optimal substructure
2. Recursive solution of overlapping subproblems
3. Building a solution bottomup, and not topdown

22 Aug (Tue) {lecture#13}

SDR



All Pairs Shortest Paths: The optimal path itself: predecessor vertex.
Illustration of Dynamic Programming with the Matrix Chain
Multiplication problem. Exhaustive enumeration of all
parenthesisations has exponential complexity. Motivation for a
Dynamic Programming solution. The concept of a `path' in an abstract
solution space, much like the All Pairs Shortest Paths problem.
1. Optimal substructure
2. Recursive solution of overlapping subproblems

23 Aug (Wed) {lecture#14}

SDR



Matrix Chain Multiplication (contd).
A mere mention of Trellis Codes/Convolutional Codes/Viterbi Algorithm.
Introduction to the String Edit Distance problem: string matching
with errors. Relating this to the original string matching
problem (FSMbased modelling, as done earlier), and Speech Signal
Processing and Music Signal Processing with Dynamic Time Warping.

25 Aug (Fri) {lecture#15}

SDR

Early class 07:30am08:30am. Venue II241 (EE Committee Room)



26 Aug (Sat)



(No class: makeup class on 19 Aug (Sat))



Minor 1

31 Aug (Thu)






Taking stock: the basic philosophy in the three Dynamic
Programming examples discussed thus far. The three basis tenets,
but problemspecific differences. We haven't attacked the third
issue in the Matrix Chain Multilpication thus far: getting a
bottomup solution. We will, after looking at the basic tenets of
the String Edit Distance problem. Basic concepts in the String
Edit Distance problem: philosophy (converting one string into
another, or string matching with errors), notation, problem statement, optimal
substructure, building the recursive problem defintion in terms
of overlapping subproblems.

05 Sep (Tue) {lecture#16}

SDR



String Edit Distance: the basic recurrence in terms of the three
possibilities for the current operation. Building a bottomup
solution to the recurrence

06 Sep (Wed) {lecture#17}

SDR



The String Edit Distance problem. Solving the recurrences
bottomup: basic pseudocode.
O(m n) to convert string X_m to Y_n.

08 Sep (Fri) {lecture#18}

SDR

(Early class 07:30am08:30am. Venue II241 (EE Committee Room)


The String Edit Distance problem (contd.): to find the operations.
Getting back to the Matrix Chain Multiplication problem: solving
the recurrences bottomup: Introduction and basic philosophy.

12 Sep (Tue) {lecture#19}

SDR



The Matrix Chain Multiplication Solution: bottomup solution with
the length of the chain. Printing the optimal parenthesisation.
Introduction to some graph algorithms.

13 Sep (Wed) {lecture#20}

SDR


6

Miscellaneous Graph Algorithms
The BellmanFord algorithm for Single Source Shortest Paths

2121

SDR



The BellmanFord algorithm for Single Source Shortest Paths.
Completing the loop from where we had started with Dijkstra's
optimisation. Dealing with negative edges and negative cycles.

15 Sep (Fri) {lecture#21}

SDR


7

AI:
BranchandBound,
BackTracking, Search Trees, Algorithm A*:
Heuristic Search

xxxx

SDR


8

Miscellaneous:
Network Flows, RedBlack Trees (Linux uses these!)
A cursorial tour of BFS/DFS for trees,
Minimum Spanning Trees (Prim's and Kruskal's algorithms)

xxxx

SDR


xx


xxxx

xx

