# UE101: Algorithms and Programming

August - December, 2016

Instructor: Dr. Minati De

Instructor: Dr. Minati De

## Targeted Audience

First year UG students of IISc.## Course Syllabus

## Text Books

## Time and Place

## Instructor

## Teaching Assistants

## Announcement

Please feel free to ask questions in: Piazza. Our team will get back to you to answer your questions.## Lecture Notes

### Lecture 0: Introduction to Computer, Algorithms and Programming

[date: 1st August]### Lecture 1: Introduction to Algorithms

[date: 3rd August]### Lecture 2: Introduction to C programming (to be continued)

[date: 4th August]### Lecture 3: Introduction to C programming

[date: 8th August]### Lecture 4: Iterations and recursions

[date: 10th August]### Lecture 5: Searching a list

[date: 17th August]### Lecture 6: Notion of complexity of algorithms

[date: 18th August]### Lecture 7: Pointers and Arrays

[date: 22nd August]### Lecture 8: Dynamic memory allocation

[date: 24th August]### Lecture 9: Structure

[date: 29th August]### Lecture 10: Linked List

[date: 31st August]### Lecture 11: Abstract Data Types (ADT) and their implementation

[date: 7th September]### Lecture 12: More examples on Linked list

[date: 12th September]### Lecture 13: Tree

[date: 14th September]### Lecture 14: Revision on previous lectures

[date: 15th September]### Lecture 15: Binary Search Tree

[date: 19th September]### Lecture 16: Binary Search Tree (contd.)

[date: 21st September]### Break due to Midterm

[during: 26th September to 4th October]### Lecture 17: Balanced Binary Search Tree

[date: 5th October]### Lecture 18: AVL Tree (contd.)

[date: 6th October]### Lecture 19: String Handling

[date: 10th October, Guest Lecture by Soham Pal]### Lecture 20: Introduction to Sorting

[date: 19th October]### Lecture 21: Merge Sort

[date: 20th October]### Lecture 22: Quick Sort

[date: 24th October]### Lecture 23: Heap

[date: 26th October]### Lecture 24: Heap Sort

[date: 31st October]### Lecture 25: More on Sorting

[date: 2nd November]### Lecture 26: Introduction to Graph

[date: 7th November]### Lecture 27: Graph Representation and Depth First Search

[date: 9th November]### Lecture 28: Dijkstra's algorithm for shortest path

[date: 14th November]### Lecture 29: Minimum Cost Spanning Tree

[date: 16th November]### Lecture 30: Breadth First Search and its applications

[date: 17th November]### Lecture 31: Dynamic Programming

[date: 21st November]### Lecture 32: Dynamic Programming (cont.)

[date: 23rd November]
Timing: 8:30 AM to 9:30 AM (Thursday); Venue: Main Lecture Hall
question [by Shivam Gupta]
question [by Inzemamul Hauque]

question [by Snigdha Athaiya and Inzemamul Hauque]

question

question [by Shivam Gupta, Snigdha Athaiya and Inzemamul Hauque]

question [by Shivam Gupta, Snigdha Athaiya and Inzemamul Hauque]

question

question [by Shivam Gupta, Snigdha Athaiya and Inzemamul Hauque]

question [by Shivam Gupta, Snigdha Athaiya and Inzemamul Hauque]

question

question [by Shivam Gupta, Snigdha Athaiya and Inzemamul Hauque]

question

## Tutorial 1

[Date: 11th August]## Tutorial 2

[Date: 25th August]## Tutorial 3

[Date: 1st September]## Quiz-1

[Date: 8th September]## Tutorial 4

[Date: 22nd September]## Tutorial 5

[Date: 13th October]## Quiz-2

[Date: 17th October]## Tutorial 6

[Date: 27th October]## Tutorial 7

[Date: 10th November]## Quiz-3

[Date: 11th November]## Tutorial 8

[Date: 24th November]## Quiz-4

[Date: 25th November]## Homework

### [Based on Lecture 2]

### [Based on Lecture 3]

### [Based on Lecture 4]

int foo ( int n )

{

int s = 0;

while (n>0)

{ n=n-1;

s =s+ 1 + foo(n);

}

return s;

}

Mr X approaches to ADARSH, an IISc undergrad to help him write an alternate way which should work better than the existing one. After learning the trade-off between recursion and iteration, ADARSH immediately suggested an alternate way of implementing this which works pretty well. Now, the question is what ADARSH suggested to Mr. X? [Hint: Reduce the number of recursions in a function call. Write the expression of foo(n) in terms of foo(n-1) only]

### [Based on Lecture 5]

### [Based on Lecture 6]

### [Based on Lecture 7,8]

### [Based on Lecture 9]

### [Based on Lecture 10]

### [Based on Lecture 11]

### [Based on Lecture 12]

### [Based on Lecture 13]

### [Based on Lecture 15]

### [Based on Lecture 17]

|Height(left_subtree(X))-Height(right_subtree(X))|<=4.

Prove that T is a balanced binary tree.