Tarique Anwar

Syllabus ♣

* Refer to the chapters of the book "T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, MIT Press, Third Edition, 2009.

Assessment Policy ♣

♣ Tentative
♦ Some Quizzes and Exams will be open-book/notes. The exact format will be announced one day before the scheduled date. Keep checking the announcements at the bottom of this page.

Textbooks

1. "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, and Clifford Stein, MIT press.
2. "Algorithm Design" by Jon Kleinberg and Eva Tardos, Pearson India.
3. "Algorithms" by Christos Papadimitriou, Umesh Vazirani, and Sanjoy Dasgupta, Mcgraw Hill Education.

Assignments and Exams

Check your marks from the download link here.
Check your attendance from the download link here.

♠ More than one student may have answered a question correctly, and got full marks. The factors considered to select the final Best Answers include correctness of the answer, richness of the provided information, organization of the presentation, and neatness of the writing.

Announcements

15/12/2018: All the marks including that of Assignment 5 have been updated. Check them from the section above or download from here.

12/12/2018: The Assignment 5 answer sheets are to be submitted to Gaurav in the Theory Research Lab (top floor, CSE department).

08/12/2018: Some project reports have been found plagiarised, and therefore marked zero. The marksheet has been update accordingly.

07/12/2018: The end-semester exam marks are out. Check them from the section above or download from here. The answer sheets will be shown tomorrow during 02-03pm in CS1.

05/12/2018: The submission due date for Assignment 5 has been extended to 12/12/2018.

02/12/2018: All marks and the PMT have been released. Check them from the section above or download from here. The answer sheets of Assignment 4 and Quiz 2 will be shown tomorrow during 10-11am in CS1.

Also check your final attendance record from the section above or here.

01/12/2018: Those who have not submitted their microproject presentations yet, they need to submit on or before 03/12/2018 (Monday). Proper submission instructions, as announced earlier, need to be followed.

30/11/2018: Assignment 5 is released. Download a copy from the Assignments section above.

26/11/2018: The microproject presentation schedule has been updated. Check the details here (click on the link). We will continue the presentations even after 09:50am on Wednesday (28/11/2018), and complete all presentations on the same day. Let me know immediately, if anyone has problem with the schedule.

24/11/2018: The microproject presentations will start from Monday in normal class times, according to this (click on the link) schedule. The presenters are themselves responsible to arrange their own laptop and set up the projector in CS1 in advance, so that there is no delay during the presentations.

24/11/2018: Update on exam syllabus.

Syllabus of Quiz 2: Chapters 22-24 (excluding Sections 22.5, 24.4 and 24.5), and 15-17 (excluding Sections 16.4 and 16.5), in the CLRS book.

Syllabus of End-Semester Examination: Chapters 1-14 (excluding Sections 11.3.3, 11.5, and 12.4), Chapters 22-24 (excluding Sections 22.5, 24.4 and 24.5), 15-17 (excluding Sections 16.4 and 16.5), and 34 (excluding Sections 34.4 and 34.5), in the CLRS book.

21/11/2018: We will start the class today at 09:30am, instead of 09:00am, in CS1.

20/11/2018: Quiz 2 update: As discussed in the class today, Quiz 2 has been rescheduled to start at 05:30pm on 25th November (Sunday) in CS1.

20/11/2018: We will have two consecutive extra classes tomorrow, starting from 9am in CS1.

19/11/2018: Quiz 2 is scheduled to start at 03:30pm on 25th November (Sunday) in CS1. The format of this quiz will be closed-book/notes, closed-time (1 hour). The syllabus includes all the topics covered in lectures after the mid-semester examination till date. These topics refer to the Chapters 22-24 (excluding Sections 24.4 and 24.5), 15-17 (excluding Sections 16.4 and 16.5), and 34 (selected topics to be announced later) in the CLRS book. Lecture notes till date have been uploaded in the Syllabus section above.

13/11/2018: An additional solution of Q1 of Assignment 3 has been uploaded in the Assignments section above. None of the submissions had the pseudocode in this much detail. Few students had written the pseudocode, but were incorrect.

Q5 of Quiz 1 has been taken as a micro-project by one group. Their technical report will be made available on the course webpage after its completion, as the solution for this question.

13/11/2018: We are planning to have Quiz 2 at 03:30pm on 25th November (Sunday). If any student has problem with this time/date, please let us know at an earliest.

12/11/2018: The answer sheets will be shown tomorrow (13/11/2018) in the morning during 11am-12pm in CS1/CS2 (whichever is free).

08/11/2018: Update on the Micro-Project guidelines.

1. The length of the technical report has to be at least 3.5 pages for the projects with only one student, and at least 5.5 pages for the projects with two students, in ACM SIG format. These pages may include reasonably sized figures, tables, and references.

2. The technical depth of the content is more important than its breadth.

