Course10610469740 lectures
Data Structures and Algorithms Design
Prof. Nitin Saxena · IIT Kanpur
About
The modern economy is run by algorithms. This a first-level course to introduce the students to the world of algorithm design, data structures, analysis, and programming. We'll start with the asymptotics notation which captures time and space of algorithms in the worst-case.
The basic data structures covered are -- array, list, queue, stack, matrix, tree, heap, set, and graph. The algorithmic paradigms covered are -- induction/recursion, divide-conquer, hashing, greedy-method, and dynamic-programming.
In the lectures, the theory will be backed up by numerous practical CS examples. The content is suitable for anyone who is mathematically inclined or computationally curious.
Intended audience: Computer Science & Engineering, Mathematics, Electronics, Physics, & similar disciplines.
Prerequisites: Very good analytical skills.
Lectures
Week 1
- Lecture 01: What is an Algorithm?
- Lecture 02: Efficient Algorithms
- Lecture 03: Sorting, Searching and Arrays
Week 2
- Lecture 04: Clever Algorithms
- Lecture 05: Asymptotics, Fast Max-Sum Subarray
- Lecture 06: Local Minima in 1D
Week 3
- Lecture 07: Local Minima in 2D
- Lecture 08: Efficient Local Minima in 2D
- Lecture 09: Recurrence & Efficient Data Structures
Week 4
- Lecture 10: Range Minima in 1D array
- Lecture 11: Abstract Data Structures: Lists
- Lecture 12: Linked Lists
Week 5
- Lecture 13: Binary Search Inspired Tree
- Lecture 14: BST : Search, Insertion
- Lecture 15: Balancing a BST, Stack Data Structure
Week 6
Week 7
Week 8
- Lecture 20: Divide and Conquer Paradigm
- Lecture 21: Integer Multiplication & Inversions
- Lecture 22: Graph Theory & Algorithms
Week 9
- Lecture 23: Graph DS & Breadth First Search
- Lecture 24: Complexity & Applications of BFS
- Lecture 25: Check Bipartiteness using BFS, Depth First Search
- Lecture 26: DFS tree and biconnected graph
Week 10
- Lecture 27: Articulation Points, Heap Data Structure
- Lecture 28: Binary Heap
- Lecture 29: Heapification
- Lecture 30: Augmented tree Data Structure
Week 11
- Lecture 31: Multi Increment and Dynamic Range Min Problems
- Lecture 32: Disjoint-Set Data Structure
- Lecture 33: Fast Union and the i-th Statistic Problem
- Lecture 34: i-th Statistic Problem: Approx Median
- Lecture 35: Greedy Algorithms: Job Scheduling
Week 12
Syllabus and materials
At NPTEL, as the course publishes them.
Credits and licence
- Institution
- IIT Kanpur
- Department
- Computer Science and Engineering
- Teacher
- Prof. Nitin Saxena
- Level
- Undergraduate
- Language
- English
- Subjects
- Computer science, Engineering
- Source
- NPTEL
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
- Who can watch
- NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed