Given by: Guy Kortsarz.
Office: 319 Business and Science Bldg.
Office hours: Wednesday. I will see you at any hour unless I have a deadline.
Url:
http://crab.rutgers.edu/~guyk/courses.html
Subjects covered:
Basic algorithms
O() and Omega() notations
Running times of
algorithms
Greedy algorithms. Exhaustive search
Divide and conquer. Dynamic programming
Graphs and Euler paths
Finding shortest paths in graphs
Free trees and minimum spanning trees
The algorithms of Prim and Kruskal
DFS on undirected graphs
An algorithm for finding 2-connected components
Book of the course: Introduction to algorithms by Cormen Rivest and Leiserson
You dont need to buy the book. I will give a printout on all
algorithms and of some proofs
Credit:
1) Exercises: there will be 4 exercises (to be posted later)
each worth 5% so 20% for exercises.
1) Midterm 30%
2) Exam: 50%
Algorithms, exercises and handouts.
Theoretical exercises, examples:
Supplementary Exercise: For a postscript file and For a pdf file
Examples of exercises (with solutions). The exercises for the course will be posted later
Exercise I: For a postscript file and For a pdf file
Exercise II: For a postscript file and For a pdf file
Exercise III: For a postscript file and For a pdf file
Exercise IV: For a postscript file and For a pdf file
Some algorithms and proofs:
Basic algorithms: For a postscript file and For a pdf file
Skeleton of a program: For a postscript file and For a pdf file
Coin Exchange: For a postscript file and For a pdf file
The subset sum algorithm: For a postscript file and For a pdf file
The BFS algorithm: For a postscript file and For a pdf file
BFS proof: For a postscript file and For a pdf file
Dijkstra proof: For a postscript file and For a pdf file
Prim correctness For a postscript file and For a pdf file
Running time of Prim and correctness of Kruskal: For a postscript file and For a pdf file
The DFS algorithm: For a postscript file and For a pdf file
The DFS algorithm with low-number computation: For a postscript file and For a pdf file
The bio-connected components algorithm For a postscript file and For a pdf file
Previously given mid-terms:
Mid-term 1, with solutions: For a postscript file and For a pdf file
Mid-term 2, with solutions: For a postscript file and For a pdf file
Mid-term 3, with solutions: For a postscript file and For a pdf file
Mid-term 4: For a postscript file and For a pdf file
Mid-term 5: For a postscript file and For a pdf file
Mid-Term 6 with solutions For a postscript file and For a pdf file
Midterm 7 For a postscript file and For a pdf file
Midterm 8 For a postscript file and For a pdf file
Midterm 9 For a postscript file and For a pdf file
Midterm 10: For a postscript file and For a pdf file
Previously given exams:
Exam 1, with solutions: For a postscript file and For a pdf file
Exam 2, with solutions: For a postscript file and For a pdf file
Exam 3: For a postscript file and For a pdf file
Exam 4: For a postscript file and For a pdf file
Exam 5: For a postscript file and For a pdf file
Exam 6: For a postscript file and For a pdf file
Exam 7: For a postscript file and For a pdf file
Exam 8 For a postscript file and For a pdf file
Exam 9: For a postscript file and For a pdf file
Exam 10: For a postscript file and For a pdf file
Exam 11: For a postscript file and For a pdf file
Exercise I: For a pdf file
MID TERM FALL 08: For a pdf file
Exercise II: For a pdf file
Exercise III: For a pdf file
Fall 08, Exam: For a pdf file