CSCI-2300: Algorithms
Fall 2011        

Announcements.

Final Exam is on Dec. 20th (Tuesday) 3-6:00 pm in DCC 308

Jeff Gaston (UPE member) will be holding office hours and help sessions on Wednesdays from 12:30 -2:30 pm in AE 117. Jason Rock and Benno (UPE members) will be holding office hours on Friday 1-3:00 ppm in AE 117.

There will be 10 questions 3 or 4 in the last part 3 or 2 in the second and 2 or 3 in the first part.

Topics for Third Test NP-complete, Approximation Algorithm, Linear Programming, Network Flow, Graphs BFS, Path, Dynamic Programming, Huffman, Greedy, Euclidean and Extended Euclidean, Algorithms Analysis (genral), construction of examples, Divide and Conquer, Recurrence Equations.
  1. Home work 9 solution is posted
  2. Sample exam 3 is posted in rpilms site
  3. HW 10 Due (12/5/2011)
  4. Lab 10 is posted.(November 30th)

  5. Extra Office hours on Saturday 1:30-3:30 pm in Union 3602

  6. Sample Exam 2 is posted in rpilms website. Exam 2 covers Chapters 4, 5 6 and Sections 3.3 and 3.4 of Das Gupta Et al's book.
  7. HW 9 Due (11/21/2011)
  8. Lab 9 is posted.
  9. HW 8 Due (11/3/2011)
  10. Lab 8 is posted.
  11. HW 7 Due (10/27/2011)
  12. Lab 7 is posted.
  13. HW 6 Due (10/20/2011)
  14. Lab 6 is posted.
  15. HW 5 Due (10/13/2011)
  16. Lab 5 is posted.
  17. Sample Solution to Test 1 is posted in rpilms.
  18. Test 1 is on Monday (Oct 3) - Open Book, Open Notes and Calculator allowed test (No internet) in DCC 318 from Noon to 1:30 pm
  19. Extra office hours on Saturday from 1:30 pm to 4:00 pm in Mothers at the Union (1:30-3:00 pm Maxim (GTA), 2:30-4:00 pm Moorthy)
  20. Home work solutions (1-4) are in rpilms.
  21. HW 4 Due (9/29/2011)
  22. Lab 4 is posted.
  23. Sample Exam 1 is posted in rpilms. (covers chapters 0,1,2,3)
  24. Solutions to First Three Labs and First Two Home Works are posted in rpilms site
  25. Please send an email to upe-tutors-l@lists.rpi.edu if you need help with Intro to Algorithms,
  26. HW 3 Due (9/22/2011)
  27. Lab 3 is posted.
  28. HW 2 Due (9/15/2011)
  29. Lab 2 is posted.
  30. HW 1 Due (9/8/2011)
  31. Lab 1 is posted.
  32. No Lab this Wednesday (8/31) - I know many/all of you are eager to start thinking about algorithms and working on it - So for this week (for the lab) you can read this blog All The Names: Algorithmic Design and the 9/11 Memorial

Lectures  

Labs    
Homework

Exams

Your Grade

 

Course Information

Instructor:         Moorthy

Email:               moorthy@cs.rpi.edu
Office Hours:    Tuesday, Friday 2:00 -3:30pm

Office:              Lally 305

Teaching Asst:Minjun Yang 
Email:   yangm6@@rpi.edu
Office Hours: Thursday 8:00 - 10:00 am.
Location:   AE 217     

Teaching Asst: Simon Ellis
Email:               elliss5@rpi.edu

Office Hours: Tuesday 9-10, friday 12-1 AE 219 (Amos Eaton)
Location:          AE 217

Teaching Asst:  Jeremy White
Email:         whitej12@rpi.edu

Office Hours: Monday 8-10:00 am  
Location:          AE 217

Teaching Asst:Maksim Tsikhanovich
Email:   tsikhm@@rpi.edu
Office Hours: Wednesday 8-10:00 pm
Location:   AE 217     

Undergraduate Lab TAs:

  1. Brian Stauffer, Dan Ibanez --Section 1 (Amos Eaton 216) W 6-7:50 pm Jeremy White (GTA)
  2. Parker Sikand --Section 2 (Amos Eaton 216) W 2-3:50 pm Maksim Tsikhanovich (GTA)
  3. Brian Stauffer, Ryan Gerstein --Section 4 (Sage 2715)W Noon -1:50 pm Simon Ellis (GTA)
  4. Parker Sikand, Dan Ibanez -- Section 5 (Sage 2715)W 10-11:50 am Minjun Yang (GTA)
  5. Peter Hajas --Section 6 (Eaton 216) W Noon-1:50 pm Maksim Tsikhanovich(GTA) or MingJung Yang(GTA) - They alternate
  6. Peter Hajas, Ryan Gerstein-- Section 7 W (Sage 2715) 2-3:50 pm Jeremy White(GTA) or Simon Ellis (GTA) - They alternate,

Course Objectives

Students at the end of the course will be able to design, implement and analyze algorithms for problems in Science and Engineering. Students will learn different Algorithmic Paradigms and learn techniques for analyzing the algorithms. Students will also learn efficiency both in design and implementation. Students will learn to compare different algorithms for solving the same problem. Students will be exposed to an elementary treatment of NP-complete problems.

