Contents (hide)

Welcome to Algorithms 2 homepage

Course Description

In this course we will study advanced techniques for algorithm design, focusing on problems that are relevant in real-life applications. We will analyze the algorithms by diverse methods, such as number theory, complex numbers, algebraic and geometric tools etc.

Some of the topics are:

  • Primality testing
  • Number multiplcation and matrix multiplication
  • Fast Fourier Transform
  • RSA cryptosystem
  • PageRank algorithm
  • Markov chains
  • Advanced data structures, union-find
  • Quantum computing, Shor's factoring algorithm
  • Linear programming
  • Dynamic programming, edit distance
  • Polynomial identity testing and perfect matchings
  • Hashing
  • Randomized algorithms
  • Online algorithms

Course Schedule

Day Time Room
Sunday 12:00-14:00Building 90, Room 140
Thursday10:00-12:00Building 90, Room 233

Instructors

Name Web page E-mail Office Office hours
Eitan Bachmat http://www.cs.bgu.ac.il/~ebachmat ebachmat at cs dot bgu dot ac dot il Building 37, Room 119 Wednesday 12:00-14:00
Ofer Neiman http://www.cs.bgu.ac.il/~neimano neimano at cs dot bgu dot ac dot il Building 37, Room 215 Wednesday 12:00-14:00

Textbook

  1. S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani. Algorithms, online book.

Grading Policy

Final exam, 70%. Students MUST PASS the exam to pass the course.
Homework assignments, 30%. There will be 4 homework assignments.
You may hand in the exercises either by yourself or with one other student. Students whose partner has a valid reason not to hand in some assignment must still hand in the assignment. You may not hand in the assignments in groups larger than two. Cheating will not be tolerated.