## 92054 CSC 3171A - 0 - Algorithms## Fall 2011 |

This web page is http://www.bernstein-plus-sons.com/.dowling/CSC3171F11/CSC3171_Syllabus.html

Copyright © 2007, 2011 Herbert J. Bernstein and other parties. All rights reserved.

This is the syllabus for CSC 3171A for Fall 2011. As the course moves forward, students should return to this page frequently for updated material. This is a hybrid course. Certain sessions are held on-site at Dowling College's Brookhaven Campus. The remaining sessions are on-line sessions.

3 credits

Algorithmic development is a key ingredient to the development of computer-based solutions for a wide variety of scientific and industrial problems. This course provides students with an opportunity to further develop their skills in developing and documenting methodologies for the solution of various problem classes. Topics include the writing of understandable pseudocode, techniques for estimating the efficiency of an algorithm, the use of advanced data structures, and the implementation of these techniques using a programming language like Java or C++. Example problems may be drawn from a variety of areas in discrete and continuous mathematics.

**Prerequisites:** MTH 1017A and CSC 2025A, or permission of the Mathematics and Computer Science
Department chair.

This Fall 2011 section is:

Algorithms - 92054 - CSC 3171A - 0 |
---|

Associated Term: Fall 2011
Registration Dates: Apr 11, 2011 to Dec 17, 2011 Levels: Undergraduate Attributes: Liberal Arts Instructors: Herbert J. Bernstein (P) Brookhaven Campus Lecture Schedule Type Blended Instructional Method 3.000 Credits View Catalog Entry |

- Name: Prof. Herbert J. Bernstein
- Office: Brookhaven Campus B111B, Lab: Brookhaven Campus B205
- Phone: +1-631-244-1328 (Office) +1-631-244-1935 (Lab)
- Skype Name: yayahjb
- Email:

- by appointment:
- Monday, 1:00 pm - 3:00 pm in B205 on the Brookhaven campus;
- Tuesday, 1:00 pm - 1:30 pm, in B205 on the Brookhaven campus;
- Thursday, 1:00 pm - 2:30 pm in B205 on the Brookhaven campus;

Students have the option of meeting with the instructor either on-site or via Skype. In order to avoid conflicts with other students and other obligations of the instructor, if possible please make an appointment via email.

Note that, in general, Dr. Bernstein will be at the Brookhaven campus on Monday, Tuesday and Thursday afternoons and on the Oakdale campus on Wednesday afternoons. Meetings on the Oakdale campus will be in KSC 103. Meetings at the Oakdale campus are by appointment only.

For more information see http://www.bernstein-plus-sons.com/.dowling/HJB_Contact_Info.html.

- Donald Knuth, "The Art of Computer Programming" V1-4, 3rd ed., Boxed
set, Pearson, 2011, ISBN 9780321751041.
- Kyle Loudon, "Mastering Algorithms with C", Ingram, 1999, ISBN 9781565924536.

Keeping clear written records is an important part of working in any scientific field. It is particularly important in Computer Science, where there are very complex, non-obvious decisions to make. In addition, 60% of your grade for this course will be in the final for which you will need a dense 2-page set of notes. A good notebook will help you to prepare those notes.

**Students are expected to have their text books no later than the
second week of class.** Students can start learning some of the material
for the course immediately by going to the MIT OpenCourseWare site
and reviewing the video lectures at
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/
While we will not be using the same text book the material presented should
be very helpful to you in understanding Knuth.

Attendance will be taken at all on-site class meetings, and regular participation in the on-line exercises is required. We are trying to arrange permission for students who wish to, to participate in the on-site sessions via Skype. We will discuss that option further at the first on-site class session. Be certain to attend that one in person.

- Quizzes: 20%
- Assignments: 20%
- Comprehensive Final: 60%

Your objective in this course is to display a firm grasp of everything that is in Knuth. The final examination will be a closed book comprehesive examination that may draw on anything and everything in Knuth. The only grades that will be given will be A, B or I, and the only way to clear an incomplete is to take an even tougher closed book make-up examination that demonstrates a thorough understanding of everything in Knuth.

Students will be given weekly quizzes and assignments to help ensure regular attention to the material of the course. On-site sessions will consist of both lecture-style reviews of materials and presentation and discussions by the students in which all students are expected to display an understanding of the material they have been working on.

