Dr



Dr. Christos Nikolopoulos

Office: BR 197

(309) 677-2456

chris@bradley.edu

class web site at : and on Sakai

Office hours: T and TH 11:45-12:30 and by appointment

CS 514 FALL Term

Algorithms

Textbook:

Neapolitan R., Naimipour K., Foundations of Algorithms, Jones and Bartlett Publishers, 4th edition, 2009.

Additional References:

The video lectures from the web:

Video set 1: MIT’s algorithm lectures



and with comments



Video set 2: from IIT Bombay:



Video set 3: Yale lectures on Game Theory



Description:

Design and analysis of algorithms, classes of algorithms (divide and conquer etc.), dynamic structures maintenance and hashing, searching, sorting, and traversal, time and space requirements, computational complexity, proof theory and testing, NP-hard and NP-complete problems. Prerequisites: CS 210 or CIS 210 or equivalent; one semester of statistics.

Time Schedule:

The homework and the project paper are due back by email on December 6th by 11:00 p.m. The choice of topic for the project paper will be on algorithmic topics not covered in class (for example Steiner Trees, evolutionary algorithms etc.) and will be assigned to you on 10/18.

The table below gives the reading assignments from the books and online sources. The dates are tentative and may be adjusted.

# Date Topics for online discussion Readings/Assignments

|8/25/2011 |Overview of what we are going to cover. Appendix A review of | |

| |math concepts | |

|8/30/2011 |Chapter 1 Algorithms, Efficiency, Analysis, and Order: 1.1 |From your book and lectures, videos. |

| |Algorithms, 1.2 The Importance of Developing Efficient | |

| |Algorithms, 1.3 Analysis of Algorithms, 1.4 Order . | |

|9/6/2011 |Chapter 2 Divide-and-Conquer: |From your book and lectures, videos. |

| |2.1 Binary Search, 2.2 Mergesort, 2.3 The Divide-and-Conquer | |

| |Approach, 2.4 Quicksort, 2.8 When Not to Use Divide-and-Conquer| |

|9/13/2011 |Chapter 3 Dynamic Programming: 3.1 The Binomial Coefficient, |From your book and lectures, videos. |

| |3.2 Floyd's Algorithm, 3.3 Dynamic Programming and Optimization| |

| |Problems, 3.5 Optimal Binary Search Trees, 3.6 The Traveling | |

| |Salesperson Problem, 3.7 Sequence Alignment. | |

|9/20/2011 |Chapter 4 The Greedy Approach: 4.1 Minimum Spanning Trees, 4.2 |From your book and lectures, videos. |

| |Dijkstra's Algorithm for Single-Source Shortest Paths | |

|9/27/2011 |Chapter 4 The Greedy Approach: 4.3 Scheduling, 4.4 Huffman |From your book and lectures, videos. |

| |Code, 4.5 The Greedy Approach Versus Dynamic Programming: The | |

| |Knapsack Problem. | |

|10/4/2011 |Chapter 5 Backtracking: 5.1 The Backtracking Technique, 5.2 The|From your book and lectures, videos. |

| |n-Queens Problem, 5.3 Using a Monte Carlo Algorithm to Estimate| |

| |the Efficiency of a Backtracking Algorithm, 5.4 The | |

| |Sum-of-Subsets Problem, 5.5 Graph Coloring, 5.6 The Hamiltonian| |

| |Circuits Problem, 5.7 The 0-1 Knapsack Problem. | |

|10/11/2011 |NO CLASS-Bradley on Fall Recess | |

|10/13/2011 |MIDTERM EXAM |From your book and lectures, videos. |

| | | |

|10/18/2011 |Discuss exam/answers |Assignment of topic for your research paper. |

|10/25/2011 |Chapter 6 Branch-and-Bound: 6.1 Illustrating Branch-and-Bound |From your book and lectures, videos. |

| |with the 0-1 Knapsack Problem, 6.2 The Traveling Salesperson | |

| |Problem, 6.3 Abductive Inference (Diagnosis). | |

|11/1/2011 |Chapter 7 Introduction to Computational Complexity, The Sorting|From your book and lectures, videos. |

| |Problem: 7.1 Computational Complexity, 7.2 Insertion Sort and | |

| |Selection Sort, 7.3 Lower Bounds for Algorithms that Remove at | |

| |Most One Inversion per Comparison, 7.4 Mergesort Revisited, 7.5| |

| |Quicksort Revisited. | |

|11/8/2011 |Chapter 7 Introduction to Computational Complexity, The Sorting|(Ch. 7 continued) |

| |Problem: 7.6 Heapsort, 7.7 Comparison of Mergesort, Quicksort, | |

| |and Heapsort, 7.8 Lower Bounds for Sorting Only by Comparison | |

| |of Keys, 7.8.1 Decision Trees for Sorting Algorithms, 7.8.2 | |

| |Lower Bounds for Worst-Case Behavior, 7.8.3 Lower Bounds for | |

| |Average-Case Behavior, 7.9 Radix Sort | |

|11/15/2011 |Chapter 8 More Computational Complexity: The Searching Problem:|From your book and lectures, videos. |

| |8.1 Lower Bounds for Searching Only by Comparisons of Keys, 8.2| |

| |Interpolation Search, 8.3 Searching in Trees, 8.3.1 Binary | |

| |Search Trees, 8.3.2 B-Trees, 8.4 Hashing, 8.5 The Selection | |

| |Problem: Introduction to Adversary Arguments. | |

|11/22/2011 |Chapter 9 Computational Complexity and intractability: An |From your book and lectures, videos. |

| |Introduction to the Theory of NP: 9.1 Intractability, 9.2 Input| |

| |Size Revisited, 9.3 The Three General Problems, 9.4 The Theory | |

| |of NP, 9.4.3 NP-Hard, NP-Easy, and NP-Equivalent Problems, 9.5 | |

| |Handling NP-Hard Problems. | |

|11/29/2011 |Chapter 10 Number-Theoretic Algorithms: 10.1 Number Theory |From your book and lectures, videos. |

| |Review, 10.1.1 Composite and Prime Numbers, 10.1.2 Greatest | |

| |Common Divisor, 10.1.3 Prime Factorization, 10.1.4 Least Common| |

| |Multiple, 10.2 Computing the Greatest Common Divisor, 10.3 | |

| |Modular Arithmetic Review, 10.4 Solving Modular Linear | |

| |Equations, 10.5 Computing Modular Powers, 10.6 Finding Large | |

| |Prime Numbers, 10.7 The RSA Public-Key Cryptosystem | |

|12/6/2011 |Review, Homework Due, Project paper due. |By email to chris@bradley.edu by 11:00 p.m. |

|12/8/2011 |FINAL EXAM 5:00-7:00 p.m. |Comprehensive exam, with around 70% from |

| | |material after the midterm. |

Assessment

200 Points Total

80 points Midterm Exam

20 points homework assignments

20 points on project paper

80 points Final Exam

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download