Find our class page at: https://piazza.com/configure-classes/spring2013/411h and enroll yourself ASAP.
Lecture: Tuesdays, Thursdays 11:10 AM - 12:25 PM, CE 222
Textbook: Introduction to Algorithms, Third Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT Press, 2009
Course Webpage: http://faculty.cse.tamu.edu/nikolova/Teaching/S13/
Web Forum: http://www.piazza.com/tamu/spring2013/csce411h
Prerequisites: CSCE 221, CSCE 222, and CSCE 315 Click here for more details on required background information and resources.
week of | topic | chapter |
1/14 | introduction and review | Chs 1-3 |
1/21, 1/28 | divide and conquer algorithms | Chs 4, 30 and 33 |
2/4, 2/11 | transformations | Chs 18, 28-30 |
2/18 | dynamic programming | Chs 15 and 25 |
2/25 | amortized analysis | Chs 17 and 21 |
3/4 | greedy algorithms | Chs 16, 23 and 24 |
3/18 | maximum flow | Ch 26 |
3/25 | linear programming | Ch 29 |
4/1 | randomized algorithms | Ch 5 |
4/8 | lower bounds | Ch 8.1 |
4/15, 4/22 | NP-completeness and approximation | Chs 34 and 35 |
4/29 | undecidability | other sources |
Your grade will be based on these components:
Course grades will be assigned according to this scale:
% total points | 90-100 | 80-89 | 70-79 | 60-69 | < 60 |
letter grade | A | B | C | D | F |
Academic Integrity Statement and Policy: The Aggie Honor Code states "An Aggie does not lie, cheat or steal or tolerate those who do". More information on academic integrity, plagiarism, etc. is available at the Aggie Honor System Office web site http://aggiehonor.tamu.edu, including:
For the assignments in this class, discussion of concepts with others is encouraged, but all assignments must be done on your own, unless otherwise instructed. If you use any source other than the text, reference it/him/her, whether it be a person, a book, a solution set, a web page or whatever. You MUST write up the solutions in your own words. Copying is strictly forbidden. Every assignment must be turned in with this cover sheet, which lists all sources you used.
Americans with Disabilities Act (ADA) Policy Statement: The Americans with Disabilities Act (ADA) is a federal antidiscrimination statute that provides comprehensive civil rights protection for persons with disabilities. Among other things, this legislation requires that all students with disabilities be guaranteed a learning environment that provides for reasonable accommodation of their disabilities. If you believe you have a disability requiring an accommodation, please contact the Department of Student Life, Services for Students with Disabilities in Cain Hall, Rm. B118, or call 845-1637.
There is a lot more to Computer Science than you will be exposed to through your normal coursework. The purpose of the culture activities is to give you an opportunity to learn about current research trends in computing as they relate to algorithms. Keeping up with trends and learning to evaluate critically what you hear and read are valuable professional skills.
Each report is to be one to two pages long, typed, and is to cover some aspect of computer science and engineering that is related to algorithms. In your report, be sure to clearly explain the connection to algorithms.
The first report, which is due Thursday, Feb 14, is a biography of someone who made important contributions to the field of algorithms. One way to find an appropriate subject is to check the list of Turing award winners and choose someone whose contribution is related to algorithms. Check with Dr. Nikolova if you want to choose someone else. Provide some biographical information as well as a description of the main technical contribution of the person.
The second report, which is due Thursday, March 21, is to be about a company whose main product is based on algorithms (e.g., Akamai). Check out the helpful list here, which is for a course at CMU called "Algorithms in the Real World". Be sure to include technical explanation of the algorithm(s) on which the company's product is based.
The third report, which is due Thursday, April 25, is to be on a research seminar related to algorithms. Check the offerings in the following seminar series to find one related to algorithms:
Each report is to be one to two pages long, typed, and must include:
Tips for getting full points on your culture reports:
The culture report due dates are posted in the calendar section and summarized here:
Follow the links in the calendar to get details on the assignments and review sheets for the exams. Reading assignments refer to the textbook.
Date | Topic | Assignment(s) |
January | ||
---|---|---|
Tue, 1/15 | Introduction | Read pp 3-4 and Chs 1-3 Review background material |
Thu, 1/17 | Brute force & exhaustive search algorithms | Quiz 1 |
Tue, 1/22 | Topological sort and strongly connected components | . |
Thu, 1/24 | Divide & Conquer algorithms; GCD & Closest pair problems | Quiz 2, HW 1 due |
Tue, 1/29 | Graham's Rule for Convex Hull; Strassen's algorithm for matrix multiplication | . |
Thu, 1/31 | Polynomials and the Fast Fourier Transform (FFT) | Quiz 3 |
February | ||
Tue, 2/5 | Polynomials and FFT continued | . |
Thu, 2/7 | LUP Decomposition; B-trees (Set 4 slides) | Quiz 4, HW 2 due |
Tue, 2/12 | B-trees continued | . |
Thu, 2/14 | Linear Programming; Practice for Exam 1. Come with questions! | Quiz 5, Culture Report 1 due |
Tue, 2/19 | EXAM 1 | . |
Thu, 2/21 | Dynamic Programming | Quiz 6 |
Tue, 2/26 | Dynamic Programming: longest common subsequence, Bellman-Ford and Floyd-Warshall shortest path algorithms | . |
Thu, 2/28 | In-class presentation on Challenge Problem; Review of Exam 1 | Quiz 7, Challenge problem report 1 due, Optional due: Culture Report 3 |
March | ||
Tue, 3/5 | Amortized analysis | |
Thu, 3/7 | Disjoint sets | Quiz 8, HW 3 due Optional due: Culture Report 3 |
Mon, 3/11 - Fri, 3/15 | SPRING BREAK | SPRING BREAK |
Tue, 3/19 | no class; make-up class was on 2/22/13: Risk in routing and games | . |
Thu, 3/21 | Greedy algorithms; minimum spanning tree | |
Tue, 3/26 | Dijkstra's shortest path algorithm; Network flow | |
Thu, 3/28 | Network flow continued | Quiz 9 |
April | ||
Tue, 4/2 | EXAM 2 | . |
Thu, 4/4 | Application of network flow: Bipartite matching | Culture Report 2 due (resume) |
Tue, 4/9 | Randomized Algorithms | . |
Thu, 4/11 | Challenge Problem presentations; Randomized Algorithms continued | Quiz 10, Challenge problem report 2 due |
Tue, 4/16 | Randomized quicksort, Sorting Lower Bound, Intro to NP Completeness | . |
Thu, 4/18 | NP Completeness | Quiz 11 |
Tue, 4/23 | Approximation algorithms | . |
Thu, 4/25 | Review for exam | Quiz 12, HW 4 due |
Wed, 4/30 | [11:10-12:25 pm] Challenge Problem final presentations | Challenge Problem final report due |
May | ||
Fri, 5/3 | FINAL EXAM |