Course Syllabus
COSC5313 (Analysis of Algorithms)Spring 2014 Instructor: Dr. Hikyoo Koh, Professor of CS Office: MA68 Phone: 880-8779 (Cell Phone: 8082554901, you can call any time, day and night) E-mail: hkoh@lamar.edu (or HKPK32@Yahoo.Com) Web: galaxy.cs.lamar.edu/~hkoh Office hours: MW: 14:40-15:40 Thurs: 14:30-16:30 Sat: 11:00-14:00 (About every other Saturday, with appointments preferred) Others: By appointments via Email or by phones Catalog Course description: Topics on what can and cannot be proven about computational complexity including algorithm design methodologies. Prerequisite: COSC2336 or equivalent.
Required textbook: Algorithms, Fourth Edition, by Robert Sedgewick and Kevin Wayne, Addison Wesley, 2011. Other useful resources: 1. Fundamentals of Algorithmics, by Gilles Brassard and Paul Bratley, Prentice Hall, 1996.
2. Algorithms, by Richard Johnsonbaugh and Marcus Schaefer, Prentice Hall, 2004.
3. Discrete Optimization Algorithms, by M.M. Syslo, at el, Prentice Hall.4. Applied Combinatorics, by Fred Roberts, Prentice Hall.5. Algorithms + Data Structures = Programs, Niklaus Wirth, Prentice Hall.6. Hawaii International Conference on Computer Science, Honolulu, Hawaii, 20047. Southeast Regional Conference of the ACM, Mobile, Alabama, 1999. Learning Outcomes: By completing this course, students will be able to:1. fully understand algorithm efficiency measures and analysis techniques,
2. fully understand some advanced algorithm design methodologies including
Linear Programming, Greedy Algorithms, Dynamic Programming, Backtracking/Recursions and Probabilistic Algorithms.3. fully understand Non-deterministic Algorithms and NP-Completeness, and
4. be proficient in designing and coding some programming problems closely related to above
mentioned algorithm design methodologies. Topics to cover: 1. Review: Efficiency of Algorithms. Asymptotic notations. Recurrence solution. 2. Linear Programming: Simplex Method, Standard form, Basic solution, Feasible solution, Optimal solution, Duality. 3. Counting and Generating Functions: Occupancy Problems and Generating Functions. Principle of Inclusions and Exclusions. Chromatic Polynomials Test-1 4. Greedy Algorithms. 5. Dynamic Programming and Backtracking.6. Probabilistic Algorithms7. Some Graph Algorithms. Depth-First Search and Breadth-First Search Branch-and-Bound. Minimax Maximum Flow/Minimum LoadTest-2 8. Random number generation. 9. NP-Completeness. Grading methods: All exams will be OPEN for you to be able to open and use, during the exam, anything you bring the exam including anything prepared for the exam, books, notes, a laptop, among others. 2 tests (OPEN): 200 points (100 points each) Final Exam (OPEN): 200 points 5 or more programs: 100 points {Programming assignments include:
} Occasional Quizzes: 50 points -------------------------------------------------------------------- TOTAL MAX: 550 points If your class average is: 85% or higher: A Else 75% or higher: B Else 65% or higher: C Else: D Online Course Evaluations. Lamar University encourages students to evaluate online the courses they take and the instruction they receive via a contract with a national company, OnlineCourseEvaluations.com. The evaluation instruments themselves were developed by LU faculty and administrators. Evaluation windows for fall and spring courses open two weeks before the final examination period and close at the end of the last class day. The student is notified of the specific dates at his/her myLAMAR e-mail address. If course evaluations are given during summers, mini semesters, and other compressed terms, evaluation windows are extended past the last class meeting. Evaluations are completely anonymous, and neither LU faculty nor LU administrators have the ability to determine the name of the student who completed a specific evaluation form. The primary purpose of course evaluation is the improvement of instruction. That is, after the semester has ended and grades have been awarded, I am able to access the results of my course evaluations, to include all student comments. I analyze the data and read the comments, and often use student observations and suggestions to make changes in course content and delivery. The results of course evaluations are also used by chairs and deans as one factor in decisions involving merit pay, tenure, and promotion. Both the administration and I take your input via course evaluations very seriously, and I encourage you to participate in this process. Any questions or comments you have about the process should be addressed to Dr. Tom Matthews, University Assessment Coordinator, at 409-880-2385 or tom.matthews@lamar.edu. Thank you. Students with Disabilities: It is the policy of Lamar University to accommodate students with disabilities pursuant to federal and state laws and the University’s commitment to equal educational opportunities.This course complies with the University Policies on Disability, Accommodations and Academic Honesty as published in the Student Handbook and also in the Computer Science Department Policy (on Academic Honesty). Student needing accommodations must first have them approved through the Office of Services for Students with Disabilities, Communication Building Room 105, phone number 409-8808347.
Please notify the instructor during the first week of class regarding accommodations needed for the class. University Policy on Academic Honesty: The University expects all students to engage in all academic pursuits in a manner that is above reproach.“Cheating” include:· Copying from another student’s paper, report, computer files, data listings, and/or programs.
· Using (during an exam) materials not authorized by the instructor giving the exam.
· Collaboration, without authorizations, with another person during an examination or in preparing academic work.
· Knowingly, and without authorization, using, buying, selling, stealing, transporting, soliciting, copying, or possessing in whole part, the contents of an unadministered test.
· In the taking of an examination or in the preparation of academic work to be submitted for academic credit, (1) Substituting for another student, (2) permitting any other person, (3) or otherwise assisting any other person to substitute for oneself or another student.
· Bribing another person to obtain an unadministered exam or information about an unadministered exam.
· Purchasing (or acquiring) and submitting as one’s own work any research paper or other writing assignment prepared by an individual or firm. This does not apply to the typing of the rough and/or final versions fo an assignment by a professional typist.
“Plagiarism”: The appropriation of another’s work or idea and the unacknowledged incorporation of that work or idea into one’s own work offered for credit. “Collusion”: The unauthorized collaboration with another person in preparing work offered for credit. Course Attendance Policy: It is the student’s responsibility to make sure that you are officially enrolled in this course. If at any point in time, you decide to drop the class, it is your responsibility to officially drop. The instructor will do everything possible to help you. Any student who stops attending the class and does not officially drop the course will be given an “F” as the final grade. Regular class attendance is critical to your effective learning. Hence each time you miss the class without the instructor’s authorization, your final grade will be lowered by one letter grade.Please view the Lamar University web page for dates for drops and withdrawals. Student Services:
Some useful student services sites are listed
below:
1.
Lamar
University academic support services
2.
General
Lamar University Students Services
3.
SMARTHINKING
SMARTHINKING connects students to E-structor
Certified tutors anytime from any Internet connection.
Your SMARTHINKING
login is your myLamar email address. Your SMARTHINKING password is constructed
as follows:
YY –
2-digit year of birth
MM –
2-digit month of birth
DD –
2-digit day of birth followed by “_” (Use the _ with no
quotations)
Last
initial – capital letter
First
initial – capital letter
Last four
digits of your social security number.
Example:
John Doe
born January 25, 1981 Social Security Number of 123456789
His
Password: 810125_DJ6789
Campus Closure (academic continuity plan):
In
the event of
campus closure and evacuation due
to a hurricane or other
disaster,
this course will
continue in an
online format until campus reopens. After
four days of closure (for
evacuation and
relocation), please login
to this course on Blackboard for any special instructions
to continue your learning activities.
These efforts will allow
you to complete the
course and semester on
time.
Special Notes: 1. The first violation of the above specified University Policy on Academic Honesty will get a grade of 0 and the second violation will get a final grade of F.
2. Furthermore, everything you turn in to the instructor to be graded is expected to be your own work at least for the most part.
In particular, NO solution programs available on a computer locally or through the INTERNET should be copied without the instructor's prior approval. 3. All programs will be accepted only in class and only when they are due. No sooner or no later.
4. It is to your advantage if you highlight output statements such as Java System.out.print() or System.out.println() or C++ cout statements of your programs to clearly indicate where in your program outputs are being actually done.
5. A program is normally due in a week and half after it is assigned.
6. Every four unexcused absences from class will lower your final grade by one letter grade.
7. Each program must have a comment at the VERY beginning of the program.
Without this comment, a program will not be graded at all. This comment must include: a. Your full name b. Course Number and program number c. Program title d. Your own assessment of the program that includes, among others: i. whether or not the program produces expected correct outputs. ii. if not, why you think the program is not producing the expected correct outputs. iii. if not, whether or not the program was compiled at all. 8. If the language allows, the main program/function/method must appear at the very end of the program.