**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
**