CSC 380 Design and Analysis of Algorithms

DRAFT (4 Jan 2019)

Section 001: T-R 12:30-1:45 PM, CIS 1006


Course Schedule

INSTRUCTOR

Professor Gene Tagliarini
E-mail: tagliarinig@uncw.edu
Phone: (910) 962-7572

OFFICE and OFFICE HOURS

CIS 2038

M&W, 9:00-11:30 AM and T&R, 9:00-10:30 AM

Other office hours may be arranged by appointment. Please email for confirmation.

TEXTBOOK

Introduction to the Design and Analysis of Algorithms, 3rd Edition, Anany Levitin, 2012, Boston, MA.

COURSE DESCRIPTION

Prerequisites: CSC 133 , CSC 231 , MAT 161 . Algorithm design paradigms such as divide and conquer, greedy, and dynamic programming; techniques for algorithm analysis, such as asymptotic notations and estimates, as well as time/space trade-offs. Topics may include sorting, searching, scheduling, string matching, graph algorithms, amortized analysis, and computational geometry.


COURSE REQUIREMENTS AND GRADING CRITERIA

Your grade for this course will arise from the mid-term test, the final examination, and a semester team software project, professional presentations and peer-reviewed paper:

1.      Midterm test (30%), date appears in the schedule;

2.      Final exam (30%), date scheduled by UNCW;

3.      Class team software A) project, B) presentations, and C) paper (total 40%);

a.       Identify and state precisely, mathematically and analytically a problem of interest and at least three, nontrivial algorithms for finding solutions to that problem;

b.      Present your algorithms to your peers for review and incorporate feedback into your project by implementing, executing, testing and analyzing correct code for the algorithms;

c.       Document the performance of those algorithms, at least, with respect to run time, solution quality and resource demands, such as memory, (The documentation must employ the formal language of algorithm analysis to express an assessment of the relative merits of the algorithms studied.);

d.      Present your analysis to your colleagues in class for review and incorporate suggestions arising from that review into your final report; and

e.       Provide at least five questions (and your answers) about the algorithms for consideration for inclusion on the Final Examination. You will be asked questions regarding your implementation and you will be expected to be able to provide analytical reasons for implementation choices.

f.       Document and report the contributions of each member of the team to the overall project.

g.      Each team will report to the instructor a rank for every project, report and presentation. Given N teams, each must be assigned a rank from the set S of labels S = {1,,N}, where the rank label 1 is best. A rank might be represented as a permutation of the labels. For example, if there were 5 teams, N=5, and the 5-tuple (3, 5, 4, 1, 2) could indicate that team 3 was first, team 5 was second, team 4 was third, team 1 was fourth, and team 2 was fifth.

GRADING SCALE

90 - 100 A

80 - 89.99 B

70 - 79.99 C

60 - 69.99 D

If your final average falls just below a cutoff, the higher grade may be assigned solely at the discretion of the instructor. In order to qualify for such consideration you should be a regular, constructive participant in the class, personally engaged in the learning process, and consistently cooperating with the objectives of the course and the goals of the instructor.

You are expected to take an active role in your learning in this course. This includes cooperating with the instructor and the objectives of the course, regularly attending, contributing in class, reading the textbook, cooperating fully on all team work, and completing all course requirements. Work together; form groups. Studies have shown that group study often results in a full grade higher average.

 

In choosing UNCW, you have become part of our community of scholars. We recognize that the UNCW learning experience is challenging and requires hard work. It also requires a commitment to make time available to do that hard work. The university expects you to make academics your highest priority by dedicating your time and energy to training your mind and acquiring knowledge. Academic success in critical thinking and problem solving prepares you for the changes and challenges you will encounter in the future. Our faculty and academic support resources are readily available as partners in this effort, but the primary responsibility for learning is yours.

It is the responsibility of every student to uphold and maintain the UNCW Academic Honor Code. For specific information, refer to the Student Handbook and Code of Student Life.

If you have a disability and need reasonable accommodation in this course, you should inform the instructor of this fact in writing within the first week of class or as soon as possible. If you have not already done so, you must register with the Office of Disability Services in Westside Hall (extension 23746) and obtain a copy of your Accommodation Letter. You should then meet with your instructor to make mutually agreeable arrangements based on the recommendations of the Accommodation Letter.

Student Learning Outcomes for CSC 380 are:

Students will:

1.       Learn, and demonstrate their knowledge of, algorithm design paradigms and the language of algorithm analysis;

2.       Choose data representations and identify, design, and implement multiple algorithms, based upon design paradigms (such as, divide-and-conquer, greedy algorithms, graph algorithms, randomized algorithms or dynamic programming);

3.       Analyze the algorithmic complexity of algorithms and employ mathematical, analytical, and asymptotic notation to describe their relative merits; and

4.       Develop an understanding of NP-completeness.

 

In this offering of CSC 380, students will accomplish these SLOs by appropriately answering in-class test questions and by:

1.       Identifying or formulating a problem of interest to both the instructor and the student using both natural and formal analytical language;

2.       Choosing data representations and identifying, designing, implementing, and testing multiple algorithms, based upon design paradigms (such as, divide-and-conquer, greedy algorithms, graph algorithms, randomized algorithms or dynamic programming);

3.       Analyzing the algorithmic complexity of the tested algorithms and employing mathematical, analytical, and asymptotic notation to describe their relative merits; and

4.       Demonstrating a conceptual understanding of NP-completeness.