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

me. I must respect the students.

2) I need to stick to Data Structures.

Many times I am asked on different subjects.

But I cant answer.

3) If a student has a question, the class stops and I 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.

If not enough people will arrive I will take names.

5) There will be strict time to submit theoretical

exercises in class. 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. This is called the Rollo Thomasi legacy.

6) Do not look on the web for answers

7) ** 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. I AM SUPER SERIOUS

** Credit:**

1) Five theoretical exercises. 40 percent in total.

See the exercises below
2) A programming assignments 10 percent.

See it below
3) A forty eight hours take home exam. 50 percent.

The exam is not posted yet. The exam below is just an example
and will NOT be the home exam.

**Url:**

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

**Old lecture notes**
here

It will help you to take a look since it elaborates

on the same subjects and other subjects.

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

** Lecture 3 **
Practicing the log n function

This is ** important. **
Appears almost always.

This will be taken from
the old lecture notes.

** Lecture 4 PDF **
QUEUE STACKS and LINKED LISTS

Lecture 5 PDF
Application of Lists: Union Find

** Lecture 6 PDF. **
Priority QUEUES

** Lecture 7 power point. **
Binomial Heaps

** Lecture 8 ppt. **
Amortize Analysis

** Lecture 9 **
Introduction to probability Self Made

** Lecture 10 power point **
Skip lists

Lecture 11
Binary trees and traversal. Self made

** Lecture 12 power point **
Applications of binary trees to DS: compressing

** Lecture 13 power point **
Binary Search Trees

** Lecture 14 power point **
AVL trees

** Lecture 15 power point **
2-3 trees

** Lecture 16 PDF**
Universal hash function part 1

** Lecture 17 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.
**

**
Queues Stacks Linked Lists.
**

**
**
An application of lists: Union-Find

**
Introduction to probability
**

**
Skip lists
**

**
Heaps. Priority QUEUES: Insert(X,S)+ Delete-Max
**

or Delete-Min

**
Heapsort
**

**
Binomial Heaps: Add a union operation in O(log n) time.
**

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

**
Using trees to compress: Huffman trees.
**

**
Scanning binary trees: Preorder, inorder, postorder
**

Computing properties of trees (like height) by recursion

**
Binary search trees and AVL Trees
**

**
2-3 Balanced trees
**

**
Hash functions
**

**
Universal hash functions. Two different methods.
**

**
Perfect Hash function
**

** Book of the course:** Introduction to algorithms by

Corman Rivest and Leiserson, and Stein

Credit: 5 Theoretical exercises 40

percent

A programing exercise 10 perfect.

A home exam for 48 hours

50 percent.

** 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 of a previous exam.

** Exam for Fall 2012 ****
PDF version
**