Software Fundamentals for Computer Technology (ELL781)

Dr. Sumeet Agarwal is the coordinator of this course. Please refer to his course page for important information, and procedural and policy information about the course:
http://web.iitd.ac.in/~sumeet/ell781.html
This page houses the part to be covered by the second instructor, Sumantra. This will constitute the first half of the course. The course will work in a bottom-up manner, starting with examples from Electrical Engineering, and the corresponding algorithms behind them, generalising the concepts to algorithmic design principles.


General Information

No one shall be permitted to audit the course. People are welcome to sit through it, however. The course is open to all suitably inclined students of all disciplines: those who have not taken a data structures and algorithms course, and have no exposure to software engineering. This is a Program Core (PC) for students of the Computer Technology Group, Department of Electrical Engineering. Please note that this course is not open to IITD B.Tech and Dual Degree students who have already done suitable courses in Data Structures and Algorithms (courses beyond COL106, for instance), typically those from the CSE, EE and Maths Departments. Those who are found enrolled after the completion of the add-drop period may be forcibly removed from the course.

Credits: 3 (LTP: 3-0-0) [Slot C]

Schedule for Classes:

Tuesday
08:00 - 09:00
IIA-201 (Bharti)
Wednesday
08:00 - 09:00
IIA-201 (Bharti)
Friday
08:00 - 09:00
IIA-201 (Bharti)

Schedule for Examinations:

Minor 1: 31 Aug (Thu), LH-316, 09:30am-10:30am
Minor 2: 06 Oct (Fri), LH-316, 09:30am-10:30am
Major: 23 Nov (Thu), LH-316, 01:00pm-03:00pm

Teaching Assistants: 

Hemant Goyal
Akash Nayak

Books, Papers and other Documentation

Basic Texts:

Reference Books:


Lecture Schedule, Links to Material (where applicable)

S.No.
Topics
Lectures
Instructor
References/Notes
1
Introduction:
Asymptotic Complexity, Iterative and Recursive Algorithms, Basic C primer with arrays and linked lists
1-2
SDR
2
State Machines: the Hardware and Software conjunction:
State Machines and Strings, State Minimisation, String Matching
03-05
SDR
String Matching: [CLRS]. Hardware-related 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: Push-Down Automata (FSM+stack), and the ultimate: Turing Machines.
25 Jul (Tue) {lecture#01}
SDR
Continuing with the 2-bit 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 state-of-the-art KMP algorithm, which works in O(n + m) time, albeit amortised.
28 Jul (Fri) {lecture#03}
SDR
Early class 07:30am-08:30am. Venue II-241 (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 sub-routines)
Basic data structures (contd): graphs. State Minimisation: the k-Equivalence technique, with its O(n^2) time complexity. Explanations, basic philosophy behind O(n^2). A mere mention of the state-of-the-art: Hopcroft's algorithm, which is O(n log n).
02 Aug (Wed) {lecture#05}
SDR
3
FFT and Friends: Divide-and-Conquer, DFT and FFT, Sorting
06-11
SDR
Recurrence relations and analysis. Recurrence and a base case. O(n^2) sorting in Selection Sort or Bubblesort. Divide-and-Conquer algorithm design strategy. Mergesort, DFT and FFT. Half-and-half split leads to log n steps. O(n) merge of two sorted arrays. O(n log n) algorithms using Divide-and-Conquer.
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 sub-routines)
4
Network Routing: Dijkstra
Greedy Algorithms, Dijkstra's Single Source Shortest Paths Algorithm
11-12
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 state-of-the-art: 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 vis-a-vis Divide-and-Conquer, 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 sub-problem. 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 make-up class in lieu of the 26 Aug (Sat) class (IITD Academic Calendar: 26 Aug (Sat) will follow the Tue timetable) 08:00am-09:00am. Venue: II-241 (EE Committee Room)
5
Network Routing, DTW, Trellis/Viterbi:
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
12-20
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 Programming-based solutions:
1. Optimal substructure
2. Recursive solution of overlapping sub-problems
3. Building a solution bottom-up, and not top-down
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 sub-structure
2. Recursive solution of overlapping sub-problems
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 (FSM-based 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:30am-08:30am. Venue II-241 (EE Committee Room)
26 Aug (Sat)
---
(No class: make-up 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 problem-specific differences. We haven't attacked the third issue in the Matrix Chain Multilpication thus far: getting a bottom-up 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 sub-structure, building the recursive problem defintion in terms of overlapping sub-problems.
05 Sep (Tue) {lecture#16}
SDR
String Edit Distance: the basic recurrence in terms of the three possibilities for the current operation. Building a bottom-up solution to the recurrence
06 Sep (Wed) {lecture#17}
SDR
The String Edit Distance problem. Solving the recurrences bottom-up: basic pseudo-code. O(m n) to convert string X_m to Y_n.
08 Sep (Fri) {lecture#18}
SDR
(Early class 07:30am-08:30am. Venue II-241 (EE Committee Room)
The String Edit Distance problem (contd.): to find the operations.
Getting back to the Matrix Chain Multiplication problem: solving the recurrences bottom-up: Introduction and basic philosophy.
12 Sep (Tue) {lecture#19}
SDR
The Matrix Chain Multiplication Solution: bottom-up 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 Bellman-Ford algorithm for Single Source Shortest Paths
21-21
SDR
The Bellman-Ford 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:
Branch-and-Bound, BackTracking, Search Trees, Algorithm A*: Heuristic Search
xx-xx
SDR
8
Miscellaneous:
Network Flows, Red-Black Trees (Linux uses these!) A cursorial tour of BFS/DFS for trees, Minimum Spanning Trees (Prim's and Kruskal's algorithms)
xx-xx
SDR
xx
xx-xx
xx
The above list is (obviously!) not exhaustive. Other reference material will be announced in the class. The Web has a vast storehouse of tutorial material on Data Structures, Algorithms and other related areas.



Assignments

... A combination of theoretical work as well as programming work.
Both will be scrutinized in detail for original work and thoroughness.
For programming assignments, there will be credit for good coding.
Sphagetti coding will be penalized.
Program correctness or good programming alone will not fetch you full credit ... also required are results of extensive experimentation with varying various program parameters, and explaining the results thus obtained.
Assignments will have to be submitted on or before the due date and time.
Late submissions will not be considered at all.
Unfair means will be result in assigning as marks, the number said to have been discovered by the ancient Indians, to both parties (un)concerned.
Assignment 1
Assignment 2

Examinations and Grading Information

The marks distribution is as follows (out of a total of 100):
Minor I
xx
Minor II
xx
Assignments
xx
Major
xx
Grand Total
100

ELL781 Evaluation: Programming Assignment Groups, Assignment/Examination-related Information [Internal Link: IIT Delhi]

Attendance Requirements:

As per Institute rules for IIT Delhi students: a minimum of 75% (i.e., a maximum of 11 absents permitted), else one grade less.
Illness policy: illness to be certified by a registered medical practioner.
Attendance in Examinations is Compulsory.

ELL781 Attendance Records (25.07.2017-25.08.2017; 05.09.2017-19.09.2017; ) [On the Moodle Page]


Course Feedback

Link to Course Feedback Form
Sumeet Agarwal, Sumantra Dutta Roy, Department of Electrical Engineering, IIT Delhi, Hauz Khas,
New Delhi - 110 016, INDIA. sumeet@ee.iitd.ac.in, sumantra@ee.iitd.ac.in