Weeks 
Topics  Resources  Suggested Readings  Special Days  Important Dates 
HAs  Projects  Exams 
#1 8/289/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 averagecase 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/49/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 InstructorApproved Late Adds via RAIL.


#3 9/119/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  topdown (recursion) and bottomup (loop) approaches.
 An example application of merge algorithm  Counting inversions.
 Readings  Chapter 1.4, 2.12.3.

Assignment 2

#4 9/189/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 #13.


#5 9/259/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. Redblack trees (optional).
 23 search trees. Search and insertion. Deletion from 23 trees.
 Exercise  Building binary search trees and 23 trees from a random list and a sorted list.
 Readings  Chapter 3.13.4.

Assignment 3

#6 10/210/6 
 Graph model and applications. Undirected and directed graphs. Unweighted and weighted graphs. Graphs and trees.
 Implementation  Adjacency matrix/lists.
 Readings  Chapter 4.14.2.

Assignment 4  Please attend talk by Reid and meeting with Technik.

#7 10/910/13 
 Breadth and depthfirst searches. Implementation of search methods using queues and stacks.
 A variation of BFS  Degrees of separation.
 Readings  Chapter 4.34.4.
Midterm Exam Week.
Friday, 10/13. Last Day to Apply for May 2018 Graduation (Registrar’s Office).

Exam 2 on Wednesday. Covers weeks #46.


#8 10/1610/20 
 Directed acyclic graphs (DAGs). Topological ordering.
 Exercise on DAG and topological ordering.
 Readings  Chapter 4.34.4.
Thursday & Friday, 10/19 & 10/20. Fall Break (or Makeup Days for Inclement Weather).


#9 10/2310/27 
 Minimum spanning trees for weighted graphs  Prim's and Kruskal's algorithms.
 Proofs of properties of MSTs  Minweighted 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).
 Biconnected component algorithm.
 Java examples on breadthfirst and depthfirst searches.
 Readings  Chapter 4.34.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.

Assignment 5

#10 10/3011/3 
 Applications of string processing algorithms. Language support for string processing  example: Java.
 String sorts. Introductory method  keyindexed counting.
 LeastSignificantDigit (LSD) first string sort for string sets with the same length.
 MostSignificantDigit (MSD) first string sort for general cases. Characterbased partition and 3way partition.
 String search. Tries  Insertion, search, deletion, and update.
 Readings  Chapter 5.15.5.


#11 11/611/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 #710.


#12 11/1311/17 
 Regular expressions (Regexes). Regex examples and exercises.
 Relationship between finite state machines and regular expressions.
 Data compression. ShannonFano algorithm. Huffman algorithm.
 Readings  Chapter 5.45.5.

Assignment 6

#13 11/2011/24 
Thanksgiving Recess.


#14 11/2712/1 
 Context of computer algorithms  scope and depth.
 Turing machine. ChurchTuring 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 NPcomplete.
 Readings  Chapter 6.

Assignment 7

#15 12/412/8 
 NPcomplete problem examples 
Circuit SAT → Fomula SAT → 3CNF SAT → Subset Sum
↳ Clique → Vertex Cover → Hamiltonian Cycle → TSP
 Proofs of NPcompleteness using reduction. Examples 
3CNF SAT → Clique. Relationship between logic problems and graph problems.
Hamiltonian Cycle → TSP.
 Coping with NPC problems 
 Solving special cases or instances.
 Applying heuristics or additional knowledge about specific instances.
 Using approximation methods. Suboptimal vertex cover.
 Using numerical simulations that involve randomness in the search process.
 ...
 Final exam review.
 Readings  Chapter 6.
Friday, 12/8. Last Day of Classes. Last Day for Complete Withdrawal from Semester.


#16 12/1112/15 
Final Exam Week.

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