Learning Outcome

The goal of this course is to provide a strong foundation in algorithms and data structures in preparation for jobs in industry or for more advanced courses. Algorithms are the basic language of computer science. After taking this course, you, the student, should be able to:
  1. Understand the correctness of, and analyze the running times of, different algorithms.
  2. Use different algorithm-design techniques, including, but not limited to, greedy, divide-and-conquer, and dynamic programming techniques, to solve particular problems.
  3. Model real problems abstractly using the language of graphs and flows.
  4. Solve problems by reducing to other problems whose solution is known, and show that problems are hard by reducing from other problems.
  5. Make intelligent decisions about alternative data structures and algorithmic techniques in the context of practical software problems, choosing from existing data structures and algorithms or designing your own when necessary

Class Time:       Monday and Thursday, 12:00 - 1:20pm
Classroom:       DCC 318
Credits:            4
Prerequisites:    CS2 (CSCI-1200) and Discrete Structures (MATH-2800).

Description

This course discusses algorithms, and the mathematical techniques necessary to design and analyze them.

Web Page: http://www.cs.rpi.edu/~moorthy/Courses/CSCI2300

 

Syllabus

            Chapter 0         Introduction

            Chapter 1         Algorithm with Numbers and Randomized Algorithms

            Chapter 2         Divide and, Conquer Algorithms

            Chapter 3         Decomposition of Graphs

            Chapter 4         Paths in Graphs

            Chapter 5         Greey Algorithms

            Chapter 6         Dynamic Programming

Chapter 8         NP-complete Problems

Chapters 8         Coping with NP-complete Problema

Chapter 7       Linear Programming

 

 

Lectures

            Class 1 (8/29):           Chapter 0                                            

Class 2 (9/1):           Chapter 0 and 1                                            

Class 3 (9/8):           Chapter 1                                                                                

Class 4 (9/12):           Chapter 1                                

Class 5 (9/15):           Chapter 2                                                                               

Class 6 (9/19):            Chapter 2 and 3                                                                     

Class 7 (9/22):            Chapter 3                                                                    

Class 8 (9/26):            Chapter 3 and 4                                            

Class 9 (9/29):          Chapter 4                                                                    

Class 10 (10/3):        Exam 1                                    

Class 11 (10/6):        Chapter 4                                                                    

Class 12 (10/11):         Chapter 5                                                        

Class 13 (10/13):       Chapter 5                                                        

Class 14 (10/17):       Chapter 6                                                        

Class 15 (10/20):       Chapter 6                                                        

Class 16 (10/24):       Chapter 6                                                        

Class 17 (10/27):       Chapter 6 and 8                                            

Class 18 (10/31):       Chapter 8                                                        

Class 19 (11/3):          Chapter 8 and Review                                                                    

Class 20 (11/7):          Exam 2                                    

Class 21 (11/10):        Chapter 8                     .       

Class 22 (11/14):        Chapter 8                     .       

Class 23 (11/17):        Chapter 9                                                                    

Class 23 (11/21):        Chapter 9                                                        

Class 24 (11/28):        Chapter 9                                

Class 25 (12/1):        Chapter 7                                            

Class 26 (12/5):        Chapter 7                                                      

Class 27 (12/8):        Review                                                       

Labs

      6pm - 7:50pm     Sec 1      Eaton 216          

      2pm - 3:50pm       Sec 2      Eaton 216          

      Noon - 1:50pm       Sec 4      Sage 2715      

      10 am - 11:50am       Sec 5      Sage 2715      

      Noon - 1:50pm       Sec 6      Eaton 216       

      2:00 pm - 3:50pm       Sec 7      Sage 2715       

  1. 8/31 - No Lab - You dont have to go to Lab on August 31st
  2. Lab 1 Lab 1 is posted(Sep 7)
  3. Lab 2 (Sep 14) Lab 2 is posted(Sep 15)
  4. Lab 3 (Sep 21) Lab 3 is posted(Sep 21)
  5. Lab 4 (Sep 28) Lab 4 is posted(Sep 28)
  6. Lab 5 (Oct 12) Lab 5 is posted (Oct 12)
  7. Lab 6 (Oct 19) Lab 6 is posted (Oct 19)
  8. Lab 7 (Oct 26) Lab 7 is posted (Oct 26)
  9. Lab 8 (Nov 2) Lab 8 is posted (Nov 2)
  10. Lab 9 (Nov 16)
  11. Lab 9 is posted for Lab on Wednesday.
  12. Lab 10 (Nov 30) Lab 10 is posted for Lab on Wednesday.

Integrity

Collaboration is not allowed. Homeworks and exams should be solved and written by individuals alone. If anyone is caught cheating then severe measures will be taken such as lowering the final grade, and the event will be reported to the appropriate authorities in the campus.

 

Homework No Late Submissions (unless there is a medical Excuse)

 

Exams (in class exams )

Your Grade

 

Required Text

 

Moorthy
Department of Computer Science
Rensselaer Polytechnic Institute
110 8th Street
Troy, NY 12180