Student Seminar – Fall 2012

Hours:

 
Instructor: Yefim Dinitz
            email: dinitz@cs.bgu.ac.il
            Tel:  647-7867
            Room: 37/203

Objectives:

This seminar is for M.Sc. students. Its main goal is learning the art of presenting research results to a wide CS audience. A good presentation should have the following three compulsory features:

 

1)    be informative;

2)    be understandable, and

3)    be interesting to the listeners.

 

Most of the topics will be on algorithms.

List of suggested topics: (++  – already caught, +- – one more student is needed, apply to the mentioned student)

1)    ++ Assignment problem paper (2)

2)    ++ Two algorithms for the shortest path problem paper (2)

3)    Scheduling with AND/OR constraints paper paper2 (2) –

4)    ++ Hanoi Towers problem with a relaxed placement rule (2)

5)    ++ Listing of all a,b-paths and of all MST paper (2) –

6)    ++ Canonical representation of a tree and tree isomorphism (2)

7)    ++ Reductions between transitive closure and BMM paper (1) and

Finding all frequent elements paper (1)

8)    ++ Scalable Content Addressable Network (2)

9)    ++ Leader Election in a chain of processors paper (2)

 

10) ++ Finding all occurrences of a pattern in a text (2)

11) ++ Suffix trees and their applications (2)

12) Optimal string alignment with Hirschberg space saving (2) –

The textbook for items 10-12 is D.Gusfield "Algorithms on Strings, Trees, and Sequences"; Aranne library has it.

 

13) Finding an optimal 3-connected vertex sub-graph paper (2) –

14) Representation of all 1-, 2-, and 3-cuts in a graph paper (2) –

15) Dinitz network flow algorithm paper paper2 (2) –

16) Preflow-Push network flow algorithm paper + [CLRS] (2) –

17) Circuit layout in a triangle area paper (2) –

18) Compact layout of Butterfly circuit paper (2) –

 

19) ++ Genetic algorithms (2)

20) ++ Historical image processing paper paper2 (2)

Additional topics of students' interest may be suggested to the instructor consideration. When presenting a topic unfamiliar to the Seminar class, a very good introduction would be needed.

Course rules:

Attendance is compulsory. Up to two absences at the Seminar meeting will be tolerated.

Lecture preparation:

1.     The first meeting on the lecture should be held in the first half of the week before one that you lecture on. In more detail:

 

                             either on Sunday afternoon-evening,

                             or on Monday either at 12 or in the evening,

                             or on Tuesday between 13 and the early evening.

2.     After that, a presentation draft (in Power-Point) should be sent, about the week-end. It should contain the entire structure of the presentation and detailing of some its parts (of about a third of them). The purpose is to check the presentation style. Comments on the draft would be either sent back by e-mail, or be discussed at an additional meeting.

3.     The full presentation should be sent on Tuesday morning the latest. Some polish (hopefully) comments will be sent back on it.

4.     In the (regular) case when two students present one topic, each one shows his/her part to the partner, for checking. Each version of the presentation file is sent to the instructor only after its checking by the partner.

5.     After the lecture, the presentation files should be sent to the instructor. They will be published at the course web page.

Listening is expected to be active. Asking (relevant) questions is appreciated. Each student should be active at some substantial part of the lectures.

Announcements:

1)   See in the list on a few topics, where students look for partners.

2)   Course rules are published.

3)   There will be no meeting on December 7.

Instead, a complementary meeting is scheduled to Tuesday, December 20, between 12 to 14, room 102/28.

Topics scheduled:                          

Last modified: January 29, 2012 Yefim Dinitz