In this course, we will cover basic technique for the design and analysis of efficient computer algorithms for solving various kinds of problems. The prerequisites for this course include Data Structures and Discrete Mathematics. Hence, you are assumed to have already familiar with basic data structures like stacks, queues, tress, linked lists etc., and basic concepts of discrete mathematics, such as basic mathematical identities, series summations and recurrences.

The course webpage will contain many materials (for example, assignments) related to the course. Please check the course webpage frequently (for example, at least once in every two days). You will be responsible for missing an assignment posted on the course webpage if you do not check the webpage frequently.

The following information on assignments and gradings are tentative and subject to change depending on the progress in the class. It is expected that there will be 3 assignments, 2 quizzes and 1 final examination. The final exam will be comprehensive. Each assignment will involve solving some excercise problems and/or writing programs implementing some algorithm. Assignments must be handed in class on the date specified. No late assignments will be accepted. Discussions with other students about assigments is allowed, but the work handed in must be the student's own work. Tentative weights of the assignments and exams in the final grading is as follows:

Topics to be covered tentatively includes the following (they are subject to change if necessary):

• Some representative problems
  • Stable matching type problems
  • Five representative problems
• Basics of Algorithm Analysis
  • Computational Tractability
  • Asymptotic Order of Growth
  • Common Running Times
• Graphs
  • Basic Definitions and Applications
  • Graph Traversal
  • Testing Bipartiteness
  • Connectivity in Directed Graphs
  • DAGs and Topological Ordering
• Greedy Algorithms
  • Interval Scheduling and Partitioning
  • Scheduling to Minimize Lateness
  • Optimal Caching
  • Shortest Paths in a Graph
  • Coin Changing Problems
  • Selecting Breakpoints
  • Minimum Spanning Tree
  • Clustering
• Divide and Conquer approach
  • Mergesort
  • Counting Inversions
  • Closest Pair of Points
  • Integer Multiplication
  • Matrix Multiplication
  • Convolution and FFT (if time permits)
• Dynamic Programming approach
  • Weighted Interval Scheduling
  • Segmented Least Squares
  • Knapsack Problem
  • RNA Secondary Structure
  • Sequence Alignment (only if we have extra time)
  • Shortest Paths
  • Detecting Negative Cycles in a Graph
• Computational Intractability
  • Polynomial-Time Reductions
  • Definition of complexity classes P,NP,EXP
  • NP-Completeness
  • co-NP and the Asymmetry of NP
  • NP-completeness reductions

Assignment 1 (first two problems) (PDF file, deadline: September 27 in class)

• Solution of first two problems of Assignment 1
• Statistics (out of 60):

  Maximum	60
  Minimum	15
  Average	49.5

Assignment 1 (remaining two problems) (PDF file, deadline: October 18 in class)

• Solution of remaining two problems of Assignment 1
• Statistics (out of 40):

  Maximum	40
  Minimum	9
  Average	35.85

Assignment 2 (first two problems) (PDF file, deadline: November 13, in class)

• Solution of first two problems of Assignment 2
• Statistics (out of 50):

  Maximum	50
  Minimum	15
  Average	46.19

• Solution of the third problem of Assignment 2
• Statistics of Assignment 2 third problem (out of 50):

  Maximum	50
  Minimum	20
  Average	43

Midterm I will be on Thursday October 18 in class. The syllabus is from the beginning (first class) up to and including the last lecture on greedy method taught on September 27

• Statistics of midterm I (out of 100):

  Maximum	100
  Minimum	24
  Average	79.5

Midterm 2 will be on Tuesday November 27 in class. The syllabus covers the divide-and-conquer and the dynamic programming chapters

• Statistics of midterm 2 (out of 100):

  Maximum	100
  Minimum	10
  Average	91.22

Assignment 3 (PDF file, deadline: December 6, in class)

All graded assignments are avaiable outside the office of the instructor (933 SEO)

• Solution of Assignment 3
• Statistics of Assignment 3 (out of 50):

  Maximum	50
  Minimum	0
  Average	44.1

• Some Representative Problems
  • Demo of propose-and-reject approach

• Basics of Algorithm Analysis

• Graphs
  • Demo of topological ordering algorithm

• Greedy algorithms (Interval Scheduling and Partitioning, Scheduling to Minimize Lateness, Optimal Caching, Shortest Paths in a Graph, Coin Changing Problems, Selecting Breakpoints)
  • Demo of interval scheduling algorithm
  • Demo of Dijkstra's algorithm for shortest paths

• Greedy algorithms (Minimum Spanning Tree, Clustering)

• Divide and Conquer approach (Mergesort, Counting Inversions, Closest Pair of Points, Integer Multiplication, Matrix Multiplication)
  • Demo of merge
  • Demo of merge and count

• Divide and Conquer approach (Convolution and FFT)

• Dynamic Programming approach (Weighted Interval Scheduling, Segmented Least Squares, Knapsack Problem, RNA Secondary Structure, Sequence Alignment)

• Dynamic Programming approach (Shortest Paths, Detecting Negative Cycles in a Graph)

• Computational Intractability (Polynomial-Time Reductions)

• Computational Intractability (Definition of complexity classes P,NP,EXP, NP-Completeness, co-NP and the Asymmetry of NP)

• Computational Intractability (NP-completeness reductions)