Madhavan Mukund

Programming and Data Structures with Python

Sep–Dec 2021

Administrative details

• Instructor: Madhavan Mukund

• Teaching Assistants: Avirup Das, Shiuli Subhra Ghosh

• Lectures and Tutorials: Two live online classes each week. Tutorials as needed.

• Evaluation:

  • Quizzes on Moodle, programming assignments, final exam

  • Weightage approximately 10%, 50%, 40%, to be confirmed

  • Copying is fatal

• Text and reference books:

  • We will not be following any specific text book. There are plenty of resources online. You can find a list of books at the following link: PythonBooks

  • The official Python tutorial is a good place to start learning Python if you already have some programming background.

Course plan

This list is approximate and subject to change.

• Programming in Python

  • Names, values, control flow
  • Lists, dictionaries, strings
  • Exception handling, input/output and files
  • Basics of object-oriented programming

• Data structures and algorithmic techniques

  • Searching and sorting
  • Quantifying efficiency
  • Loop invariants
  • Stacks, queues, priority queues, heaps
  • Backtracking
  • Balanced search trees
  • Dynamic programming

• Python for data science

  • Processing data from tables, displaying charts and graphs
  • numpy, pandas and matplotlib libraries

Assignments

• Assignment 1, due 2 November, 2021
• Assignment 2, due 12 November, 2021
• Assignment 3, due 24 November, 2021
• Assignment 4, due 17 December, 2021
• Assignment 5, due 31 December, 2021

Lectures

• Lecture 1: 20 Sep 2021
  (Class Notes (pdf), Lecture Notes (pdf), Jupyter Notebook (ipynb), Lecture video)

  Introduction to algorithms and programming

  Example: computing gcd – names/variables, numeric and structured values (lists), for, if-else, induction/recursion

• Lecture 2: 23 Sep 2021
  (Class Notes (pdf), Class Notes (ipynb), Lecture video)

  Euclid's algorithm for gcd

  Introduction to Python: names, values, types; numeric values – int, float, arithmetic operators, comparisons, math library; boolean values; lists

• Lecture 3: 27 Sep 2021
  (Class Notes (pdf), Class Notes (ipynb), Lecture video)

  Control flow: defining functions, if-then-else

  Lists: concatenation, append

• Lecture 4: 30 Sep 2021
  (Class Notes (pdf), Class Notes (ipynb), Lecture video)

  Control flow: for loop, range(), while loop

• Lecture 5: 04 Oct 2021
  (Class Notes (pdf), Class Notes (ipynb), Lecture video)

  Nested loops, if-elif, truth values, list slices, mutable and immutable values, nested lists

• Lecture 6: 07 Oct 2021
  (Class Notes (pdf), Class Notes (ipynb), Lecture video)

  Mutable and immutable values, passing parameters to functions, name spaces, strings, basic input/output, type conversion, tuples

• Lecture 7: 11 Oct 2021
  (Class Notes (pdf), Class Notes (ipynb), Lecture video)

  Mutable and immutable values, dictionaries

• Lecture 8: 18 Oct 2021
  (Handwritten Notes (pdf), Class Notes (pdf), Class Notes (ipynb), Lecture video)

  Using dictionaries

  Implementation of lists, arrays, dictionaries

• Lecture 9: 21 Oct 2021
  (Handwritten Notes (pdf), Class Notes (pdf), Class Notes (ipynb), Lecture video)

  Experiments with lists, arrays, dictionaries

  Implementing a linked list using nested dictionaries

• Lecture 10: 25 Oct 2021
  (Lecture Slides (pdf), Lecture Slides Annotated (pdf), Class Notes (pdf), Class Notes (ipynb), Lecture video)

  User defined datatypes: classes and objects

  • Classes, Python Tutorial, Section 9.3

  • Errors and Exceptions, Python Tutorial, Section 8.1–8.3

• Lecture 12: 01 Nov 2021
  (Class Notes (pdf), Class Notes (ipynb), Lecture video)

  List comprehension, defining list functions inductively

• Lecture 13: 08 Nov 2021
  (Lecture Slides (pdf), Class Notes (pdf), Class Notes (ipynb), Lecture video)

  Inductive functions on lists

  Introduction to analysis of algorithms and data structures

• Lecture 14: 11 Nov 2021
  

  No class. Watch recorded lectures.

  1. Analysis of Algorithms ( Slides, Video )
  2. Comparing Orders of Magnitude( Slides, Video )
  3. Calculating Complexity ( Slides, Video )

• Lecture 15: 15 Nov 2021
  (Lecture Slides (pdf), Class Notes (pdf), Lecture video)

  Searching for a value in a list

  Sorting: selection sort, insertion sort, merge sort

• Lecture 16: 18 Nov 2021
  (Lecture Slides (pdf), Class Notes (pdf), Python experiments (pdf, ipynb), Lecture video)

  Sorting: mergesort analysis, quicksort, stable sorting

• Lecture 17: 22 Nov 2021
  (Class Notes (pdf), Class Notes (ipynb), Lecture video)

  Numpy, Pandas

• Lecture 18: 25 Nov 2021
  (Class Notes (pdf), Class Notes (ipynb), Lecture video)

  Pandas

• Lecture 19: 02 Dec 2021
  (Lecture Notes (pdf), Class Notes (pdf), Lecture video )

  Reading/writing files, string functions, pass/del/None, passing arguments to functions

• Lecture 20: 06 Dec 2021
  (Lecture Notes (pdf), Class Notes (pdf), Python notebook (pdf), Python notebook (ipynb), Lecture video )

  Backtracking, global variables

• Lecture 21: 09 Dec 2021
  (Lecture Notes (pdf), Class Notes (pdf), Lecture video )

  Stacks, queues, priority queues, heaps

• Lecture 22: 13 Dec 2021
  (Lecture Notes (pdf), Class Notes (pdf), Lecture video )

  Search trees

• Lecture 23: 16 Dec 2021
  (Lecture Notes (pdf), Class Notes (pdf), Lecture video )

  Balanced search trees (AVL trees)

  Memoization

• Lecture 24: 20 Dec 2021
  (Lecture Notes (pdf), Class Notes (pdf), Lecture video )

  Dynamic programming: Grid Paths, Longest Common Subword, Longest Common Subsequence

• Lecture 25: 23 Dec 2021
  (Lecture Notes (pdf), Class Notes (pdf), Lecture video )

  Dynamic programming: Edit Distance, Matrix Chain Multiplication