Algorithms-1 - CS21003

Autumn Semester - 2018

Instructors

Prof. Arobinda Gupta will be teaching Section-2 (Even Roll Numbers) and I will be teaching Section-1 (Odd Roll Numbers). The Timings below are same for both the sections, except that the classes for Section-2 will be in NR 224.

Course Timings

Lectures

Wednesday - 10:00 - 11:00 (NR223)

Thursday - 09:00 - 10:00 (NR223)

Friday - 11:00 - 12:00 (NR223)

Tutorial: Friday - 12:00 - 13:00 (NR223)

Teaching Assistants

Amrith Krishna, Abhijit Mondal, Ami Ladani, Gagan Sharma, Satendra Kumar

Reference Books

  1. Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms, Third Edition, MIT Press, 2009.
  2. Udi Manber, Algorithms -- A Creative Approach, Addison-Wesley, Reading, MA, 1989.
  3. Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.

Topics Covered

July 18th, 2018 Introduction: What is an algorithm?
July 19th, 2018 Efficiency of Algorithms
July 25th, 2018 Complexity Analysis
July 26th, 2018 Complexity Analysis contd...
July 27th, 2018 Data Structures: Binary Trees, Binary Search Trees
August 1st, 2018 Binary Search Trees: Basic Operations
August 2nd, 2018 Height Balancing, Red-black Trees
August 3rd, 2018 Red-black Trees: Insert Operation
August 8th, 2018 Hashing: Chaining
August 9th, 2018 Hashing: Open Addressing
August 10th, 2018 Hashing, Sorting - Merge Sort, Quick Sort
August 16th, 2018 Quick Sort: Average Case Analysis
August 17th, 2018 Comparison based sorting: lower bound, Linear time sorting: Counting sort, radix sort, bucket sort
August 23rd, 2018 Sorting, ADT, Heaps
August 24th, 2018 Heaps, HeapSort
August 29th, 2018 Order Statistics, Selection Problem
August 30th, 2018 Algorithm Design Techniques: Divide and Conquer
August 31st, 2018 Divide and Conquer, Dynamic Programming: Matrix Chain Multiplication
September 6th, 2018 DP: Matrix Chain Multiplication, Memoization
September 7th, 2018 DP: Longest Common Subsequence (LCS)
September 12th, 2018 Greedy Algorithms: Activity Scheduling
September 13th, 2018 Activity Scheduling, Fractional Knapsack
September 14th, 2018 0-1 Knapsack
September 27th, 2018 k-ary search trees, B-trees: insertion
September 28th, 2018 B-trees: deletion, Graph: definitions
October 3rd, 2018 Graphs, Traversal
October 5th, 2018 BFS, DFS, applications -- tree edges, topological sorting
October 11-12th, 2018 Minimum Spanning Trees, Prim's Algorithm
October 24th, 2018 Kruskal's Algorithm, Disjoint Set Data Structure
October 25th, 2018 Disjoint Set Data Structure, Shortest Paths
October 26th, 2018 Dijkstra's Algorithm, Floyd-Warshall
October 31st, 2018 String Matching: Rabin-Karp Algorithm
November 9th, 2018 String Matching: KMP

Announcements

Algo-1 Class Test - 2 will be on October 31st, 7:00 - 8:00 PM. Venue: CSE 107, 108, 119, 120. Seating arrangement.

Algo-1 Class Test - 1 will be on August 29th, 7:00 - 8:00 PM. Venue: CSE 107, 108, 119, 120. Seating arrangement.

Section -1 will have the next tutorial on August 21st, 2018 - CSE 108, 6-7 PM.

First Algo-1 class will be on July 18th, 10:00 - 11:00 AM (NR223). First Algo Lab will be on July 19th, 2:00 - 5:00 PM at CIC (PC_Lab II and PC_Lab V).