# CS2700: Programming and Data Structures

## Course information

**When**: Jul-Nov 2022**Lectures**: Slot C**Where**: CS25**Teaching Assistants**: Nalin Raj Gudipati, Rishabh Singh, Vrushab Ramesh Karia, Amishi Panwar, Ashish Parjapati, Jatin Singh Kanyal, Kartik Arvindbhai Gondaliya, B Abhijit, Muhammed Tharikh, Nitesh Rakesh Patwa, Susmit Jaiswal, Yashasvi Mahajan

## Course Content

Analysis of algorithms using time and space complexity.

Arrays, lists, stacks, queues, trees.

Searching and sorting algorithms.

Graph algorithms, dynamic programming.

## Grading

Quiz-I and II: 15% each

Final exam: 40%

Tutorials: 6% each (Best 5 out of 7)

## Important Dates

Tutorials: 5 Aug, 19 Aug, 5 Sep, 16 Sep, 14 Oct, 28 Oct, 4 Nov

Quiz-I: 24 Aug

Quiz-I: 28 Sep

Final exam: 14 Nov

## Textbooks

Michael T. Goodrich, Roberto Tamassia, and David M. Mount. Data structures and algorithms in C++. John Wiley & Sons, 2011.

Mark A. Weiss. Data structures and algorithm analysis in C++. Pearson, 2014.

## Schedule

Lecture number | Topics Covered | Section reference |
---|---|---|

Lecture 1 | Analysis of algorithms: Primitive operations and growth rate |
Section 4.2 of [Goodrich et al.] |

Lecture 2 | Analysis of algorithms: Big-oh notation, asymptotic analysis |
Section 4.2 of [Goodrich et al.] |

Lecture 3 | Analysis of algorithms: Prefix averaging example, friends of Big-oh |
Section 4.2 of [Goodrich et al.] |

Lecture 4 | Recurrence equations: Iterative substitution and guess-and-test solution approaches |
Section 11.1.5 of [Goodrich et al.] |

Lecture 5 | Recurrence equations: Master method | Appendix A of [Goodrich et al.] |

Lecture 6 | Merge-sort | Section 11.1 of [Goodrich et al.] |

Tutorial 1 | ||

Lecture 7 | Sorting lower bound | Section 11.3 of [Goodrich et al.] |

Lecture 8 | Quick-sort | Section 11.2 of [Goodrich et al.] |

Lecture 9 | Worst-case runtime of quick-sort | Section 11.2 of [Goodrich et al.] |

Lecture 10 | Average-case runtime of quick-sort | Section 11.2 of [Goodrich et al.] |

Lecture 11 | Bucket and radix sort | Section 11.3.2 of [Goodrich et al.] |

Tutorial 2 | ||

Lecture 12 | Tutorial-2 discussion Quickselect |
Section 11.5 of [Goodrich et al.] |

Lecture 13 | Average-case analysis of quickselect Sets data structure |
Section 11.5 and 11.4 of [Goodrich et al.] |

Quiz 1 | ||

Lecture 14 | Stacks | Section 5.1 of [Goodrich et al.] |

Lecture 15 | Applications of stacks: evaluating expressions and computing spans | Section 5.1 of [Goodrich et al.] |

Lecture 16 | Queues and singly-linked lists | Sections 5.2 and 3.2 of [Goodrich et al.] |

Lecture 17 | Doubly-linked lists, and growable arrays (vectors) | Sections 3.3 and 6.1 of [Goodrich et al.] |

Tutorial 3 | ||

Lecture 18 | Circular linked lists, Sequence ADT | Sections 3.4 and 6.3 of [Goodrich et al.] |

Lecture 19 | Trees: Definition, Traversal algorithms | Sections 7.1 and 7.2 of [Goodrich et al.] |

Lecture 20 | Binary Trees: Properties, Application (expression trees) | Section 7.3 of [Goodrich et al.] |

Lecture 21 | Implementation of Trees Priority Queues, Selection and Insertion Sort |
Sections 8.1 and 8.2 of [Goodrich et al.] |

Lecture 22 | Heaps: Definition, Priority Queue implementation | Section 8.3 of [Goodrich et al.] |

Problem solving session | ||

Tutorial 4 | ||

Lecture 23 | Heap-sort, Quiz 1 discussion | Section 8.3 of [Goodrich et al.] |

Lecture 24 | Bottom-up heap construction, solving problems on heaps | Section 8.3 of [Goodrich et al.] |

Lecture 25 | Maps ADT | Section 9.1 of [Goodrich et al.] |

Problem solving session on trees and heaps | ||

Lecture 24 | Hash functions and hash codes | Section 9.2 of [Goodrich et al.] |

Lecture 25 | Hashing: Compression functions and collision handling (separate chaining) |
Section 9.2 of [Goodrich et al.] |

Quiz 2 | ||

Lecture 26 | Quiz-2 discussion Hashing: Collision handling via linear probing |
Section 9.2 of [Goodrich et al.] |

Lecture 27 | Hashing: Collision handling via quadratic probing and double hashing | Section 9.2 of [Goodrich et al.] |

Lecture 28 | Dictionary ADT and implementation guidelines | Section 9.5 of [Goodrich et al.] |

Lecture 29 | Skip lists: Search, insertion and deletion | Section 9.4 of [Goodrich et al.] |

Lecture 30 | Probabilistic analysis of skip lists | Section 9.4 of [Goodrich et al.] |

Problem solving session on hashing and skip lists | ||

Tutorial 5 | ||

Lecture 31 | Binary search trees: Definition, find and insert operations | Section 10.1 of [Goodrich et al.] |

Lecture 32 | Deletion in binary search trees, introduction to AVL trees | Sections 10.1 and 10.2 of [Goodrich et al.] |

Lecture 33 | AVL trees: Update operations | Section 10.2 of [Goodrich et al.] |

Problem solving session on search trees | ||

Lecture 34 | (2,4) trees: Introduction, insertion | Section 10.4 |

Tutorial 6 | ||

Lecture 35 | Dynamic programming: Matrix chain product | Section 12.2.1 |

Lecture 36 | (2,4) trees: Deletion | Section 10.4 |

Lecture 37 | Dynamic programming: Longest common subsequence | Section 12.2.2 |

Lecture 38 | Dynamic programming: Allocation problems | Chapter 1 of [Applied DP, Bellman and Dreyfus, 1962] |

Tutorial 7 | ||

Problem solving session on sorting, trees, heaps, dynamic programming |