CSCE 411H: Design and Analysis of Algorithms: Honors
Spring 2013


[Announcements] [Syllabus] [Homework] [Culture] [Calendar]


Announcements

Back to beginning


Syllabus

Instructor: Prof. Evdokia Nikolova
Office: HRBB 515A
Office Hours: Tuesdays and Thursdays after class; Tuesdays 3-5 PM; available other times by appointment
Email: nikolova (at) tamu.edu

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.


Course Goals: At the end of the semester, you should: Course Content and Tentative Schedule: The course will cover the following topics. The relevant chapters of the textbook are indicated.

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


Assignments and Grading: All assignments will be announced in class and posted on the course web page calendar. No late assignments will be accepted. However, to accommodate for emergencies during the semester, you are allowed to not turn in one assignment, at no penalty. You do not need to ask for special permission to do so.

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:

Please review this material.

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.

Back to beginning


Culture Reports

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:

Other seminar series might also have an appropriate offering; check with Dr. Nikolova. (If you have a legitimate scheduling conflict with all possible seminars, please see Dr. Nikolova for an alternative assignment.)

Each report is to be one to two pages long, typed, and must include:

  1. Cover sheet
  2. Bibliography of all your sources. For the seminar report, include the title, name of speaker, and date.
  3. For the seminar report, summary of the seminar
  4. For the seminar report, how the contents of the seminar relate to our class (algorithms)
  5. For the seminar report, include your critique: at least one comment about the presentation or question that it raised in your mind, indicating that you have thought critically about the material presented.
DO NOT PLAGIARIZE! You must write up your summary in your own words. See academic integrity policy in the syllabus.

Tips for getting full points on your culture reports:

The culture report due dates are posted in the calendar section and summarized here:

Back to beginning


Calendar

This calendar lists all due dates as they become known for Powerpoint lecture slides and other materials will be posted as they become available:

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

Back to beginning