Course: Data structures
Given by: Guy Kortsarz.
Office: 319 Business and Science Bldg.


Office hours: By appointment.

SOME RULES

1) The students must respect each other and also
must respect me. I must respect the students.

2) I am not allowed to talk on anything but Data Structures.
I will not answer any question that is not on data structure

3) If a student has a question, I stop the class and answer.

4) I will observe people participating. Asking questions and answering
The course must be a discussion. People who participate a lot
will get a bonus in their grade. Please participate.

5) There will be strict classes in which to submit theoretical
exercises. A person that submits late without an iron
solid reason will get a 0. If you do not submit in time even twice
I dont see how you can get better than D.

5) Work alone. If you will cooperate, I will know and your grade
will be cut by 1/2.

6) If you go to the web to find answers, I cant stop you.
But I will know. In such case
the 48 hours take home exam will become much harder.

7) I do not take names but you should attend every class.
The power points and PDF DO NOT cover
all the material. Many things will be taught in class.

8) WRITING PROGRAMS IS STRICTLY FORBIDDEN.
AT FIRST YOU WILL LOOSE SOME POINTS BUT LATER ALL POINTS.
LEARN HOW TO WRITE IN PSEUDOCODE. OR EVEN BETTER:
EXPLAIN IN WORDS. AN ALGORITHM IS AN IDEA AND SO CAN BE
EXPLAINED IN WORDS.



Credit:
1) Five theoretical exercises. 40 percent in total.
2) A programming assignments 10 percent.
3) A forty eight hours take home exam. 50 percent.

THE CLASS OF 12 of DECEMBER 2017 IS MADATORY.
IF A STUDENT WILL NOT APPEAR THIS WILL LEAD TO
BADE CONSEQUENCES,

Url:
http://crab.rutgers.edu/~guyk/courses.html

Old lecture notes here

New power point pdf notes collected from the web

Lecture 1 Powerpoint Running times and the O() notation
Lecture 2 PDF. Practicing pseudocode. Self made. S.
Lecture 3 PDF QUEUE STACKS and LINKED LISTS
Lecture 4 PDF. Practicing the log n Self made. S
Lecture 5 PDF. Priority QUEUES
Lecture 6 Introduction to probability Self Made S
Lecture 7 power point Skip lists
Lecture 8 Binary trees and traversal. Self made S.
Lecture 9 power point Binary Search Trees
Lecture 10 power point AVL trees
Lecture 11 power point Amortized Analysis
Lecture 12 powerpoint Splay trees
Lecture 13 power point 2-3 trees
Lecture 14 PDF Universal hash function part 1
Lecture 15 power point Universal Hash function part 2

Subjects covered:

O() and Omega() notations. Running times
for serial algorithms.

Math basics. The log n functions, summations and more.
Queues Stacks Linked Lists.
Introduction to probability
Skip lists
Heaps. Priority QUEUES: Insert(X,S)+ Delete-Max
Heapsort
A dictionary: Search Delete and Insert. How much time
these operations will take if we used a linked list or an array?
Trees. Representing of
general trees by binary trees
Scanning binary trees: Preorder, inorder, postorder
Computing properties of trees (like height) by recursion
Binary search trees and AVL Trees
Amortize analysis and Splay trees.
2-3 Balanced trees
Hash functions
Universal hash functions. Two different methods.
Book of the course: Introduction to algorithms by
Corman Rivest and Leiserson, and Stein


Theoretical exercise I For a pdf file
Theoretical exercise II For a pdf file
Theoretical exercise III For a pdf file
Theoretical exercise IV For a pdf file
Theoretical exercise V For a pdf file

A programming assignments:

Programming exercise I PDF version.
An example:

Exam for Fall 2012 PDF version