3. The content has to be entirely in the authors' own words and properly cited. Any case of plagiarism will be strictly dealt with. The student will get an "F" grade in the course (in case of major plagiarism) or zero in the project (in case of minor plagiarism), depending on the severity.

4. The technical report has to be submitted on or before 25th November 2018, by emailing its soft copy in pdf to tarique@iitrpr.ac.in. The subject of the email should be "CS506 Micro-Project Technical Report - Group ID x", and the pdf should be named as CS506-project-x.pdf, where x is the group id in the shared project sheet.

5. The presentations will begin on 26th November 2018 during class times. Each presentation will have 10+5 minutes time to present the technical report at a high level. The presentation slides have to be submitted through email after presenting the project. The subject of the email should be "CS506 Micro-Project Presentation Slides - Group ID x", and the presentation slides should be named as CS506-presentation-x.ppt (or, CS506-presentation-x.pdf), where x is the group id in the shared project sheet.

6. All the project technical reports and presentation slides will be put online on the course webpage, except if there is some confidential research content or the student has any objection.

05/11/2018: The answer sheets will be shown tomorrow (06/11/2018) in the morning during 11am-12pm in CS1/CS2 (whichever is free). The best answers of Assingment 3 and Mid-Sem Exam have been uploaded (check the Assignments section above). The best answers of Quiz 1 will not be uploaded, as the performance of the entire batch was poor.

03/11/2018: Some students found Question 1 of Assignment 4 a bit confusing. Here is a small clarification. The graph may or may not contain these two components: 1) a cycle, 2) a Hamiltonian path. The problem is to determine if at least one of them exists in the graph- Yes or No? If Yes, at least which one (cycle or Hamiltonian path). If one of them is confirmed, it is not required to check the other. This question has been re-written in a better way in another document, uploaded in the Assignments section above.

02/11/2018: The complete attendance record till date has been released. It can be checked from the section above or here.

02/11/2018: All the marks have been released. They can be checked from the section above or here.

31/10/2018: Assignment 4 is released. Download a copy from the Assignments section above.

24/10/2018: Thanks for the great question asked in the class today, regarding the advantages of Bi-directional Dijkstra Algorithm over the Classical Dijkstra Algorithm. Here is the answer of this question. The worst case running time complexities of both these algorithms are same, but Bi-Directional Dijkstra is practically much faster, as it generally processes lesser number of vertices and edges. Have a look at these examples: Example 1, Example 2. Possibility of parallel processing of the forward and backward searches with simple modifications is of course another major advantage, additionally.

14/10/2018: The scheduled lecture on 16/10/18 (Tuesday) has been cancelled. This lecture will be re-scheduled sometime later.

12/10/2018: The assessment weightage of Micro-Project has been increased from 5% to 10%, and that of End-Sem Exam has be decreased from 35% to 30%. The last date to form groups and finalize the project title is 19/10/18 (Friday).

11/10/2018: As part of our regular Data Science Research Meeting, we have a presentation/discussion tomorrow on "IP-Tree: An Index for Indoor Spatial Queries" during 03:30pm-05:30pm. It will be presented by Gaurav Kumar (MTech thesis student) and the venue is Meeting Room, Ground Floor, CSE Building. This topic is very related to the CS506 course. Those interested on the topic are welcome to attend and participate in the meeting.

10/10/2018: Here are some guidlines for the Micro-Project.

1. Any algorithmic problem/topic that is not covered in the class, within the textbook or beyond, can be considered.

2. PhD students are recommended to select an algorithmic problem aligned with their thesis. You may also discuss with your supervisor to decide on the problem.

3. MTech students are recommended to select an algorithmic problem/topic of their interest. This is a good opportunity to set up the foundations for your MTech thesis/project.

4. The project has two requirements. The first requirement is to prepare a technical report in ACM SIG style, at least 3 pages long (approximately 3000 words). Download the ACM SIG alternate latex template from here. The structure/skeleton of the technical report may look like this. The second requirement is to present the study in front the class in the last week of the semester.

Once you are ready with your problem or topic for the Micro-Project, enter the details here, and leave the "approval" column blank.

04/10/2018: The performance of the whole class has been very poor in Quiz 1, much below my expectations. The questions in the mid-semester exam are going to be of similar kind (except Question 5 of Quiz 1). Manage your time well, and be precise in your answers. Good luck!

04/10/2018: The Assignment 2 answer sheets will be shown tomorrow (05/10/18, Friday) at 11:00am by the TAs in Room no 205, CSE Block. The students are recommended to check their marks and discuss with the TAs to clarify their doubts, if any.

03/10/2018: The mid-semester exam will be closed-book/notes and closed-time. The syllabus is same as Quiz 1.

03/10/2018: Assignment 3 is released. Download a copy from the Assignments section above. The completed assignments can be submitted to the Instructor in Room no. 205, CSE Block.

03/10/2018: The Assignment 2 marks are released in the Assignments section above. The marks are tentative. A time slot will be announced by our TAs after the mid-sem examination to show the answer sheets and discuss on doubts, if any.

