CS213/293: Data Structure and Algorithms 2024
Instructors: Ashutosh Gupta
Timings: Lectures 11:00-12:30 Wednesday-Friday (Slot 6), Lab Friday 14:00-17:00
Venue: LA001
(discussions on Piazza )
Optional tutorials:
Source material
- Textbook: 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.
Interaction policy
- No contact with TAs about the course via non-official channels, including WhatsApp messages.
- TAs will do a tutorial on a given set of problems at their chosen slot. Please discuss this 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: 25% (best 3 out of 4 lab exams)
- Project: 20% (take home)
May change later.
Attendance Quiz URL
CS293 Lab exam/project schedule
- Lab exam 1: 2024-08-23 (Week 4)
- Lab exam 2: 2024-09-(14-22) (Midsem week: Department timetable)
- Lab exam 3: 2024-10-18 (Week 11)
- Lab exam 4: 2024-11-08 (Week 14)
- Project description declared: 2024-10-13 (Week 12)
- Project submission deadline: 2024-11-10 (Week 14)
Tutorials
- Tutorial problems: look at the tutorial section of slides
CS213 Lectures and quizzes
2024-07-29: Week 1 - Introduction
Basic data structures
2024-08-05: Week 2 - Stack and queue
- Implementations: array, (circular/doubly)-linked list
- Growth and applications
-
Lecture 3
2024-08-12: Week 3 - Dictionary and hashing
- Dictionary problem, Hashing, Hash functions, and open addressing
- Lecture 4
Trees
2024-08-19: Week 4 - Trees and Binary search tree
- Trees, tree walks, binary search tree(BST)
- Search, insert, Minimum, and successor on BST
- Lecture 5 and Lecture 6
2024-08-28T08:30 (Wednesday): Quiz 1
- Exam rules are listed below.
- Venue: LA 001, LA 002 and LA 201
2024-08-26: Week 5 - Red-black tree
- (remaining)Delete in BST, average insertion time in BST
- Red-black tree, Insert and delete in red-black tree
- Lecture 7
2024-09-02: Week 6 - Priority queue and Heap
- (remaining) delete in red-black tree
- Priority queue, heap, and operations on heap
- Lecture 8
Handling strings
2024-09-09: Week 7 - Text processing
2024-09-(14-22): Midterm week
- Syllabus: everything that is covered in lectures before the midsem.
- See the exam rules below!
2024-09-23: Week 8 - Compression
Graph
2024-09-30: Week 9 - Graphs: Basics and BFS
- Basic definitions for graph, connected, tree, breadth-first search
- Since Wednesday is holiday, the lecture will happen at 2024-10-01T17:30 in LA002
- Lecture 12 and Lecture 13
2024-10-07: Week 10 - DFS for graphs and applications
- Depth-first search, 2-edge connected graphs
- DFS analysis, Topological sort, and strongly connected graph
- Lecture 14,
More basics: Sorting and union-find
2024-10-14: Week 11 - Sorting
- Since I am travelling on wednesday, no lecture!
- Merge sort, quick sort, radix sort, and bucket sort
- A bound on comparison sorts
- Lecture 15
Algorithms on weighted graphs
2024-10-21: Week 12 - No lectures (Instructor is away)
- CS228 will run in this slot. So please come to the class.
2024-10-23T08:30 (Wednesday): Quiz 2
- Venue: LA 001, LA 002 and LA 201
- Syllabus: everything that is covered in lectures before the quiz.
- See the exam rules below!
2024-10-28: Week 13 - Union find and minimum spanning tree
- Lectures will run in slot 4 and 6 (four lectures Monday(LA002 11:30-13:00),Tuesday(LA002 8:30-9:30),Wednesday(LA001 11:00-12:30),Friday(LA001 11:00-12:30); Total: 5.5 hours)
- Union find
- Minimum spanning tree: Kruskal's algorithm and Prim's algorithm
- Review lecture on Friday (ask questions!)
- Lecture 16, and Lecture 17
2024-11-04: Week 14 - Shortest path
- Lectures will run in slot 4 and 6 (three lectures Monday(LA002 11:30-13:00),Tuesday(LA002 8:30-9:30),Wednesday(LA001 11:00-12:00); Total: 3.5 hours)
- Shortest path: Dijkstra's algorithm
- Review lecture on Tuesday (ask questions!)
-
Lecture 18
- No lecture on Friday since we are running ahead!
2024-11-22: End semester exam
Some rules
- We do not provide solutions to the problems that are not in the tutorials.
We can discuss your approach with you. Some TAs may give you answers to some
of the problems. It is their choice. However, they are not obligated to provide
written detailed answers.
- We do not discuss the format of the question papers. Kindly do not ask.
- We do not discuss rubrics before the rebuttal session.
Do not approach TAs and seek undue influence.
- All exam rebuttal sessions will be physical and need to be done by yourself.
- Missing theory exams: prorated scores up to 30% of the course. Otherwise, makeup exam.
- Missing lab: Upto one miss, no re-exam. Otherwise, like the theory exams.
Exam rules
- Syllabus: everything that is covered in lectures before the exam.
- You may bring an A4-sized cheat sheet for theory exams. Write only on a single side. We will collect the sheet at the end. Write your rollno on the sheets.
Cheatsheet is NOT allowed for the lab exams.
- Bring your physical student ID.
- Please write pseudo codes when we ask for the algorithms.
- Please do not block the entry of the lecture halls or walkways by your bags. Keep them on the dais.
- Only bring a pen and a water bottle. All other items are prohibited. Digital devices (phones, smartwatches, calculators, etc.) are strictly prohibited.
Turn them off and store them with your belongings.
- Keep your area clean. You are responsible for any litter around you.
- Please be seated in the assigned room. Your answersheet will not be corrected if you are seated in the wrong room.
- We will not allow entry after five minutes before the exam.
- You cannot leave exam hall without permission.
- For biobreak, only one student is allowed to leave the exam hall accross
all rooms. Please ask TAs.
Leave rules for non-medical reasons
Please follow the rules specified in 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 compensation rules.
Attendance hacking challenge!
- Here is the source code of the attendance system
- If you can change your attendance by finding a flaw in the system, you will receive a grade bump!
- Ground rules: DO NOT TRY TO STEAL MY PASSWORD! Once you find a flaw, please report it to me and do not share it with others.