• 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.

• 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.

• 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.

• 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.

• 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.

• 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.

• 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.

• Directed acyclic graphs (DAGs). Topological ordering.
• Exercise on DAG and topological ordering.
• Readings - Chapter 4.3-4.4.

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

• 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.
• Shortest path trees for weighted digraphs - Dijkstra's algorithm.
• Difference between Minimum Spanning Trees (MSTs) and Shortest Path Trees (SPTs).
• Bi-connected component algorithm.
• Java examples on breadth-first and depth-first searches.
• Readings - Chapter 4.3-4.4.

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.

• Applications of string processing algorithms. Language support for string processing - example: Java.
• String sorts. Introductory method - key-indexed counting.
• Least-Significant-Digit (LSD) first string sort for string sets with the same length.
• Most-Significant-Digit (MSD) first string sort for general cases. Character-based partition and 3-way partition.
• String search. Tries - Insertion, search, deletion, and update.
• Readings - Chapter 5.1-5.5.

• Substring search. Finite state machines.
• FSM examples. Java/C++/C# multiple-line comments.
• Implementation of finite state machines. Sample programs - Odd As & even Bs. Multiple-line comments syntax checker.
• Readings - Chapter 5.4.

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.

• Regular expressions (Regexes). Regex examples and exercises.
• Relationship between finite state machines and regular expressions.
• Data compression. Shannon-Fano algorithm. Huffman algorithm.
• Readings - Chapter 5.4-5.5.

Thanksgiving Recess.

• Context of computer algorithms - scope and depth.
• Turing machine. Church-Turing thesis.
• Theory of intractability. Polynomial and exponential etc. running times. Practical border for "hard problems".
• The concept of reduction and its application - Solving problems or proving problems are "hard".
• Reduction examples - Ranking problem to sorting problem, independent set problem and vertex cover problem to each other, etc.
• Classes P, NP, and NP-complete.
• Readings - Chapter 6.

• NP-complete problem examples -
      Circuit SAT → Fomula SAT → 3-CNF SAT → Subset Sum
                                                                ↳ Clique → Vertex Cover → Hamiltonian Cycle → TSP
• Proofs of NP-completeness using reduction. Examples -
        3-CNF SAT → Clique. Relationship between logic problems and graph problems.
       Hamiltonian Cycle → TSP.
• Coping with NPC problems -
1. Solving special cases or instances.
2. Applying heuristics or additional knowledge about specific instances.
3. Using approximation methods. Sub-optimal vertex cover.
4. Using numerical simulations that involve randomness in the search process.
5. ...
• Final exam review.
• Readings - Chapter 6.

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

Final Exam Week.

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