CS314 Algorithm Design and Analysis

  • Course Outline

    Design of an efficient algorithm is a basic knowledge which every computer scientist should possess. This course is an introduction to algorithms for learners with at least a little programming experience. We expect that you have already done a course on data structure(CS121). It covers the common algorithms, algorithmic paradigms, and data structures used to solve these problems.

  • Taught by:
  • Class Meetings
    • Tuesday 12-1:30
    • Thursday 12 -1:30
  • The necessary evil - marks, exam, etc.

    The evaluation for the course will be based on midterm test1 (weightage 20%), midterm test2 (weightage 20%), assignments (weightage 10%) and final exam (weightage 50%). There will be 2-4 assignments that will carry weightage for your final evaluation. In addition, a number of problem sheets will be given which are for your practice, and in particular, solving them will be useful for getting good marks in the exams.

  • Some cautionary notes on tests, assignments and problem sheets

    This course is essentially a problem solving course, and so there will be lots of problems in the form of assignments and practice problems. Anything you hand in is assumed to be done by you on your own. If you had consulted any resource (including books, internet, or other persons), then please mention that in the work you hand in. Copying from any source without acknowledgement will result in unwanted consequences for everyone!

  • Video Lectures

Topics we will assume i.e. won't be covered here

  1. Sorting, Searching and Asymptotic Notation(Chapters 3, 4, 6 of CLRS)
  2. Basic graph algorithms including (Chapters 22, 23, 24 and 25 of CLRS)
    • BFS and Applications of BFS (connectivity, spanning tree/forest, shortest paths, checking for bipartiteness)
    • DFS and Applications of DFS (Topological sort, strongly connected components, finding articulation points)
    • Minimum Weight Spanning Trees (Prim's and Kruskal's algorithms including their implementations)
    • Shortest paths in weighted graphs (Single Source, All pairs, when weights are negative, ....)
  3. Basic Data Structures including
    • Arrays, lists, stacks, queues, hashing, binary heaps, balanced binary search trees (any one of AVL trees, Red Black Trees, B-trees), Disjoint Set union find (Chapters 6, 10, 11, 13, 18)
  4. Basics of Divide and Conquer, Greedy and Dynamic Programming(Chapters 2, 23, 24 of CLRS)

Topics we hope to cover (not necessarily in this order)

  1. Amortized analysis(Chapter 17 of latest edition CLRS)
  2. Binomial and Fibonacci heap (Chapters 20, 21 of *first* edition of CLRS)
  3. Union-Find data structure (Chapter 21 (from latest edition) except for 21.4 for which CLRS first edition Chapter 22.4)
  4. Polynomials and FFT (Chapter 9 (of latest edition) and Chapter 30).
  5. More Divide and Conquer Algorithms (Selection, FFT) (Chapters 9 and 30)
  6. Network Flows and Matching (Chapter 26)
  7. Advanced examples of Dynamic Programming
  8. Algorithms and Data Structures for String Matching (Chapter 32 + more )
  9. Linear Programming (Chapter 29)
  10. Lower Bounds and NP-completeness (Chapter 34 + )
  11. A brief tour of Randomization, Approximation and Parameterized Complexity (Chapters 5, 35 + )

Assignments

  • Kleinberg, J., and Tardos, E., Algorithm Design, Pearson Education, 2014
  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C., Introduction to Algorithms, MIT Press, 2009