Dr. Zhijun Wang, Professor of Computer Science
♦   Welcome to CIS 431 — Algorithms   ♦
Weeks Topics | Resources | Suggested Readings | Special Days | Important Dates HAs | Projects | Exams
#1
8/28-9/1
  • Introduction and syllabus. Course website. Class policies and guidelines.
  • Textbook website - Some very helpful computer science resources.
  • Optional - Java programming exercises and libraries provided by the textbook.
  • Data structures and algorithms.
  • Basic data structures review - stack, queue, and their implementation methods.

  • "Scientific method" and procedure for the analysis of algorithms.
  • Running time of algorithms. Logical time units.
  • Time and space efficiency. Examples - Insertion sort and merge sort.
  • Best-, worst-, and average-case running times.
  • Asymptotic notations review - Big O, big Ω, and big Θ.
  • Readings - Chapter 1.1 - 1.4 or a data structure reference.

Monday, 8/28. Add/Drop and Late Registration via RAIL or at Ikenberry Hall.

Friday, 9/1. Last Day to Add/Drop or Late Register via RAIL or at Ikenberry Hall.

Assignment 1

#2
9/4-9/8
  • Common running times - from constant to factorial.
  • Problem and algorithm examples.
  • Polynomial running times. Definition of efficient algorithms.
  • Readings - Chapter 1.4.

Monday, 9/4. Labor Day — Holiday.

Friday, 9/8. Last Day for Instructor-Approved Late Adds via RAIL.

#3
9/11-9/15
  • Quadratic time sorting algorithms review - Bubble, insertion, and selection sorts.
  • Binary heap and heap sort - quick review.
  • Merge sort. Recursive definition.
  • Exercise on merge sort - count number of comparisons.
  • Implementations of merge sort - top-down (recursion) and bottom-up (loop) approaches.
  • An example application of merge algorithm - Counting inversions.
  • Readings - Chapter 1.4, 2.1-2.3.
Assignment 2

#4
9/18-9/22
  • Quick sort. Sample implementation of quick sort. Java sorting method.
  • Exercises on sorting algorithms - tracing the sorting process and counting the number of comparisons.
  • Divide and conquer techniques. Master's theorem. Examples and exercises.
  • Readings - Chapter 2.4.

Exam 1 on Wednesday. Covers weeks #1-3.

#5
9/25-9/29
  • Importance of search. Search methods with different efficiencies.
  • Search model. Symbol tables/dictionaries/indexes.
  • Sequential search, performance, and implementation.
  • Review of hash table search.
  • Binary search and performance. Sorted list implementation of binary search.
  • Binary search trees - linked structure implementation of binary search.
  • Search, insertion, and deletion in a binary search tree.
  • Exercise - Writing a program to study linear, binary, and hash table search times. Example.
  • The need for balanced search trees. Red-black trees (optional).
  • 2-3 search trees. Search and insertion. Deletion from 2-3 trees.
  • Exercise - Building binary search trees and 2-3 trees from a random list and a sorted list.
  • Readings - Chapter 3.1-3.4.
Assignment 3

#6
10/2-10/6
  • Graph model and applications. Undirected and directed graphs. Unweighted and weighted graphs. Graphs and trees.
  • Implementation - Adjacency matrix/lists.
  • Readings - Chapter 4.1-4.2.
Assignment 4 - Please attend talk by Reid and meeting with Technik.
#7
10/9-10/13
  • Breadth- and depth-first searches. Implementation of search methods using queues and stacks.
  • A variation of BFS - Degrees of separation.
  • Readings - Chapter 4.3-4.4.

Mid-term Exam Week.

Friday, 10/13. Last Day to Apply for May 2018 Graduation (Registrar’s Office).

Exam 2 on Wednesday. Covers weeks #4-6.

#8
10/16-10/20
  • Directed acyclic graphs (DAGs). Topological ordering.
  • Exercise on DAG and topological ordering.
  • Minimum spanning trees for weighted graphs - Prim's and Kruskal's algorithms.
  • Proofs of properties of MSTs - Min-weighted edge. Uniqueness of MST.
  • Summary of greedy algorithms.
  • Readings - Chapter 4.3-4.4.

Thursday & Friday, 10/19 & 10/20. Fall Break (or Make-up Days for Inclement Weather).

#9
10/23-10/27

Wednesday, 10/25. First Day of Academic Advisement for Continuing Students for Spring 2018.

Friday, 10/27. Last Day to Withdraw from a Full Semester Class — See Advisor by Noon.

#10
10/30-11/3
#11
11/6-11/10

Monday, 11/6. First Day of Spring 2018 RAIL Registration for Continuing Students.

Wednesday, 11/8. Last Day of Academic Advisement for Continuing Students for Spring 2018.

Exam 3 on Wednesday. Covers weeks #7-10.

#12
11/13-11/17
#13
11/20-11/24

Thanksgiving Recess.

#14
11/27-12/1
#15
12/4-12/8

Friday, 12/8. Last Day of Classes. Last Day for Complete Withdrawal from Semester.

#16
12/11-12/15

Final Exam Week.

Final Exam -
12 – 2 pm,
12/13, Wednesday.