CS213/293 : Data Structure and Algorithms 2023
Instructors : Ashutosh Gupta
Timings : 8:30 Monday, 9:30 Tuesday, 10:35 Thursday (Slot 1)
Venue : LH 101 (discussions on Piazza Join (Access code was given in class))
Optional tutorials :
Source material
- Text book: Introduction to Algorithms, third edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- Course syllabus: Slides define the syllabus. The content only before the problem section in slides is in the syllabus. In terms of problems, you must solve tutorial problems. All the other problems are optional. Any new concept defined there is not part of the course. If the concept appears in the exam, we will redefine it in the question paper.
Some rules
- We do not provide solutions of the problems that are not in the tutorials.
We can discuss your approach with you. Some TAs may give you answer to some
of the problems. It is their choice. However, they are not obligated to provide
written detailed answer.
- We do not discuss format of the question papers. Kindly do not ask.
- We do not discuss rubrics before the crib session.
Do not approach TAs and seek undue influence.
Interaction policy
- TAs will do a tutorial on a given set of problems at their chosen slot. Please discuss with your TA.
Evaluation structure
CS213
- Attendance quiz: 5% (half marks for attempt and half marks for 3+ options correct)
- Quizzes : 25% (2 quizzes)
- Midterm : 30% (2 hours)
- Final : 40% (3 hours)
CS293: three lab exams and a project
- Attendance quiz: 5%
- Lab exams : 60% (3 exams)
- Project : 35% (take home)
May change later.
Attendance Quiz URL
CS293 Lab exam/project schedule
- Lab exam 1: 2023-08-25 (week 4)
- Lab exam 2: 2023-10-06 (Week 9)[moved from week 8 to 9]
- Project description declared: 2023-10-13 (Week 10)
- Lab exam 3: 2023-10-27 (Week 12) [there was a mistake eariler!]
- Project submission deadline: 2023-11-10 (Week 14)
Tutorial solutions
Lectures
2023-07-31 : Week 1 - Introduction
- Monday lecture is moved to Saturday
- Introduction, Binary search, Big-O, and containers
- Lecture 1,
Lecture 2,
- Tutorial problems: 1.11, 1.12, 1.13, 2.5, and 2.6
2023-08-07 : Week 2 - Stack and queue
- Stack:implementation, growth, applications
- Queue: Array implementation, Linked list implementation
- Circular linked list, Doubly linked lists
-
Lecture 3,
Lecture 4
- Tutorial problems: 3.3, 3.4, 3.5, 4.10, 4.11, and 4.12
2023-08-14 : Week 3 - Dictionary and hashing
- Dictionary and Hashing
- Tuesday Holiday
- Lecture 5
- Tutorial problems: 5.9, 5.10, 5.11, and 5.12
2023-08-21 : Week 4 - Trees
- Trees and tree walks, binary search tree(BST)
- Search, Minimum, successor on BST
- Lecture 6, and
Lecture 7
- Tutorial problems: 6.11, 6.12, 6.13, 7.4, 7.5, and 7.6
2023-08-23T08:30 (Wednesday) : Quiz 1
- Syllabus: everything that is covered in lectures before the quiz.
- Venue: SIC201, CC101, CC103 and CC105
- You may bring an A4 sized cheat-sheet.
- Write only on single side. We will collect the sheet at the end.
- Bring your student id.
2023-08-28 : Week 5 - Binary search tree(remaining) and Red-black tree
- Insert and delete in binary search tree
- Average insertion time in binary search tree
- Insert and delete in red-black tree
- Lecture 8, Lecture 9
- Tutorial problems: 8.10, 8.11, 8.12, and 9.9
2023-09-04 : Week 6 - Text processing
- Pattern matching, KMP algorithm, Trie, and suffix trees
- Lecture 10,
Lecture 11
- Tutorial problems: 10.4, 10.5, 10.6, 11.7, and 11.8
2023-09-11 : Week 7 - Priority queue and Heap
- Priority queue, heap, and operations on heap
- Lecture 12
- Slides have a section tutorial problems.
2023-09-.. : Midterm week
- Syllabus: everything that is covered in lectures before the midsem.
- You may have an A4 sheet of paper with any text.
- Write only on single side. We will collect the sheet at the end.
- Bring your student id.
2023-09-25 : Week 8 - Compression
2023-10-02 : Week 9 - Sorting
- Merge sort, quick sort, radix sort, and bucket sort
- A bound on compression sorts
- Monday Holiday,Lecture 14
- Tutorial problems: look at the tutorial section
2023-10-09 : Week 10 - Algorithmic trading
2023-10-16 : Week 11 - Graphs: Basics and BFS
- basic definitions for graph, connected, tree
- Breadth-first search
- Lecture 15,Lecture 16
- Tutorial problems: look at the tutorial section
2023-10-18T08:30 (Wednesday) : Quiz 2
- Syllabus: everything that is covered in lectures before the quiz.
- Venue: Rooms: CC 101, CC 103, CC 105, and SIC 201
- You may bring an A4 sized cheat-sheet.
- Write only on single side. We will collect the sheet at the end.
- Bring your student id.
2023-10-23 : Week 12 - DFS for graphs and applications
- Depth-first search, 2-edge connected graphs
- DFS analysis, Topological sort, and strongly connected graph
- Lecture 17,Holiday on tuesday,
- Tutorial problems: look at the tutorial section
2023-10-30 : Week 13 - Minimum spanning tree
- Minimum spanning tree, Kruskal's algorithm, and Prim's algorithm
- Lecture 18
- Tutorial problems: look at the tutorial section
2023-11-06 : Week 14 - Shortest path
- Shortest path
- Lecture 19
- Tuesday and Thursday will be discussion lectures.(no attendance,ask questions!)
2023-11-..: End semester exam
Leave rules for non-medical reasons
Please follow the rules specified in the section 15 of the UG rule book for leave. Our interpretation of the section is that you need to get a leave approved by the head of CSE on the recommendation of your faculty advisor. Please submit the approved form/email/AMS on our form for leave, which is shared on Piazza. Once we have the approved leave we will apply the usual rules of compensation.