Messages

  • Aug. 7, 2016: webpage draft created.
  • Jan. 15, 2017: assignment 1 posted, due date Jan. 30, 2017, in class.
  • Feb. 1, 2017: assignment 2 posted, due date Feb. 13, 2017, in class.
  • Feb. 19, 2017: assignment 3 posted, due date Mar. 6, 2017, in class.
  • Mar. 6, 2017: assignment 4 posted, due date Mar. 20, 2017, in class.
  • Mar. 26, 2017: assignment 5 posted, due date Apr. 10, 2017, in class.
  • Apr. 9, 2017: assignment 6 posted, due date Apr. 24, 2017, in class.
  • Mar. 22, 2017, mid-term, in class.
  • May. 5, 2017, final, 10:15am – 12:15pm at BH 344.

Learning outcomes and competences

After attending this course, participants should be able to
  • Given an algorithm, analyze its correctness and running time.
  • Given a problem, design a correct and efficient algorithm for it, express it in a form that a programmer can easily convert into code.
  • Have an idea about what problems are intractable, and basic algorithms for those that are tractable.
  • Know the mathematical techniques that you will need to analyze your algorithms.

  • Course syllabus

    Course summary

    In this course we will discuss some basic techniques for algorithm design and analysis, including:
    1. Sorting and searching
    2. Divide-and-conquer
    3. Dynamic programming
    4. Greedy algorithms
    5. Graph algorithms
    6. NP-completeness
    Detailed list of topics is available in the course schedule below.

    Lecturer

    Qin Zhang
    Office hour: Wednesday 3pm-4pm, LH430A
    Email: qzhangcs@indiana.edu

    Associate Instructors
  • Erfan Sadeqi Azer
    Office hour: Tuesday 11am-12pm, LH215D
    Email: esadeqia@indiana.edu

  • Xiaomeng Ye
    Office hour: Friday 2pm-3pm, LH406
    Email: xiaye@umail.iu.edu

  • You can also talk to
  • Haoyu Zhang
    Office hour: Thursday 4pm-5pm, LH406
    Email: hz30@umail.iu.edu

  • Time and place

    1:00pm-2:15pm Monday/Wednesday, Ballantine Hall 344

    Texbooks

    Required Textbook: [KT] Algorithm Design, J. Kleinberg, E. Tardos. Pearson Education.
    Supplementary Textbook: [CLRS] Introduction to algorithms, T. Cormen, C.Leiserson, R. Rivest, C. Stein. 3rd edition. MIT

    Course schedule

    (subject to adjustments as we go along; [KT] denotes the textbook by Kleinberg and Tardos).

     Week   Date   Section   Content   Comments 
      1     Jan. 9     1. Introduction   Overview, efficiency     intro
      1     Jan. 11       Big-O notations     [KT] Ch 2.2  
      2    Jan. 16       No class     MLK day
      2    Jan. 18       Common running times     [KT] Ch 2.4  
      3     Jan. 23     2. Graphs     Basics     [KT] Ch 3.1  
      3     Jan. 25         BFS, implementation  
      Graph representation  
      [KT] Ch 3.2, 3.3  
      4     Jan. 30         Testing bipartiteness  
      DFS, implementation  
      [KT] Ch 3.2, 3.3  
      4     Feb. 1         DAG, topological sorting     [KT] Ch 3.6
      5     Feb. 6     3. Greedy     Interval scheduling     [KT] Ch 4.1
      5     Feb. 8         Interval scheduling (cont.)     [KT] Ch 4.1
      6     Feb. 13         Shortest path (Dijkstra's algo)     [KT] Ch 4.4
      6     Feb. 15         Dijkstra's algo (cont.)     [KT] Ch 4.4
      7     Feb. 20         Minimum Spanning Tree (MST)     [KT] Ch 4.5
      7     Feb. 22         MST (cont.)     [KT] Ch 4.5
      8     Feb. 27         MST (cont.)     [KT] Ch 4.5
      8     Mar. 1     4. Divide & Conquer     Mergesort     [KT] Ch 5.1  
      9     Mar. 6         Counting inversions     [KT] Ch 5.3  
      9     Mar. 8         Closest pair     [KT] Ch 5.4  
      10     Mar. 13         No class     Spring break  
      10     Mar. 15         No class     Spring break  
      11   Mar. 20     Mid-term Review          
      11   Mar. 22     Mid-term        
      12     Mar. 27     5. Dynamic Programming     Weighted interval scheduling   [KT] Ch 6.1, 6.2 
      12     Mar. 29         Subset-sum     [KT] Ch 6.4
      13     Apr. 3         Sequence alignment     [KT] Ch 6.6
      13     Apr. 5         Sequence alignment (cont.)     [KT] Ch 6.7
      14     Apr. 10     6. NP and Intractability     Polynomial reduction     [KT] Ch 8.1
      14     Apr. 12         Polynomial reduction (cont.)     [KT] Ch 8.2
      15     Apr. 17         NP-completeness     [KT] Ch 8.3
      15     Apr. 19         NP-completeness     [KT] Ch 8.4
      16   Apr. 24     Final Review I          
      16   Apr. 26     Final Review II          
      17   May 5     Final          

    Grading

    • Assignments 20%

      About six written assignments. Assignments are posted in Canvas, and are due before class on the due date, in hard copy. If you can, typeset in your favorite software and bring printed hard copy to class. If you are handwriting, make sure it is legible.
      No extensions or late homeworks will be granted.

    • Projects 15%

      You will be asked to solve a question from HackerRank website. You will have the choice over which programming language to use. You will write a report for your experience. Details can be found in this instruction.

    • Exams 65%

      (1) Mid-term 30%
      (2) Final 35%
      There will be NO make-up exams. If students have to miss the in-class midterm exam due to family/medical emergencies (and/or other reasons which will be granted on a case by case basis), they need to contact the instructor before the exams for permission, and their other exam grades will be re-weighted. Internship and job application interviews and paper deadlines are NOT proper reasons to miss an exam.

    Course policies

    For assignments, students may discuss answers with anyone, including problem approaches and proofs. But all students must write their own proofs, and write-ups. The names of all people that you have talked to should be listed at the beginning of the first page. If a solution comes from existing papers/web/books, they must be properly cited, and you must write the solution in a way that demonstrates your understanding (simply copying the solution will be considered as plagiarism, and will result an "F" for the entire course). All deadlines are firm. No late assignments will be accepted unless there are legitimate circumstances.
    For more details, see Indiana University Code of Student Rights, Responsibilities, and Conduct.

    Prerequisites

      CSCI-C241 "Discrete Structures for Computer Science", CSCI-C343 "Data Structures", and MATH-M 216 "Analytic Geometry and Calculus II" (or MATH-M 212 CALCULUS II). The prerequisites are enforced.