marat.snowbear's blog

Algorithms course on Coursera
By marat.snowbear, history, 9 years ago, In English

I'd like to inform you that on 30th of June on Coursera will start second session of Tim Roughgarden's "Algorithms: Design and Analysis, Part 1" course. I took first session of this course a couple of years ago, in fact this is a source of my initial knowledge about algorithms and data structures and I started taking part in competitive programming contests soon after finishing second part of the course. I would definitely recommend taking it, I'd say that it should be interesting and useful for CF green & blue rating zone coders. The course consists of video lectures, quizzes and programming assignments (it's not a pure theory class) and will take approximately 4-8 hours per week to finish it successfully.

To give you an idea on topics covered by this course, let me just copy the course syllabus here:

Week 1: Introduction. Asymptotic analysis including big-oh notation. Divide-and-conquer algorithms for sorting, counting inversions, matrix multiplication, and closest pair.

Week 2: Running time analysis of divide-and-conquer algorithms. The master method. Introduction to randomized algorithms, with a probability review. QuickSort.

Week 3: More on randomized algorithms and probability. Computing the median in linear time. A randomized algorithm for the minimum graph cut problem.

Week 4: Graph primitives. Depth- and breadth-first search. Connected components in undirected graphs. Topological sort in directed acyclic graphs. Strongly connected components in directed graphs.

Week 5: Dijkstra's shortest-path algorithm. Introduction to data structures. Heaps and applications.

Week 6: Further data structures. Hash tables and applications. Balanced binary search trees.

There is a second part of this course as well which covers greedy algorithms, dynamic programming and NP hard problems, I would recommend taking it as well but it turns out that there was a session of it which finished recently, I don't know when they will schedule the next one but I guess you can still watch the lectures.

  • Vote: I like it
  • +93
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

And while being on this topic let me also mention that this week Coursera started another session of Robert Sedgewick's Algorithms, part 1 course, you can still join, I'm going to watch these lectures as well.

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Are there any special prerequisites for this course? and are all kinds of data structures ( i know not all can be taught but those which are taught are useful?) taught in depth in it or we need to know data structures before taking this course?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need to know at least one programming language to do programming exercises and that's mostly it. No background in algorithms or data structures is necessary for this course. Quote from the course's page:

    Required background: How to program in at least one programming language (like C, Java, or Python); and familiarity with proofs, including proofs by induction and by contradiction. At Stanford, a version of this course is taken by sophomore, junior, and senior-level computer science majors.

    Whatever is included in this course is explained very well with attention to details. Obviously the field of algorithms and data structures includes much more than this course's material, that's why I said that is good source of basic knowledge — if you want to advance further you will need to learn much more but the course itself is a good start point.

    → Reply