Note that each student has been given a Secret Key, and the marks are displayed corresponding to the Secret Keys. Please send an email to our TAs from your official email id to get your Secret Key.

29/09/2018: One more chance has been given to submit the solution of Question 5 in Quiz 1. The students can email the photos of their hand-written solutions to the course instructor before 11:59pm, 30th September. In this case, the question will be marked out of 6 marks. The best performance out of the two trials (the answer submitted in the classroom and the one emailed next day) will be considered for totaling the marks.

28/09/2018: All lecture notes of the topics covered so far have been uploaded on this page. Refer to the Syllabus section above for the details.

27/09/2018: Quiz 1 is scheduled to start at 03:30pm on 29th September (Saturday) in CS1. The format of this quiz will be closed-book/notes, but open-time. The syllabus includes all the topics covered in the lectures so far. These topics refer to the chapters 1-14 in the CLRS book, excluding Sections 11.3.3, 11.5, and 12.4.

19/09/2018: Click on this Youtube link to see an excellent demonstration of the SELECT algorithm discussed in the class today.

19/09/2018: Those who have not submitted the Assignment 2 yet, can submit to our TA Rahul Pal Singh in the CSE Research Lab during 4-5pm today. If this time does not suit you, communicate to him through email and make arrangements for the submission.

15/09/2018: There was a typo in Question 3 of Assignment 2. It has been corrected and Assignment 2 has been updated with a new file now. Download the updated copy from the Assignments section above. Thanks to Abhishek Mishra, for pointing this out.

13/09/2018: Based on our discussion in today's class, Quiz 1 has been tentatively scheduled at 03:30pm on 29nd September (Saturday) in CS1. If any student has problem with this time/date, please let us know at an earliest. If no body raises any objection till 18th September (Tuesday), the tentative schedule will be finalized.

12/09/2018: We are planning to have the Quiz 1 at 2pm on 22nd September (Saturday). If any student has problem with this time/date, please let us know at an earliest.

11/09/2018: Few students were caught in the act of plagiarism in Assignment 1. They have been given zero marks in Assignment 1. Whoever gets caught in plagiarising any content now onwards, will get a complete zero in the Assignment section of assessment (which carries a weightage of 10%). The student will then have the final aggregated marks only out of the remaining 90% weightage.

10/09/2018: Assignment 1 answer sheets will be shown to the students tomorrow at 12:50pm by the TAs in CS1. The students are recommended to check their marks and discuss with the TAs, in case they of any question.

09/09/2018: Assignment 2 is released. Download a copy from the Assignments section above. The completed assignments can be submitted to the Instructor after the classes on Mon, Tue, and Wed.

09/09/2018: The Assignment 1 marks are released and can be viewed from this link. The marks are tentative. They can be revised if required. A time slot will soon be announced by the TAs to show the answer sheets to the students and discuss on discrepancies, if any.

06/09/2018: A student was recently caught in inappropriately marking attendance in the class. The student has been penalized by 3 attendances. Whoever gets caught in the same practice next time, will be penalized by 5 attendances, and this penalty will keep increasing by 2 each time.

23/08/2018: The Assignment 1 solutions are to be submitted to our TA Rahul Pal Singh during 02:30pm-04:30pm on Thursday and Friday (23-24/08/2018) in the Research Lab, Second Floor, CSE Block. His name is displayed on the door. If none of these times suit you, please email Rahul (also include me in cc), and arrange a suitable submission time on or before Friday.

21/08/2018: This announcement is to clarify a confusion in Assignment 1. Throughout this course, whenever it is asked to write down an algorithm, the students are supposed to write down the pseudocode for the algorithm steps, and a brief explanation of the pseudocode in natural language. For further clarification, refer to the style of Insertion Sort algorithm, Chapter 2, CLRS book.

18/08/2018: The lecture on 20/08/2018 (Monday) requires a basic background knowledge of asymptotic notations and solving recurrences (Refer Sections 3.1, 3.2, 4.3, 4.4, and 4.5, of CLRS Book). The students are expected to come prepared with these topics.

14/08/2018: Assignment 1 has been released. Download a copy from the Assignments section above. The completed assignments are to be submitted on or before the due date to our TA (Rahul Pal Singh) in the Research Lab, CSE Block.

08/08/2018: Due to shortage of seating space for students in CS2, the venue of our course CS506 has been changed to CS1 (Room no. 117). All the lectures from now on including the next lecture on Monday (13th August) will take place in CS1.

01/08/2018: Welcome to the course CS506 - Data Structures and Algorithms. It will be taught by Dr Tarique Anwar (myself). The first lecture will be given on 07th August (Tuesday) during 12:00pm-12:50pm in Lecture Hall 2 (Room no. 119) in the Department of Computer Science and Engineering (permanent campus), Indian Institute of Technology Ropar.

Note: This page will be updated regularly with all the helpful information and announcements. Students are recommended to keep checking the updates here.