Course: Data structures
Given by: Guy Kortsarz.
Office: 319 Business and Science Bldg.
Office hours: By appointment.
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
THE CLASS IN 11 OF DECEMBER IS A MUST SHOW CLASS
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.
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.
Lower bound proof for finding the min plus the max. Lower bound for max and min.
Lecture 4 PDF QUEUE STACKS and LINKED LISTS
Lecture 5 PDF Application of Lists: Union Find
Lecture 6 PDF. Priority QUEUES
Practice exercises Here
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 pdf Augmenting data structures
Lecture 16 PDF Universal hash function part 1
Lecture 17 power point Universal Hash function part 2
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
Heaps. Priority QUEUES: Insert(X,S)+ Delete-Max
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
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
A programing exercise 10 percect.
A home exam for 48 hours
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