Class Details

Evaluation

• 20%: I Minor Exam.
• 20%: II Minor Exam.
• 32%: Major Exam.
• 3%: Java lab viva.
• 25%: Programming assignments. Best 5 out of 7 will be counted.

TA assignment

Attendance

List of topics with tentative number of lectures in parentheses

Upto Minor I

• Data types and Data structures: Definitions and uses. (0.5)
• Fundamental data structures: linked lists and arrays. (1.5)
• Efficiency analysis and Asymptotic analysis. (2)
• Linear data structures: Stacks and Queues. (3)
• Tree data structures: Definitions, implementations and traversal algorithms. (4)
• Priority queues: Definition and simple implementations. (1)

Between Minor I and Minor II

• The Heap data structure. (3)
• Dictionaries: Definition and operations. (1)
• Hashing and hash maps. (1)
• Skip lists. (1)
• Binary Search Trees: Definition and algorithms. (2)
• Balanced Binary Search Trees: AVL Trees. (2)
• Multiway search trees: (2,4) Trees. (2)
• Sorting. (3)

Between Minor II and Major

• Text processing and Tries. (Self study not included in Major exam)
• Text compression. (Not included in Major exam)
• The Graph data type. (1)
• Data structures for Graph storage. (1)
• Graph traversals: BFS and DFS (3)
• Shortest paths. (2)
• Minimum spanning trees. (2)

Supplementary Material

• Data Structures and Algorithms in Java by Goodrich and Tamassia. You do not need to buy the book. We will roughly follow an older edition.
• Video. How to use asymptotic analysis to differentiate between algorithms. Posted 9th September 2016.
  
• Video. Growable stacks: An example of amortised analysis. Posted 18th August 2016.
  
• Link to discussion on amortised analysis including discussion of the binary counter problem. Author: Cornell University.
• * Link to Wikipedia entry on Abjad numerals, an ancient method of "hashing" text to integers that is still in use today.
• Video. Bottom-up heap creation done in-place in an array with no extra storage. Posted 8th September 2016.
• * Link to a tight asymptotic analysis of max load of a simple balls and bins setting (see Sec 1). Source: Course page of 15-859(M): Randomized Algorithms, Spring 2011, taught by Avrim Blum and Anupam Gupta at CMU. This is a link to lecture 8, dated 2nd February 2011.
• Video. Finding the inorder succesor and inorder predecessor in a Binary Search Tree. Posted 22nd September 2016.
• Video. 2,4 Trees (Deletion discussion begins at 30:00, Click here to go directly to deletion). Note that 2,4 trees are referred to as 2-3 trees in this lecture. Lecture by Dr P P Chakraborty, IIT Kharagpur. Lecture dated 27 June 2010. Posted 12 October 2016.
• Scanned lecture notes. Analysis of randomised quicksort (requires some understanding of the Treap data structure). Posted 13 October 2016.

Java Lab

• Java module.
• Supporting code.

Programming assignments

Please click here for the late assignment and late demo policies.

• Assignment 1. Due by 11:55 PM, Tuesday, 23 August 2016. Download statement, supporting files.
• Assignments 2 and 3. Download common statement, common supporting files.
  • Assignment 2 due by 11:55 PM, Saturday, 10 September 2016.
  • Assignment 3 due by 11:55 PM, Saturday, 21 September 2016.
• Assignments 4 and 5. Download common statement.
  • Assignment 4 due by 11:55 PM, Monday, 3 October 2016. Download supporting files.
  • Assignment 5 due by 11:55 PM, Wednesday, 19 October 2016. Download supporting files.
• Assignment 6. Due by 11:55 PM, Tuesday, 1 November 2016. Download statement, supporting files.
• Assignment 7. Due by 11:55 PM, Thursday, 1 November 2016. Download statement, supporting files.

Exam re-evaluation rules

• On a separate piece of paper write out the question numbers of the questions you want re-evaluated. Staple this paper onto your exam paper. Failure to do this will mean your paper will be ignored. However if it is only a retotalling issue you may write "totalling error" on the paper itself and submit it.
• If we do not increase your marks in any question/part of a question you have asked us to re-evaluate we will award you -1 for that part.
• Give a detailed explanation of why you want re-evaluation for each part. If you simply say "Recheck Q2.1", this will be ignored and a -1 will be awarded.
• Please try and understand why your solution has been graded down. Watch at the solutions and grading video, discuss with your friends and convince yourself that what you have done is right. If the note you write does not convince me that you have put in the effort required then you will get a -1. Saying "I think this is right" or "Why is this wrong?" will get you a -1.
• DO NOT write "My TA feels this is right." You can discuss your solutions with your TA, of course, but you are to make a judgement on your own and take responsibility for it. Saying that your TA feels this is right is not a protection against getting a -1.
• Finally, DO NOT approach me with your paper to discuss your solutions. Since it is not feasible for me to discuss everyone's solutions with them personally, it is only fair that I refuse everyone. Please respect my desire to be fair to your fellow students.