Jia (Kevin) Liu,

Assistant Professor of Electrical and Computer Engineering, The Ohio State University

  • Home
  • Research
  • Publications
  • Awards
  • Grants
  • Activities
  • Teaching
  • My Group

COM S 311: Design and Analysis of Algorithms
(Spring 2020, Section B)
[Link to Canvas]


Personnel

Instructor: Jia (Kevin) Liu, Assistant Professor, Dept. of Computer Science
Contact: 209 Atanasoff Hall, jialiu@iastate.edu
Time & Location: Tue/Thu 3:40pm -- 5:00pm, 0124 Ross Hall
Office Hours: Thu 11am -- 12pm

Course Objectives

    • Know a set of standard algorithms (and data structures) and be able to model a problem to use them.
    • Gain a strong foundation in designing algorithms based on common techniques, including greedy, divide and conquer, dynamic programming, etc.
    • Be able to reason about correctness of algorithms, either by proof or providing a counterexample.
    • Be able to recognize intractable problems and have an idea on how to develop approximation algorithms.
    • Be able to implement algorithms given their description.

Course Materials

    • There is no required textbook.
    • Recommended Book 1: [KT] J. Kleinberg and E. Tardos, "Algorithm Design," Pearson, 2005.
    • Recommended Book 2: [CLRS] T. Corman, C. Leiserson, R.L. Rivest, and C.E. Stein, "Introduction to Algorithms," MIT Press, 2009.

Homework and Programming Assignments

    • Home works and programming assignments will be assigned over the semester.
    • There will be around 5-8 home works and 2 programming assignments. A programming assignment and a homework might be assigned at the same time.
    • All programming assignment must be written in Java and submitted electronically to the Canvas system. Homework can be written or typed.
    • Homeworks should be submitted via Canvas. Homework discussions should go to Piazza (sign-up link here).

Exams

There are two midterms and a final exam. Dates for midterms are Feb. 27 and Apr. 7. The date for final exam is TBD.

Grading Policy

    • Homework: 15%; Programing Assignments: 20%; Midterm Exam 1: 20%; Midterm Exam 2: 20%; Final Exam: 25%

Late Policy

Without the consent of the instructor, 1-day late homework submission will incur 25% penalty, and late submission beyond 1 day will result in a grade of zero. In the case of an emergency (sudden sickness, family problems, etc.), an after-the-fact notice is acceptable. But we emphasize that this is reserved for true emergencies.

Schedule

Here is an estimated class schedule, which is subject to change depending on lecture progress and/or class interests. Please check for latest adjustments.

Class Date Topics Lecture Topics Lecture Notes Assignments
1 Jan. 14 Basic Algorithms Analysis Big-O Analysis
Basic Proof Techniques for Correctness
Lecture 1
2
Jan. 16

3
Jan. 21

4
Jan. 23

5 Jan. 28
Common Data Structures
BST: Add/Delete, Search, Max/Min
Balancing BST: Red-Black Tree, Treaps
Hashing Functions and Applications
Heaps: Max/Min Heaps, Maintain&Construct
Lecture 2

6 Jan. 30

7 Feb. 4

8 Feb. 6

9 Feb. 11

10 Feb. 13

11 Feb. 18
Searching & Sorting
(feat. Divide-and-Conquer)
Merge Sort and Quick Sort Lecture 3

12 Feb. 20

13 Feb. 25

Midterm Exam 1: Feb. 27, 8:15-9:45pm
14 Mar. 3

Selection


15 Mar. 5

Graph Algorithms

Data Structures for Graphs
BFS, DFS, and Topological Sort
Strongly Connected Components

Lectures 4


16 Mar. 10

17 Mar. 12

Spring Break
18 Mar. 24




19 Mar. 26
Greedy Algorithms
Interval Scheduling, Minimum Spanning Trees
Shortest Path Problems
Lecture 5

20 Mar. 31

21 Apr. 2

Midterm Exam 2: Apr. 7, 8:15-9:45pm
22 Apr. 9




23 Apr. 14
Dynamic Programming
Weighted Interval Scheduling
Segmented Least Squares, Knapsack,
Longest Common Subsequence, Edit Distance
Bellman-Ford Shortest Path Problem
Lecture 6

24 Apr. 16

25 Apr. 21

26 Apr. 23

27 Apr. 28
NP
Basics of NP-Completeness, Reduction
Lecture 7

28 Apr. 30
Final Review
Topics since Exam 2
Final Review

Final Exam: TBD

Academic Integrity

This course will follow ISU's Code of Academic Conduct. Discussions of homework assignments and final projects are encouraged. However, what you turn in must be your own. You should not directly copy solutions from others. Any reference (including online resources) used in your solution must be clearly cited.

 
Copyright © 2004- Jia (Kevin) Liu. All rights reserved.
Updated: . Design adapted from TEMPLATED.