In addition to routine reading assignments, students will have two kinds of special assignments: ones that will help them to explore algorithms in practice and ones that will help them to study a syllabus topic in depth. Students have one week from the start of the semester to propose a significant topic within which they will to explore appropriate algorithms. If no proposals are made, the instructor will make assignments involving the following threads: molecular graphics, nearest neighbor problems, numerical linear algebra.

The study assignments will be handled by each student presenting a web page lecture on that topic for the instructor and other class members to review presenting that topic to the class during an on-site session with discussions both in-class and on-line on the algorithm issues in that topic resulting in revisions to the web page. The resulting web page will become a part of the publicly available on-line materials of the course.

You will have to do such assignments multiple times.

Every student will be required to maintain a contemporaneous hardbound notebook recording all significant activities related to this course.

The work load for this course is very heavy. Students are encouraged to form study groups and to work together.

**In general,
no assignments will be accepted late and no makeups will be given for
missed quizzes or examinations.** Requests for exceptions to this policy
will be considered only for the most pressing reasons (illness requiring
hospitalization, death in the family, reserve call-up, etc.), must be
submitted in writing in a timely manner, and will be granted only if the
instructor has sound reason to believe that the student is highly likely
to master the material of the course within the current semester.

The syllabus and the course objectives that follows are derived in part from the IEEE/ACM "Computing Curricula 2001 Computer Science" - Final Report - (December 15, 2001) by the Joint Task Force on Computing Curricula, Publisher:IEEE Computer Society, Association for Computing Machinery.

- Administrative matters.
- Overview of the course.
- Review
- Introduction to Professional Issues: Ethical issues; fiduciary responsibility; Murphy's Law; KISS.
- Solving problems with computers.
- Review of programming.
- Data types, algorithms and objects.
- Performance issues -- space and time.
- Big "Oh", little "Oh".
- Primitive data types.
- References, pointers, arrays, structures and unions.
- Classes and inheritance
- Stacks, heaps, queues, lists, trees, hash tables and graphs. (See http://www.wikipedia.org/wiki/Data_structure).
- Searching and sorting
- Random Numbers
- Lists
- Trees and Graphs
- Donald Knuth's Computer Musings

- Wikipedia article on the Art of Computer Programming
- Fundamental Algorithms (Knuth Volume I)
- Algorithms
- Mathematical Preliminaries
- Mathematical Induction

see Wikipedia article on Mathematical Induction - Numbers, Powers, Logarithms
- Sums and Products
- Integer Functions and Elementary Number Theory
- Permutations and Factorials

see Wikipedia article on Permuatations - Binomial Coefficients

see Wikipedia article on Binomial Coefficients - Harmonic Numbers

see Wikipedia article on Harmonic Numbers - Fibonacci Numbers

see Wikipedia article on Fibonacci Numbers - Generating Functions

see Wikipedia article on Generating Functions - Analysis of an Algorithm see Wikipedia article on Analysis of Algorithms
- Asymptotic Representations

see Wikipedia article on Asymptotic Analysis

- Mathematical Induction
- MIX
- GNU mdk MIX and MIXAL-tutorial
- Fundamental Programming Techniques
- Subroutines

see Wikipedia article on Subroutines - Coroutines

see Wikipedia article on Coroutines - Interpretive Routines

see Wikipedia article on Interpreters, Wikipedia article on Threaded code, Wikipedia article on Virtual machines - Input and Output

- Subroutines
- Information Structures
- Linear Lists
- Circular Lists
- Doubly Linked Lists
- Arrays and Orthogonal Lists
- Trees
- Multilinked Structures
- Dynamic Storage Allcation

- Seminumerical Algorithms (Knuth Volume II)
- Sorting and Searching (Knuth Volume III)
- Sorting
- Searching

- To understand the development of algorithms used to solve problems with computers
- To understand the analysis of algorithms.
- To better understand the professional responsibilties of a programmer and the limitations of hardware and software.
- To sharpen programming skills in a problem-solving environment.
- To understand the interaction between data structures and algorithmic performance.

Please consult the course assigments page frequently.

Using VNC via SSH: vnc.html

If you're interested in joining with your fellow students in developing and maintaining a web site, or pursuing your exploration of computer hardware or software, you might want to consider joining the Dowling Computer Club. Just follow the link for further details:

Dowling College Computer Club Web Site

Updated 6 October 2011.