Today : Thu, Apr 18, 2024

  • No meeting

Announcements

Back to Courses

Basic Information


What is this course about?

The past few decades have seen a lot of applications of Algorithmic techniques related to Algebraic structures in various sub-areas of theoretical computer science. In particular, areas like Algorithms, Computational Geometry, Cryptography and Complexity Theory have benefited immensely from these algorithmic techniques. This course aims to introduce these algorithms and some of their applications in a systematic manner. We will be particularly focusing on algorithmic problems and techniques related to groups, rings and polynomials.

Syllabus?

  • Algorithms for Groups & Applications : Basic group theory. Graph Isomorphism (GI) Problem, Automorphism Group, Permutation Groups. Generators, Schreier-Sims algorithm. Orbit and Stabilizer. Membership Testing in permutation Groups. Jerrum's Filter, Group Intersection Problem. Algorithms for bounded degree graph isomorphism, bounded eigen value multiplicity Graph Isomorphism.
  • Algorithms for Polynomials & Applications : Algorithm for GCD: Euclid’s algorithm. Hilbert’s basis theorem. Solving polynomial equations; ideal membership problem; Grӧbner bases: Buchberger’s algorithm. Representation, Factorization Problem. Polynomial Identity Testing problem; Applications to Primality Testing: AKS Primality test; Complexity of Polynomials. Polynomial and Matrix Multiplication Problems, Permanent vs Determinant problem and connections to Polynomial Identity Testing.

Target audience? Pre-requisites?

Any student who is interested in algebra and computation and having basic discrete mathematics training. We will be quickly covering the basic algebra needed and get to the "algorithmic part". But the course is intended to be self-contained. The course is intended to be reaching out students who would wish to see algorithmic ideas borrowed from and applied to rich algebraic structures.

Evaluation:

The course grading will be done in "absolute" scale rather than "relative" scale. That is, Grades will depend on four parameters listed in activities page with the following weightage.

  • Problem Sets (5 Nos x 7 Points Each = 35%)
  • Exam-1 (25%)
  • Exam-2 (25%)
  • Student Presentations (15%)

For an 'S' grade one needs to score at least 90 in the over-all evaluation. The cut offs for 'A' will be 80, 'B' will be 70, 'C' will be 60, 'D' will be 50, 'E' will be 40 and below 40 is the fail grade.

Some (Unsolicited) Advice !

Here are some thoughts which from our experience with this course, will help to get the maximum benefit out of it.
  • Keep at it, Don't fall behind ! - In a conceptual and deeply mathematical course like this, it takes time for ideas and terminologies to sink in and become a part of your easy language and thought process. This is particularly important in the beginning where more of algebraic concepts will be introduced. It is extremely important to put in consistent effort throughout the semester, rather than hoping to learn everything together at the end, right before the deadlines or tests. Even though we divide the course into themes, the ideas are so inexplicably connected across themes. So, even missing a few lectures, can cause difficulty.
  • Solve the problems from the problem sets ! - The problems in the problem sets are handpicked in order to ensure that you complete the thought process started in the lectures. The are released incrementally - that is, the problem relevant for a lecture reaches you on the same day evening. Thus, this is designed to enhance the understanding on that topic of discussion. The problem 5 of the problem set (which is the last one to be added to the set) will be added at least 7 days before the submission deadline for that problem set.
    A suggestion: Here is a useful scheme to work on the problem sets. Start working on the problems by yourself as soon as they are available (which will be the same day on which the material was taught - so this helps you learn and revise that material too). The earlier you start the more mature the thoughts will become before the deadline.
    About 3-4 days before the deadline, identify the problems that you think you might not be on the right track and talking to someone might help (at the expense of 10% of the credit - see below). Collect your thoughts (and mind-blocks) on those problems in a sheet of paper (consider this as a read only tape) - and hold a meeting with your partner for a discussion. The tape/paper is read-only - so the conversation and the details of it will not be (and should not be) recorded. After the discussion, reproduce, on your own, the ideas which helped you get over your mind-blocks and of course cite the source. This will naturally avoid plagiarism and you definitely will learn the solution and the reason it gets you over the mind-block.
    Make sure you submit before the deadline even if you could not solve all the problems. There will be discussion sessions for problem sets.

Policy Matters :

Here are some policy matters regarding problem sets :
  • Policy regarding Collaboration: Collaboration is allowed. The idea is to encourage collaboration on the harder problems (you should not collaborate on problems which you would otherwise be able to solve by yourselves), and encourage collaborations which has roughly an equal contribution from the participants. It is also a principle that one who solves the problem on his/her own should get the maximum credit. Based on this view, here are the rules of the game.
    • It is a strict rule that, even after collaboration the answer should be written individually and independently.
    • At most one collaborator is allowed for each problem in a problems set. The submission must contain, for each problem, the name of the collaborator whom you worked with and this should be reciprocated in your collaborator's submission. If inconsistencies are found, then both the submissions become invalid.
    • Collaborated solutions will be charged 10% of it's score.
    • The scheme is entirely based on trust. If two people collaborate and chose not to write the collaborators name - this scheme is not designed to respond. However, if detected (there might be random checks of various forms), the penalty for such unethical practices and plagiarism in submissions is extremely high (even if a reference to the original source is given).
  • Late Penalty: We will allow a delay of maximum two days from the deadline with penalty. To ensure fairness, delayed submissions will be charged with a multiplier of 0.8 of it's score.