CSC 421: Algorithm Design and Analysis
Spring 2016



9:30-10:45 MW
110 Eppley
Dr. David Reed
203D Hitchcock      x2583
DaveReed@creighton.edu


Text: Introduction to the Design and Analysis of Algorithms, 3rd ed., Anany Levitin, Addison Wesley, 2012.

Prerequisite: CSC 321

Course Description

This is the fourth course in the computer science sequence, building upon the concepts and skills acquired in the first three. Whereas CSC 221 and CSC 222 focused on the design of simple algorithms and CSC 321 focused on basic data structures, this course considers both facets of problem solving and their interrelationships. In order to solve complex problems efficiently, it is necessary to design algorithms and data structures together since the data structure is motivated by and affects the algorithm that accesses it.

As the name of the course suggests, special attention will be paid to analyzing the efficiency of specific algorithms, and how the appropriate data structure can affect efficiency. Specific topics covered in this course will include: advanced data structures (e.g., trees, graphs and hash tables), common algorithms and their efficiency (e.g., binary search, heapsort, graph traversal, and big-Oh analysis), and problem-solving approaches (e.g., divide-and-conquer, backtracking, and dynamic programming).

The specific goals of this course are:


Required Work

Students will complete 5-7 assignments throughout the semester. Most assignments will involve the design and implementation of Java programs that appropriately utilize data structures and algorithms. Assignments may also contain written components, for example, justifying design choices or analyzing program behavior. Late assignments will be accepted up to 7 days after their due date, with a 25% penalty. Beyond 7 days, late submissions will not be accepted. There will be 8-10 module quizzes, one 75-minute midterm exam, and a cumulative final exam (see the schedule below for exam dates).

There is no specific attendance policy for the course, although it is expected that absences will leave the student unprepared for tests and assignments. Quizzes and tests will not be rescheduled except in extreme circumstances. However, the lowest quiz grade will be dropped. The final grade for the course will be based on the following weightings:

module quizzes/exercises 05 %
5-7 programming assignments 45 %
75-minute midterm exam 20 %
100-minute final exam 30 %

At the minimum, departmental grading cutoffs for the final average will apply. That is, 92-100% guarantees an A, 87-91% a B+, 82-86% a B, 77-81% a C+, 71-76% a C, and 60-70% a D. Depending on class performance, some shifting of grades (in an upward direction only) may occur as final letter grades are assigned.

It is expected that all students check their Creighton email accounts regularly. Official announcements, such as assignment revisions or class cancellations, will be distributed through Creighton email.


Policy on Collaboration

Creighton's policy on cheating and plagiarism is spelled out in the the Student Handbook, with college procedures available online. In addition to this, the following guidelines hold pertaining to programs. Programs are to be the sole work of the student -- collaboration on the design or coding of a program is not allowed. Questions regarding homework assignments should be directed at the instructor only. Students may seek debugging assistance or clarifications on assignments using the class mailing list (via BlueLine). Repeat: All student interactions regarding homework assignments must take place via the class mailing list!

Violations of this collaboration policy will be dealt with severely, with possible outcomes including failure in the course. In the case of programming assignments, you are encouraged to start early so that there is time to seek help from the instructor as the need arises.


Daily Schedule (check regularly for updates)

Date Topic Readings Assignments
Jan 13 Course overview. (pptx/pdf) HW1: due 1/26
18
20
Java/Data Structures review. (pptx/pdf)
Brute force: (pptx/pdf)
321 material, Ch. 1-2
Ch. 3

 
25
27
     generate & test, nP-hard, efficiency.
Decrease-and-conquer: (pptx/pdf)
 
Ch. 4

 
Feb 1
3
     by-constant, by-constant-factor, by-variable-amount.
snow day -- no class
 
 
HW2: due 2/14
 
8
10
Divide-and-conquer. (pptx/pdf)
Transform-and-conquer. (pptx/pdf)
Ch. 5
Ch. 6
 
 
15
17
Space vs. Time. (pptx/pdf)
     string matching, Boyer-Moore.
Ch. 7
 
 
HW3: due 3/4
22
24
Greedy algorithms: (pptx/pdf)
     Prim's, Dijkstra's, Huffman codes.
Ch. 9
 

 
29
Mar 2
MIDTERM EXAM
work day
 
 
 
 
7
9
SPRING BREAK -- NO CLASS
14
16
midterm and HW4 review
Backtracking: (pptx/pdf)
 
Ch. 12.1
HW4: due 3/29
 
21
23
     maze search, blob counting,
     branch and bound, game search.
 
Ch. 12.2
 
 
28
30
EASTER MONDAY -- NO CLASS
Dynamic programming: (pptx/pdf)
 
Ch. 8
 
Apr 4
6
     bottom-up, binomial coefficient,
     caching, Floyd's algorithm.
 
 
HW5: due 4/17
 
11
13
Analyzing problems: (pptx/pdf)
     stable matching, lower bounds.
Ch. 10
Ch. 11
 
HW6: due 4/29
18
20
Complexity & computability: (pptx/pdf)
     complexity theory, decidability,
Ch. 12.3
 
 
 
25
27
     P vs. NP, Halting Problem, NP-complete.
work day -- no class
 
 
 
 
May 2
FINAL EXAM    Mon, 8:00-9:40

Sample code from class



In the event of disruption of normal classroom activities due to a flu outbreak or other emergency, the format for this course may be modified to enable completion of the course. In that event, you will be provided an addendum to this syllabus that will supersede this version.